[실전 알고리즘] 0x0F강 - 정렬 II

 

안녕하세요, 정렬 두 번째 시간입니다. 첫 시간에는 머지 소트와 퀵 소트를 배웠고 이번에는 카운팅 소트랑 라딕스 소트를 배울 예정입니다. 아마 전 시간보다는 더 쉬울거라 걱정을 조금 덜어내시고 들으면 될 것 같습니다.

 

목차는 가볍게 넘어가겠습니다.

 

먼저 카운팅 소트로 시작을 해보겠습니다. 지금 이 수열을 크기의 오름차순으로 정렬하고 싶다면 어떻게 할지 생각해보겠습니다. 일단 원소의 개수가 작아서 그냥 버블 소트같은걸 써도 될거고 이제 좀 배운 사람 답게 앞단원에서 같이 얘기한 머지 소트나 퀵 소트 같은걸 써도 됩니다. 그런데 중요한 얘기라 한 번만 더 하고 가겠습니다. 퀵 소트는 O(NlgN)이 보장 된다 안 된다? 안 된다, 최악의 경우 O(N²)이다. 꼭 기억하셔야 합니다.

 

아무튼 뭐 어찌됐든 정렬을 큰 어려움 없이 할 수 있는데 저흰 좀 더 정렬을 날로 먹고 싶습니다. 그래서 제가 (1 5 4 2 3 1 4 3)이라는 수열을 조금 변형을 해서 알려드릴테니까 정렬을 한 번 시도해보도록 합시다.

 

이 표의 의미를 아시겠나요? 이 표는 1이 수열에서 2번 나왔고 2는 1번 나왔고 3은 2번, 4는 2번, 5는 1번 나왔다는걸 의미합니다. 이 표를 보고 수열을 어떻게 정렬할지 생각해봅시다.

 

이 표만 있으면 정렬을 너무 쉽게 할 수 있는게, 그냥 1부터 차례로 나온 횟수만큼 적으면 끝입니다. 1이 2번 나왔으니 1을 2개 쓰고, 2는 1번이니 1개 쓰고, 이런식으로 하면 너무나 쉽게 정렬이 가능합니다.

뭔가 이걸 보고 느낌이 오시는게 없나요? 그냥 각 수의 등장 횟수만 세면 장땡인걸 왜 그렇게 정렬을 어렵게 했을까 하는 생각이 듭니다. 지금 이 알고리즘이 바로 카운팅 소트입니다. 정렬 알고리즘 중에서 가장 쉬운 알고리즘이라고 할 수 있습니다.

 

하지만 이 카운팅 소트는 아쉽지만 만능은 아닙니다. 일단 카운팅 소트를 쓰려고 하면 각 수의 등장 횟수를 저장해야 합니다. 그리고 등장 횟수를 세는 방법은 0x03강 - 배열 단원에서 몇 번 나왔었지만 미리 큰 테이블을 만들어두고 수에 대응되는 원소의 값을 1 증가시켜서 처리하는 방법입니다. 만약 수가 0에서 9 사이라고 한다면 freq[10] 배열을 선언해서 처리할 수 있고 수가 0에서 9999 사이라고 한다면 freq[10000] 배열을 선언해서 처리할 수 있습니다.

 

그런데 만약 수의 범위가 0에서 999,999,999 까지라고 하면 크기가 10억인 배열이 필요합니다. 그리고 메모리 제한이 512MB라고 해도 int 기준 대략 1.2억인 배열밖에 잡을 수 없으니 이러면 카운팅 소트를 써먹을 수가 없습니다. 결론적으로 말해서 수의 범위가 어느 정도 한정적일 때에만 카운팅 소트를 쓸 수 있습니다. 이론적으로는 수의 범위가 0에서 1억까지여도 카운팅 소트를 쓸 수 있지만 풀이를 하는 입장에서는 수의 범위가 대략 1000만 이하일때에는 카운팅 소트를 쓰고 그렇지 않을 경우에는 카운팅 소트를 쓰지 못한다고 생각을 하시면 되겠습니다.

