프로그래머스 lv2 - 전화번호 목록

https://school.programmers.co.kr/learn/courses/30/lessons/42577

프로그래머스

문제 풀이

다른 번호의 접두사인 경우가 있는지 확인한다.
= 배열에 저장된 데이터 전체에 대해 비교해야 한다. 

어떤 번호가 다른 번호의 접두사인 경우가 있으면 false, 아니면 true
= 접두사인 경우가 1개만 있어도 false이다.

1. 정렬하기

접두어가 없는 경우 어쩔 수 없이 전체 데이터에 대해 비교를 하게 되지만,
정렬을 하면 어떤가?

비슷한 값의 데이터들이 모이면서 접두어가 있는 경우를 앞부분에서 찾아낼 수도 있다.

물론 여기서 말하는 정렬은 정수형 또는 실수형에 대한 데이터가 아닌 문자열에 대한 정렬이다.

vector<string> phone_book
sort(phone_book.begin(), phone_book.end());

 

2. 비교하기

그럼 정렬된 데이터를 어떻게 비교하면 좋을까?

- find

처음에는 find를 생각했다.
그러나 find는 문장 전체를 비교해서 불필요한 비교가 발생한다는 생각이 들었다.

무슨 말이냐 하면
[11, 12398711]
위와 같은 데이터가 있다고 하자.

우리는 접두사인 경우만 확인하면 되기 때문에 12398711의 앞에 두 자리에 대해서만 비교를 하면 된다.
그러나 find를 사용하는 경우, 불필요하게 12398711 전체에 대해서 11이라는 값이 있는지 없는지를 확인하게 된다.

 

- Compare

그래서 나는 Compare을 사용해보았다!

    for(int i = 0; i < phone_book.size()-1; i++){
        string current = phone_book[i];
        if(phone_book[i+1].compare(0, current.length(), current) == 0){
            answer = false;
            break;
        }
    }

current 문자열의 길이만큼만 비교하도록 말이다!

---

결과 비교

compare 사용 시

find와 compare를 사용한 코드로 각각 테스트한 결과는 다음과 같다.

예상과는 다르게 4ms 정도로 아아아주 미세하게 find가 더 빠른 효율성을 보였다.

왜 find가 더 효율적일까?

내가 놓친 경우의 수는 바로 앞부분에 대한 비교이다.
이게 무슨 말이냐 하면

[11, 21, 341]
위와 같은 데이터가 있다고 가정할 때, 
find는 11과 21의 1과 2처럼 앞자리가 다르면 바로 비교를 종료한다.

그러나 compare은 앞자리가 다르건 말건 일단 11과 21 두 자리를 비교한다.

이번 알고리즘의 경우 뒷부분까지 비교하는 경우를 막는 것보다 
애초에 처음부터 값이 다르면 초장부터 쳐내는 방법이 더 효율적인 방법이었던 것이다.

---

트라이 방식으로 풀이하는 방법도 있는 것 같던데 한 번 공부해봐야겠다.