뚝딱뚝딱

***해시알고리즘을 사용한 java 코드가 궁금하다면 아래 블로그를 참고하세요***

2023.10.18 - [CO-TE/challenge] - [프로그래머스] java / c++ LV2 전화번호 목록 / 해시알고리즘, SORT 풀이 (2)

이 문제는 처음에 c++로는 2중 for문을 돌면서, 배열에서 첫번째 전화번호를 기준으로 시작하여, 다른 전화번호들 중 기준이 되는 전화번호보다 길이가 작으면 continue로 건너 뛰고, 그렇지 않으면, substr을 사용해 기준 전화번호 길이만큼 잘라서 비교한 후, 문자열이 동일하면 false를 반환하는 방식으로 접근했다.

이렇게 하면 테스트 케이스는 다 맞지만, 효율성에서 떨어지게 된다. 당연히 무식하게 2중 for문으로 일일이 확인하기 때문에 복잡도가 O(n^2)일 수 밖에 없다.

문제의 카테고리에서 주어진 방식대로 해시 알고리즘을 사용해서 풀면 효율성 문제를 해결할 수 있지만, 사실 해시 알고리즘을 어떻게 사용하는지 몰랐기 때문에, 다른 사람의 코드를 보고 참고하여 먼저 정렬을 이용해 더 쉽게 풀이하였다.

  c++ / sort 함수와 1중 for문으로 풀기 

string 타입의 배열 phone_book을 <algorithm> 헤더에 있는 기본 정렬 함수인 sort()를 통해 정렬한다.

숫자로 표현된 문자열의 경우 사전식으로, 각 문자열의 첫번째 값부터 비교한다. 

첫번째 값들이 다 동일하면 두번째 값을 비교한다.

즉 숫자 그 자체가 큰지가 아니라, 앞에 문자열부터 각 숫자가 작은 것 부터 정렬하는 방식이다

예) "12" "14" "112" 가 있으면, 112, 12, 14 순으로 정렬 된다.

첫번째 1은 모두 같고, 두번째 값이 1,2,4순이기 때문이다.

따라서 이렇게 정렬을 먼저 해 놓으면, 자연스럽게 접두사가 될 확률이 높은 문자열이 앞에 위치하게 되고, 해당 접두사를 가지는 문자열은 무조건 그 문자열의 다음에 정렬될 것이기 때문에, 이 방법은 1중 for문으로도 인접한 문자열에 대해 한번씩만 비교하면 된다. 

해당 코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool solution(vector<string> phone_book) {
    bool answer = true;
    
    sort(phone_book.begin(), phone_book.end());
    
    for(int i=0; i<phone_book.size()-1; i++){
        string s = phone_book[i+1].substr(0, phone_book[i].size());
        if(phone_book[i]==s) {
            answer = false;
            break;
        }
    }
  
    return answer;
}

• sort함수에 배열의 첫번째 요소와, 배열의 마지막 요소를 인자로 넣어주면, 자동으로 정렬된다.
• 1중 for문을 통하여 string 문자열 s에는 현재 접근하는 phone_book의 전화번호 바로 다음에 위치한 전화번호를, 접두사 길이 만큼 잘라 (substr을 사용) 저장한다. 이때 c++에서는 substr(시작 인덱스, 자르고 싶은 만큼의 문자열 크기) 이므로 이에 유의한다. 
• 그래서 현재 접두사 후보의 값과 s가 일치한다면 false를 반환하도록 answer에 설정해준다.

사실상 해시 알고리즘으로 푸는 의도의 문제이긴 하지만, 실제 코테에서는 이 방법을 꼭 사용하라는 명시가 없기 때문에, 위와 같이 효율적인 코드가 생각이 난다면 당연히 사용해도 좋다.

그러나 해시 알고리즘을 이번 기회에 알고 넘어 가기 위해 java를 이용해서 한번 더 풀어보았다.

2탄에서 이어서...