설명이 길어졌는데, 아무튼 바로 카운팅 소트를 구현해보겠습니다. BOJ 15688번: 수 정렬하기 5 문제를 같이 풀어보겠습니다. 조금 전에도 언급했지만 freq 배열에 등장 횟수를 저장하고 그 횟수를 보며 정렬된 결과를 출력한다고 생각하면 아주 간단하게 구현할 수 있습니다. 그리고 문제에서 수의 범위가 절댓값이 1,000,000보다 작거나 같은 정수, 즉 -1,000,000에서 1,000,000 까지이기 때문에 freq 배열에 값을 넣으려고 할 때 약간의 처리가 필요한데 여러분들의 응용력을 믿기 때문에 먼저 코드를 작성하는 시간을 가진 후에 제 코드를 같이 살펴보도록 하겠습니다.

 

작성을 해보니 어떤가요? 아마 난이도가 그렇게 높지는 않다고 생각이 드는데 혹시 뭔가 꼬였더라도 너무 좌절하지는 마시고 제 코드를 같이 보겠습니다. 일단 수가 -1,000,000에서 1,000,000인게 껄끄러우니 freq 배열의 인덱스에 접근할 때에는 13번째 줄처럼 100만을 더했습니다. 그리고 freq 배열의 값을 보면서 수를 출력할 때에는 17번째 줄처럼 100만을 빼주면 됩니다. 카운팅 소트는 이게 다입니다.

 

시간 복잡도를 같이 생각해보면 수의 범위가 K개라고 할 때 맨 처음 N개의 수를 보면서 freq 배열에 값을 추가하고 답을 출력할 때, 혹은 정렬을 수행할 때 총 K칸의 값을 확인해야 하기 때문에 O(N+K)입니다. 즉 수의 범위 K가 작을 때에는 카운팅 소트가 굉장히 효율적으로 동작합니다. 정리하자면 수의 범위가 제한되어 있을 때에는 카운팅 소트를 쓰면 굉장히 구현이 간단해서 활용할 여지가 있다, 그렇지만 수의 범위가 크면 카운팅 소트를 사용할 수 없다 정도로 이해하고 마무리하겠습니다.

 

두 번째로는 라딕스 소트를 같이 보겠습니다. 이유는 모르겠지만 머지 소트, 퀵 소트, 카운팅 소트는 그렇게 읽어도 별로 안어색한데 라딕스 소트는 뭔가 라딕스 소트라고 말하면 어색합니다. 기수 정렬이나 Radix Sort가 더 자연스럽고 그렇습니다. 그런데 딴건 다 머지 소트, 퀵 소트, 카운팅 소트라고 적어놓고 이것만 기수 정렬이나 Radix Sort라고 쓰는건 또 좀 이상해서 그냥 라딕스 소트라고 쓰겠습니다.

라딕스 소트는 자릿수를 이용해서 정렬을 수행하는 알고리즘으로, 카운팅 소트를 응용한 알고리즘이라고도 생각할 수 있습니다. 일단 알고리즘이 어떻게 굴러가는건지 같이 살펴보겠습니다. 지금 보시는 이 10개의 수를 라딕스 소트로 정렬해보겠습니다. 012, 007 이런건 그냥 12, 7인데 설명의 편의를 위해 0을 앞에 붙여놨습니다. 과정을 보다보면 0을 붙여서 나타낸 이유를 이해할 수 있을 것입니다.

 

일단 먼저 10개의 리스트를 생성합니다. 지금 0번 리스트, 1번 리스트, ... , 9번 리스트까지 있는거고 각 리스트에 수를 넣을 예정입니다. 처음에는 수열에서 수를 하나씩 읽으면서 1의 자리에 따라 수를 넣습니다.

 

즉 처음에 012는 1의 자리가 2이니까 2번 리스트에 넣고, 421은 1의 자리가 1이니까 1번 리스트에 넣고, 이렇게 차례대로 수를 넣어줍니다.

 

