백준 1181번 – 단어 정렬

백준 1181번 – 단어 정렬

요즘은 백준 온라인저지(https://www.acmicpc.net/)에서 단계별 문제 풀기를 틈틈이 하고있다. C 언어를 아주 기초만 알고있기도 하고 해서 그냥 기초부터 제대로 다질 겸 쉬운 문제들부터 풀고있다.

최근에 정렬문제 묶음을 풀다가 좀 헤맸던 문제가 1181번 문제다. 문제 자체는 쉽다. 단어들이 주어지면 먼저 길이가 짧은 순으로, 길이가 같으면 사전 순으로 정렬하여 출력하는 것이 목표이다. 그런데 자꾸만 시간초과로 통과하지 못했다.  분명 정렬 알고리즘 중엔 가장 빠른 편이라는 퀵소트를 이용한 코드를 썼음에도 말이다. 아래가 바로 퀵소트를 이용한 코드.

 

입력을 받는대로 struct word배열인 words[]에 문자열과 문자열의 길이를 넣고, 바로 퀵소트를 돌린다. stringcmp라는 함수를 통해 두 단어의 대소관계를 파악한다. 대소관계가 뒤바뀌어 있다면 swap함수를 통해 두 word의 순서를 바꾼다.  정렬이 끝나면 words[]를 첫 번째 원소부터 출력한다. 어렵진 않은 코드다.

인터넷을 찾아보면 모두 <algorithm.h>를 사용한 코드들밖에 안보이는데,  algorithm.h에서 제공하는 정렬 알고리즘을 사용한다는 점을 빼면 입력을 받거나 출력을 받는 부분, 자료구조의 형태 등은 다 비슷했다. sort알고리즘에 대해 더 찾아보니 algorithm.h에서 사용하는 sort 알고리즘도 그냥 O(nlogn)정도 걸린다고 명시되어 있어서 더욱 난감한 부분.(http://www.cplusplus.com/reference/algorithm/sort/). 퀵소트도 보통 O(NlogN)인데… 뭐가 문제일까?

귀찮지만, 퀵소트랑 동일한 시간복잡도를 가지는 머지소트를 실행해봤다. 바로 풀렸다.

 

바뀐 부분은 퀵소트에서 사용한 words[]배열을 두 개로 쪼갠 것이다.  wordsA[]를 입력 받은 단어들의 정보를 저장하는 부분으로, wordsB[]를 머지소트를 위한 여분의 배열로 선언했다. 그리고 머지소트 이용. 그 외에는 사실상 똑같음.

개인적으로 원인을 생각해보면 백준에서 제공하는 테스트케이스 중에 단어들이 역순 정렬 되어있는게 있기 때문인 것 같다. 퀵소트는 “평균적”으로 O(NlogN)이지만 “최악”의 경우(피벗 값을 최대값 순으로 또는 최소값 순으로 선택하는 경우)는 O(N^2)가 걸린다. 반면 머지소트는 최악이든 평균적이든 O(NlogN)를 유지한다. 입력의 최대 단어 갯수가 20000개니까 O(NlogN)의 경우는 약 300000번인 것에 비해 퀵소트는 최악의 경우 400000000번까지 단어를 비교할 수 있다.

퀵소트가 캐시 히트율이 좋아서 보통 가장 빠른 성능을 내는 것으로 알려져있는데, 최악의 경우까지 고려한다면 (피벗을 최악의 경우로 고를 확률은 굉장히 적지만) 무조건 이게 빠르다라고 말하긴 힘든 것이 사실이다. 회사에서 알고리즘 연수를 받을 때 교수가 “무조건 머지소트 쓰세요”라고 했었는데 이제서야 좀 알 것 같은 느낌이다. 교수는 당시에 속도 측면에서 보다는 “안정정렬”이라는 측면에서 머지소트를 쓰라고 한 것 같지만 말이다.

 

One thought on “백준 1181번 – 단어 정렬

댓글 남기기

이메일은 공개되지 않습니다. 필수 입력창은 * 로 표시되어 있습니다