숫자로 되어있는 문자열의 정렬 기준(전화번호 목록 문제 부가 설명)

프로그래머스 고득점 Kit에 "전화번호 목록"이라는 문제가 있습니다. 주어진 전화번호 목록에서 특정 전화번호가 다른 전화번호의 접두사가 아닌지 비교하는 문제인데, 여기서 정렬을 활용하지 못하면 O(n2)으로 문제를 접근하게 됩니다. 반면, 정렬을 활용하면 O(n)의 시간복잡도로 문제를 풀수가 있습니다.

 

해시 문제, 문자열 문제 등에서 자주활용되는게 정렬이기에 숫자에 관한 정렬도 알아두면 좋은 부분이라고 생각합니다. 에시 2개로 간단하게 살펴보겠습니다.

 

 

첫번째 예시)

만약 위와 같은 문제에서 어떻게 정렬이 되는지 정확하게 알고 계시다면 이번 포스팅에서 볼 부분을 다 알고 계시기에 넘어가셔도 괜찮습니다.

 

정답은 01, 1, 10, 100, 1009, 11, 15, 3, 30, 3100, 9999, c 순서입니다. 왜 그렇게 될까요?

 

숫자형태인 문자열을 정렬하면 어떻게되나? -> 사전순 정렬

a, b, c, d, 가, 나, 다, 라 등 우리가 보통 자주쓰는 사전순이라고 하면 당연히 일반적인 문자형태고 이는 익숙한편이지만 숫자를 사전순으로 볼일은 크게 없으니 알고 있더라도 까먹었을 경우가 있습니다. 즉, 코딩테스트 문제를 풀 때 접하게 되는 경우가 많습니다. 다른 예시를 보면서 조금 더 자세히 보겠습니다.

 

 

두번째 예시)

숫자가 문자열로 된경우는 한자리씩 비교해서 더 작은 것, 그 다음 자리에서도 똑같이 반복합니다.

"0", "0000", "00", "000" -> "0", "00", "000", "0000" 이 경우 비교대상이 모두 0이라 쉬워보입니다.

 

 

세번째 예시)

이런 경우라면 어떻게될까요? 우선 첫째자리부터 살펴보면서 가장 작은걸 찾습니다. "100"은 1로 시작하기에 다른 0들로 시작하는 것과 비교하기 어려워보입니다. 우선순위에서 제외됩니다. 나머지는 모두 0으로 시작하기에 그 다음자리수를 비교하려고 하는데 그 다음 자리수가 없는 "0"이 존재합니다. 따라서, "0"은 가장 우선순위로 정렬해줍니다.

 

두번째 자리로 넘어가서 비교합니다. "01", "002", "010" 등이 대상이며, 여기서 두번째가 가장 작은 숫자는 "002"가 됩니다. 따라서 두번째 정렬대상은 "002"가 됩니다. 그러면 남은건 "01"과 "010"이 남았는데 이렇게 앞자리가 같은 경우는 더 짧은 숫자가 우선순위가 되어 "01"이 우선정렬됩니다. "01"까지 끝났으니 나머지 "010"이 대상이 됩니다.

 

그렇다면 전체적으로 순서는 "0", "002", "01", "010", "100"이 되겠습니다.

 

 

네번째 예시)

마지막 예시입니다. 전화번호 목록이라는 문제에서 특정 전화번호가 다른 전화번호의 접두사인지를 물었기 때문에 정렬기준을 명확하게 파악했다면 해당 문제를 비교시 현재 비교대상과 바로 그 뒤에있는거만 비교하면 되게됩니다. 위 예시의 정렬 결과는 어떨까요?

 

위에서 살펴본 예시들로 똑같이 과정이 진행되면서 110, 111, 119, 119112, 120, 12011192223, 121 이렇게 정렬 될것입니다.

 

 

전화번호 목록이라는 문제를 풀면서 숫자형태의 문자열 정렬 기준에 대해서 자세하게 살펴봤는데, 이해가 안되는 부분 있다면 알려주시면 감사하겠습니다.