이렇게 리스트에 수를 다 넣은 후에는 0번 리스트부터 보면서 수를 꺼내서 수열을 재배열합니다. 뭔가 카운팅 소트랑 비슷한듯 다릅니다.

 

일단 이 과정을 거치고 나면 수열이 1의 자리를 기준으로 재배열된다는건 이해가 갈 것입니다. 예를 들어 100은 1의 자리가 0이니 가장 앞이고, 007은 1의 자리가 7이니 가장 뒤이고, 421과 021을 보면 둘 다 1의 자리가 1인데 원래 수열에서 421이 021 앞에 있었기 때문에 1번 리스트에 421이 021보다 앞에 오게 되었습니다. 그래서 이 과정을 거치고 나면 421이 021보다 앞에 옵니다. 즉 이 재배열을 통해 1의 자리 순으로 정렬이 이루어졌고, 1의 자리 값이 같은 수들끼리는 맨 처음의 순서가 그대로 유지됩니다.

 

그 다음으로는 1의 자리를 기준으로 정렬된 리스트를 다시 10의 자리로 정렬합니다. 100은 10의 자리가 0이니까 0번 리스트에 넣고 421은 10의 자리가 2이니까 2번 리스트에 넣고 이런식으로 다시 수를 리스트에 차례로 다 넣습니다. 그 다음 1의 자리에서 한 것과 마찬가지로 0번 리스트부터 보면서 수를 꺼내서 수열을 재배열합니다. 이렇게 10의 자리까지 처리를 끝냈습니다.

 

1의 자리에 대해서도 했고 10의 자리에 대해서도 했으니 마지막은 100의 자리입니다. 리스트를 채우고 재배열하는 과정은 설명 없이 넘어가겠습니다. 일단 뭐가 뭔지는 모르겠지만 하란대로 했는데 결과를 확인해보면 정렬이 완료되었습니다.

 그냥 리스트를 가지고 먼저 1의 자리 순으로 재배열하고, 그 다음 10의 자리 순으로 재배열하고, 마지막으로 100의 자리 순으로 재배열했더니 정렬이 됐습니다. 왜 이렇게 정렬이 가능한지를 짚고 넘어가보겠습니다.

 

먼저 굉장히 뜬금없는 질문을 하나 드려보겠습니다. 502과 421 중에 뭐가 더 크죠? 502가 더 큰데 왜 502가 더 클까요? 그냥 당연히 502가 더 큰거 아닌가, 이걸 어떻게 설명하라는건가 싶을 것 같습니다. 그런데 왜 502가 421보다 더 큰지를 생각해보면 이 라딕스 소트를 이해할 때 아주 큰 도움이 됩니다. 시계를 좀 많이 돌려서 초등학교 2학년 때로 돌아가보겠습니다. 지금 초등학교 2학년으로 돌아갈 수 있다면 비트코인을 풀매수할텐데... 아무튼 초등학교 2학년 1학기 1단원에서 세 자리 수의 비교를 배웁니다.

 

단원의 내용에 따르면 502과 421을 비교할 땐 먼저 100의 자리를 비교합니다. 502에서는 5이고 421에서는 4여서 502가 421보다 크다는걸 알 수 있습니다. 즉 우리가 수를 비교해서 수 A가 수 B보다 더 크다고 하는건 더 큰 자리에서 A의 자릿수가 B의 자릿수보다 큰 경우가 먼저 생긴다는 얘기입니다. 이걸 인지한 상태로 다시 라딕스 소트 과정을 보겠습니다.

 

다른 수들은 신경쓰지말고 421과 502에 주목을 해보면 정렬이 잘 되었다면 정렬이 끝났을 때 421이 502 앞에 위치해야 합니다. 그리고 비록 10의 자리까지는 502가 421에 앞에 위치했지만 그 전까지 둘의 위치가 어디에 있는지와 전혀 무관하게 100의 자리에 대해 재배열을 할 때 421은 4번 리스트에 들어가는 반면 502는 5번 리스트에 들어가기 때문에 재배열을 끝낸 후 421이 502보다 앞에 올 수 밖에 없다는걸 알 수 있습니다.

 

100과 103을 예시로 들어서 한번 더 설명하겠습니다. 100과 103은 1의 자리가 0과 3으로 다르고 10의 자리와 100의 자리는 똑같습니다. 그러면 일단 1의 자리를 기준으로 재배열할 때 100은 0번 리스트에 들어가는데 103은 3번 리스트에 들어가기 때문에 100이 103 앞에 옵니다. 그 후에 10의 자리를 보면 둘 다 0번 리스트에 들어가는데 상대적인 순서는 유지가 되니 100이 계속 103 앞에 위치하고 100의 자리에 대해서도 마찬가지로 둘 다 1번 리스트인데 상대적인 순서는 유지가 되어서 최종 결과를 봤을 때 100이 103보다 앞에 와서 정렬이 잘 수행되었습니다.

 

즉 두 수 A, B의 위치 관계를 생각해보면 A > B일 때 더 큰 자리에서 A의 자릿수가 B의 자릿수보다 큰 경우가 먼저 생기니까 라딕스 소트에서 결국 언젠가는 B가 A보다 앞에 올 수 밖에 없고 그 상대적인 위치 관계가 계속 유지된 채로 정렬 과정이 끝납니다. 그렇기 때문에 이 방법을 이용하면 정렬이 잘 수행됩니다.

라딕스 소트의 시간복잡도는 자릿수의 최대 개수가 D개라고 할 때 D번에 걸쳐서 카운팅 소트를 하는 것과 상황이 똑같습니다. 그러면 리스트의 개수를 K개라고 할 때 엄밀하게 말하면 시간복잡도는 O(D(N+K))이지만 보통 리스트의 개수는 N에 비해 무시가 가능할 정도로 작습니다. 당장 지금 예시로 든 상황도 리스트의 갯수 K가 10밖에 안됩니다. 그래서 결론적으로 라딕스 소트의 시간복잡도는 O(DN)입니다.

 

그런데 새로운 소트를 배웠으니 구현을 해보는게 인지상정이지만 라딕스 소트는 맹점이 하나 있습니다. 앞에서 보면 라딕스 소트를 수행하기 위해 10개의 리스트가 필요했습니다. 그리고 실제 구현을 할 때 C++의 배열을 이용하면 N개의 원소를 정렬할 때 한 리스트에 N개의 원소가 다 몰릴 수도 있으니 10개의 리스트 모두를 N칸의 배열로 만들어야 하는데 이건 너무 공간의 낭비가 심합니다. 공간의 낭비를 해결하려면 각 리스트를 vector와 같은 동적 배열 혹은 연결 리스트로 사용해야 합니다.

그런데 동적 배열이든 연결 리스트든 STL이 없으면 구현이 많이 까다롭고, STL을 쓸 수 있는 상황이라면 그냥 STL sort 함수를 쓰고 말지 굳이 라딕스 소트를 직접 짜고 있지는 않을 것입니다. 그렇기 때문에 코딩테스트에서 머지 소트나 기타 다른 소트를 구현할 일도 STL을 쓸 수 없는 아주 드문 환경 이외에는 없지만, 특히 라딕스 소트는 구현을 해야하는 상황이 아예 없습니다. 그래서 라딕스 소트는 개념 이해만 하고 넘어가도 되긴 합니다. 그래도 구현이 그렇게 어렵지는 않아서 구현 코드를 한 번 보여드리긴 하겠습니다.

 

코드를 간단하게만 짚고 넘어가보면 n은 원소의 수, arr는 정렬을 하고 싶은 원소들의 목록, d는 자릿수의 최댓값, p10은 10의 지수를 저장할 배열입니다. 지금은 원소들이 1000 미만이기 때문에 d를 3으로 뒀습니다.

 

digitNum 함수는 x에서 10^a 자리를 추출하는 함수입니다. 예를 들어 digitNum(253, 1)은 253에서 10의 자리인 5를 반환합니다. vector<int> 배열 l은 0번에서 9번 리스트를 나타내고, p10[i]은 10ⁱ를 저장할 변수인데 그 값을 18, 19번째 줄처럼 하는게 정석입니다. 무심코 pow 함수를 써서 p10[i] = pow(10, i); 와 같은 방식으로 하면 pow는 실수형을 반환하는 함수이기 때문에 실수 오차로 인해 꼬여버릴 수 있다는 점 꼭 인지하시고 혹시 다음에라도 정수 거듭제곱을 계산해야 하면 pow 함수 대신 지금 이 코드와 같은 방식으로 작성해야 합니다. 

 

그 후로는 22, 23번째 줄처럼 자릿수를 가지고 리스트에 값을 넣고 24, 25, 26, 27번째 줄처럼 그 결과를 다시 arr에 넣는걸 d번에 걸쳐서 반복하면 구현이 끝납니다.

 

이제 마지막 얘기 하나만 딱 하고 라딕스 소트를 끝낼건데, 혹시 저번 시간에 배운 버블, 머지, 퀵 소트와 이번 시간에 배운 카운팅, 라딕스 소트는 계산 과정에서 차이가 있습니다. 저번 단원에서 다룬 머지, 퀵, 버블 소트는 원소들끼리 크기를 비교하는 과정이 있었는데 카운팅, 라딕스 소트는 원소들간의 크기를 비교 하지 않고 정렬을 수행합니다. 그래서 버블, 머지, 퀵 소트는 Comparison Sort인 반면 카운팅, 라딕스 소트는 Non-comparison Sort입니다. 코딩테스트를 칠 때 필요한 개념은 아니지만 알아두면 좋을 것 같아서 소개를 해드렸습니다.

 

이렇게 두 단원에 걸쳐서 머지 소트, 퀵 소트, 카운팅 소트, 라딕스 소트 이 4개를 배웠는데, 그럼 이제 진짜 코딩테스트에서 정렬을 해야 할 때 이 넷 중에서 뭘 쓰면 좋을까요? 정답은 바로 코딩테스트에서 직접 정렬을 짜고 있으면 흑우다 이말입니다.

 

코딩테스트에서는 STL에 있는 sort 함수를 써서 정렬을 딱 한 줄의 코드로 수행할 수 있습니다. 배열의 경우에는 인자로 포인터 2개를 넘겨주는건데 지금처럼 원소가 5개일 때 두 번째 인자로 7을 가리키는 a+4가 아닌 a+5를 넘겨줘야 합니다. next_permutation 함수에서도 비슷한 상황이었으니 헷갈리면 안됩니다.

vector에서는 iterator 2개를 넘겨주고 begin(), end()로 건네주면 됩니다. b의 길이가 5일 때 b.end()는 b.begin() + 5이니 두 번째 인자를 b.begin() + 5로 줘도 괜찮습니다. 참고로 STL sort는 퀵 소트를 기반으로 하지만 리스트가 불균등하게 쪼개지는 상황이 계속 반복되어서 재귀에서의 깊이가 너무 깊어지면 O(NlgN)이 보장되는 정렬 알고리즘으로 나머지를 처리합니다. 그래서 STL sort는 최악의 경우에도 O(NlgN)이 보장되기 때문에 마음 편하게 쓰면 됩니다. 더 찾아보고 싶으신 분은 Introspective sort를 검색해보시면 좋을 것 같습니다. 다만 sort 함수는 stable sort가 아닙니다. 그래서 동일한 우선순위를 가진 원소들 사이의 상대적인 순서가 보존되지 않을 수 있습니다. 꼭 stable sort가 필요하다면 stable_sort 함수를 사용하면 됩니다. stable_sort 또한 sort 함수와 사용법이 똑같아서 자세한 설명은 생략하겠습니다.

또한 pair, tuple에는 이미 대소 관계가 우리에게 익숙한대로 먼저 제일 앞의 원소의 대소를 비교하고, 값이 같으면 그 다음 원소의 대소를 비교하는 방식으로 정해져있습니다. 예를 들어 pair에서 {2, 5} < {3, -2}고 tuple에서 {2, 1, 0} > {2, -2, 6}입니다. 그래서 좌표를 정렬하거나 기타 여러 속성이 있는 원소를 정렬할 때 별도로 구조체를 둘 필요가 없고 pair나 tuple 등을 이용하면 됩니다.

 

STL sort에는 아주 강력한 기능이 하나 더 있는데, 비교 함수를 내가 정해서 넘겨줄 수 있습니다. 예를 들어 int형을 크기 순으로 정렬하고 싶으면 위의 코드와 같이 하면 되는데 int형을 5로 나눈 나머지 순으로, 5로 나눈 나머지가 같다면 크기 순으로 정렬하고 싶다고 해보겠습니다. 그럴땐 아래의 코드와 같이 비교 함수를 만들어서 인자로 주면 됩니다. 이렇게 하면 배열 a가 5, 1, 6, 2, 7, 3, 4로 정렬됩니다. 이처럼 비교 함수 cmp(int a, int b)는 a가 b의 앞에 와야할 때 true를, 그렇지 않을 때에는 false를 반환해야 합니다.

 

비교 함수에서 가장 실수하기 좋은게 있는데, a가 b의 앞에 와야할 때만 true를 반환해야 하니 두 값이 같을 때 혹은 우선순위가 같을 때에는 반드시 false를 반환해야 합니다.

 

예를 들어 수열을 크기의 내림차순으로 정렬하고 싶을 때 왼쪽과 같이 비교 함수를 작성하면 얼핏 봤을 때에는 문제가 없어보이지만 a와 b가 같을 경우 true를 반환하기 때문에 오류가 발생할 수 있습니다. 오류란게 정확히 어떤거냐면 sort 함수가 도는 과정에서 런타임 에러가 발생할 수 있습니다. 이게 참 웃긴게 비교 함수가 올바르지 않다고 해도 100% 런타임 에러가 발생하는건 아니어서 두 값이 같을 때 true를 반환하는 코드를 제출해도 운이 좋으면 통과될 수 있긴 합니다. 그래도 구글에 STL sort 런타임에러라고 검색해보면 열에 아홉은 지금 이 문제여서 꼭 두 값이 같을 때 false를 반환해야 한다는 점을 기억해야 합니다. 지금 이 코드는 오른쪽과 같이 변경하는게 나아보입니다.

 

주의사항 두 번째는 reference에 관한 부분입니다. 문자열을 받아서 끝자리의 알파벳 순으로 정렬하고 싶다고 하면 비교 함수를 왼쪽과 같이 작성하면 결과가 정상적으로 나옵니다. 그런데 이렇게 작성을 하면 별로 바람직하지 않습니다. 0x02강에서도 잠깐 언급했지만 함수의 인자로 STL이나 구조체 객체를 실어서 보내면 값의 복사가 일어나는데 지금 이 비교 함수를 생각해보면 굳이 복사라는 불필요한 연산을 추가로 하면서 시간을 잡아먹을 필요가 없습니다. 그래서 복사를 하는 대신 reference를 보내는게 더 바람직합니다.

 

const string& a, const string& b라고 쓰면 이 cmp 함수에서 a와 b의 값은 변하지 않는다는걸 명시적으로 나타내기 때문에 제대로 된 코딩을 할 때에는 const라는걸 달아주는게 좋은데 사실 코딩테스트에서는 그냥 const를 쓰지 않아도 크게 상관은 없습니다.

 

다만 주의사항 1번과는 다르게 지금 지적한 이 문제로 수행 시간에서 약간의 차이가 있을 수는 있지만 원래는 맞을 코드가 시간 초과가 나거나 시간 초과가 나야할 코드가 통과되거나 할 정도의 큰 차이는 아니긴 합니다. 그래서 특히 두 값이 같을 때 false를 반환해야 한다는 점을 꼭 기억해주시면 좋겠습니다. 비교 함수를 연습해보기 위해 STL sort를 가지고 1431번: 시리얼 번호 문제를 한 번 풀어보시면 좋은 연습이 될 것입니다.

 

정렬에 대해 다룰건 다 다뤘고 마지막으로 정렬을 써먹을 수 있는 문제를 소개하겠습니다. 단순히 답을 오름차순으로 출력하라는 것과 같이 직관적으로 정렬이 필요함을 알 수 있는 문제 말고 정렬을 이용해서 시간복잡도를 개선할 수 있는 문제를 같이 보겠습니다. BOJ 11652번: 카드 문제를 확인해주세요.

 

문제를 보면 리스트에서 가장 많이 나온 수를 찾는 문제이고 아마 O(N²) 풀이는 너무나 직관적으로 보일 것입니다. 그냥 각 수에 대해서 전체 리스트를 다 보면서 그 수가 몇 번 등장했는지를 세면 끝입니다. 그런데 O(N²)이면 시간초과이니 더 좋은 방법을 찾고 싶은데 마땅치가 않습니다. 보통 등장 횟수를 찾는 상황에서는 각 인덱스를 가지고 등장 횟수를 세는 큰 배열을 이용하기 마련인데 지금은 수의 범위가 -2⁶²에서 2⁶²인만큼 가능하지 않습니다. 좀 배우신 분이라면 C++의 map을 떠올릴 수 있겠지만 map은 아직 배우지 않았고 또 이진 검색 트리라는 개념을 사용하는 만큼 map을 이용한 풀이는 배제하겠습니다. 그러면 이 문제를 어떻게 해결하면 좋을까요?

 

일단 지금 주어진 리스트를 놓고 뭔가를 해보려고 하면 뭐 할 수 있는게 없습니다. 대신 이번 단원에서 배운걸 이용해서 정렬을 해놓고 나면 뭔가 좀 희망이 보입니다. 정렬의 특성상 같은 수들끼리는 인접하게 붙기 때문입니다. 이렇게 정렬이 된 이후에는 O(N)에 해결이 가능한데 한 번 방법을 고민해보는 시간을 가져보겠습니다. 즉, 저렇게 정렬된 상태에서 2가 3번 나오고, 3이 1번 나오고, 5가 2번 나오고, 7이 2번 나오는걸 효율적으로 알아내는 방법을 고민해보겠습니다.

 

이게 아예 손도 못대겠다는 수준까지는 아니지만 대충 느낌은 알겠어도 처음 하면 구현이 은근 까다롭습니다. 그래서 저의 풀이를 설명드리겠습니다. 이걸 적당한 아이디어 정도만 설명해야 하나, 아니면 거의 코드를 한 줄 한 줄 뜯어보는 수준으로 설명을 해야하나 살짝 고민했는데 설명에 있어서는 과한게 부족한 것 보다 낫다는 저의 평소 지론에 따라 바로 코드로 옮길 수 있을 정도로 상세하게 설명을 드리겠습니다.

일단 저의 구현에서는 중요한 역할을 하는 변수가 3개 있습니다. 각각의 이름은 cnt, mxval, mxcnt이고 cnt는 현재 보고 있는 수가 몇 번 등장했는지, mxval은 현재까지 가장 많이 등장한 수의 값, mxcnt는 현재까지 가장 많이 등장한 수의 등장 횟수입니다. 일단 초기 값으로 cnt는 0, mxval은 -2^62-1, mxcnt는 0을 주겠습니다. mxval이 -2^62-1인 이유는 등장 가능한 수의 최솟값보다 더 작은 값으로 초기값을 둔 것이지만, 사실 mxval은 적어도 한 번은 갱신이 일어나기 때문에 처음 들어가있는 값은 크게 중요하지 않습니다. 이제 수들을 앞에서부터 차례로 보면서 이 변수들의 값을 변화시켜줄 예정입니다.

 

먼저 cnt는 현재 보고 있는 수가 몇 번 등장했는지를 나타낸다고 했습니다. 그러면 현재 보고 있는 수가 제일 앞에 있는 수이거나 현재 보고 있는 수와 바로 직전에 나온 수가 같을 때에는 그냥 cnt를 1 증가시키면 됩니다. 그래서 지금 이 첫 번째 수에 대해서는 cnt를 1 증가시키면 끝입니다.

 

그 다음 수는 직전에 나온 수도 2로 자기 자신과 똑같으니 cnt를 1 증가시키고

 

그 다음에도 마찬가지입니다.

 

이 다음의 처리가 핵심입니다. 이제는 직전에 나온 수가 2였는데 자기 자신은 3이기 때문에 더 이상 2가 연속해서 존재하지 않습니다. 이 때 mxval과 mxcnt를 업데이트해줘야 합니다. 먼저 mxcnt를 보면 2가 3번 나오기 전에 가장 많이 등장한 수의 등장 횟수가 0번입니다. 이 값보다 3이 더 크기 때문에  mxval은 2로, mxcnt는 3으로 갱신합니다. 그리고 cnt는 1로 변경합니다. 이제부터는 3이 몇 개 있는지를 세어나가면 됩니다. 그 뒤의 과정은 생략하겠습니다.

 

설명을 보고 나니 충분히 해볼만하다는 생각이 들 것 같습니다. 이렇게 이 문제를 처음 정렬에 O(NlgN), 이후의 처리에서 O(N)으로 총 O(NlgN)에 해결할 수 있습니다. 수의 범위가 int 안에는 다 담기지 않고 long long을 써야한다는 점에 주의해서 구현을 해보는 시간을 가져보겠습니다.

 

제 코드를 같이 보겠습니다. 앞의 설명을 곧이곧대로 구현하면 되는데 27번째 줄처럼 제일 마지막 수에 대한 처리가 있어야 한다는건 유의하셔야 합니다. 이 처리가 빠지면 제일 마지막 수는 등장 횟수를 세지 않게 됩니다.

 

지금 코드도 그럭저럭 나쁘지는 않지만 조금 더 세련되게 고칠 수 있는 방법이 있습니다. a[n]에 2⁶² + 1 값을 넣고 for문을 n-1까지가 아니라 n까지 돌면 27번째 줄을 지울 수 있고, 또 cnt에 0을 넣는게 아니라 1을 넣고 시작하면 i를 0이 아닌 1부터 시작해버릴 수 있어서 18번째 줄과 같이 i == 0일 때를 별도로 예외처리할 필요가 없어집니다. 이런 소소한 처리를 다 코드에 넣고 설명을 하려고 하면 내용이 길어질 것 같아서 코드에 넣지는 않았지만 이런 사소한 것들이 코드의 가독성을 높이고 실수를 줄여주기 때문에 시간 나실 때 한 번 개선을 시도해보시면 좋을 것 같습니다.

 

이 문제에서 사용한 정렬을 하면 같은 수는 인접하게 된다는 성질을 이용해 수열에서 중복된 원소를 제거할 수도 있습니다. 비슷한 문제가 나왔을 때 정렬을 하는 아이디어를 떠올려볼 수 있도록 합시다.

 

이렇게 두 단원에 걸쳐서 정렬을 같이 살펴봤습니다. 앞으로 문제를 풀 때에는 머지, 퀵, 카운팅, 라딕스 소트와 같은 것들을 직접 구현할 일이 없고 STL sort 함수만 주구장창 쓰겠지만 이렇게 한 번 해두고 나면 언젠가 면접을 앞두고 있어서 다시 공부를 할 때 큰 도움이 될 것입니다. 문제집에 있는 문제들로 STL sort 사용법도 연습해보시고 정렬을 이용하는 문제도 풀어보시면 도움이 될테니 문제들을 꼭 풀어보셔야 합니다. 특히 문제집의 문제들 중에서 7795번: 먹을 것인가 먹힐 것인가 문제의 풀이를 찾아보면 많은 사람들이 이분탐색을 이용해서 풀었을텐데 이분탐색 없이 정렬만을 가지고 해결하는 방법을 고민해보면 좋은 연습이 될 것 같습니다. 그럼 다음 시간에 만나요!