사전 순으로 단어 정렬하기

문제 : 사전순으로 단어를 생성하여 N 번째 올 단어를 찾아라

● 특정 문자열이 주어지고 이 문자열 안에 포함된 단어들을 사전순으로 정렬하라. 그리고 주어진 N 번째 오는 단어가 무엇인지 구하라.

단, 문자열의 최대 길이는 1,000 이고, 모두 소문자 알파벳으로만 되어 있다.

중복되는 단어는 한 단어로 생각한다. 

시간제한이 있다. (빠를 수록 점수가 높다, 1초가 넘으면 실패)

● 사전순이란 것은 알파벳 a ~ z 까지 단어를 정렬하는 것을 의미한다. 

● 예를 들어, melon 이란 문자열이 주어졌을 때, 7번째 오는 단어를 구하라. 

melon 안에 포함된 단어를 사전순으로 정렬하면 다음과 같다. 

1 : e

2 : el

3 : elo

4 : elon

5 : l

6 : lo

7 : lon

8 : m

9 : me

10 : mel

11 : melo

12 : melon

13 : n

14 : o

15 : on

즉, 답은 lon 이 된다. 

일반적인 풀이

● 풀이방법 1 : 위 문제와 같이 알파벳 a부터 문자열 안에 단어를 찾고, 그 뒤로 한글자씩 붙여서 단어를 만들어 나간다.

    

○ 문제점 :  주어진 문자열이 최대 1,000으로 길기 때문에 a가 몇번이고 반복될 수 있다. 예를 들어, a 부터 시작할 경우, 문자열 내의 모든 a 의 위치들을 기록하고, 그 뒤에 오는 단어들을 비교해서 순서를 만들어 나가야 한다. a가 세 번 반복된 경우, 각각의 단어의 뒷글자를 확인해서 순서를 정해야 한다. 위 문제의 예제와 같은 경우는 e가 한 번만 나오지만, e가 계속 반복되는 경우, 또 비슷한 알파벳이 많아지는 경우 문제가 복잡해진다. 

● 풀이방법 2 : 문자열의 첫글자부터 문자열을 만들어 나가면서 이 문자열을 이진 트리 형태로 저장하여 빠르게 정렬한다. 이를 통해 n 번째 아이템을 빨리 찾을 수 있다. 풀이방법 1의 반복적인 검색을 생략할 수 있다.

○ 문제점 : 모든 문자열을 다 만들어보아야 해서 메모리 문제가 있을 수 있다. C++이나 Java로 문제를 푸는 경우는 메모리 이슈를 피할 수 있지만 <STDIO.H> 만 허용된 C언어에서는 어려움이 있다. 트릭을 통해 malloc과 유사하게 푼다 하여도 속도 이슈가 발생할 수 있다. 실제로 C++로 이 문제를 푼 경우 제한 시간에 걸렸다. 

답이 되는 풀이

● 생각의 전환이 필요하다. 문자열로부터 시작하는 것이 아니라 사전 으로 부터 시작한다. 즉, a가 있는지 검색하고 있으면 다시 aa가 있는지 검색한다. 이 때, 문자열 전체를 보는 것이 아니라 a를 찾은 위치에서 그 바로 뒤에 문자와만 비교하면 된다. a를 찾은 위치의 인덱스를 활용한다. 

● 예를 들어, 주어진 문자열이 kdaabdgga 일 때, 

1) 우선 a 를 찾는다. 인덱스가 2에 a가 있음을 발견한다. 

2) 인덱스 2부터 aa가 있는지 확인한다. 인덱스 2에 aa가 있다.

3) 인덱스 2부터 aaa가 있는지 확인한다. 인덱스 2에는  aaa는 없다

3-1) 문자열 전체에서 aaa가 있는지 확인한다. aaa는 없다. 

4) 인덱스 2부터 aab가 있는지 확인한다. aab는 있다. 

5) 인덱스 2부터 aaba가 있는지 확인한다. 인덱스 2에는 aaba가 없다. 

5-1) 문자열 전체에서 aaba가 있는지 확인한다. aaba가 없다. 

6) aabc, aabd 등을 동일하게 확인한다. 

● 이 방식은 풀이방법 1과 비교할 때, 검색 횟수가 현저하게 줄어든다. 문자열이 랜덤하게 만들어진다는 가정하에 a는 여러번 나오겠지만, aa는 그 숫자가 적어질 것이고, aaa는 훨씬 적을 것이기 때문이다. 

최상의 풀이

● 답이 되는 풀이도 속도 문제는 있다. aaa가 있는지 확인을 첫번째 a의 인덱스 뒤로는 다 해야 하기 때문이다. 즉, 예를 들어, 주어진 문자열이 aac로 시가된다면, aab 가 있는지 aad가 있는지 문자열 전체를 검사하는 작업을 계속 반복하게 된다. 

● 이 검색 시간을 줄이기 위해서 각 알파벳에 대한 해시를 만들어 놓으면 검색 시간을 대폭 단축시킬 수 있다. 헤시 인덱스를 한단어로 만들어도 되고 두 단어로 만들어도 된다. 두 단어 이상으로 만들면 오히려 효율이 떨어질 것으로 예상된다. 주어진 문자열이 일정길이 이상일 때만 헤시 테이블을 만드는 작업을 수행하는 식으로 프로그램을 완성하면 효율적인 검색이 가능하다. 

● 헤시테이블은 간단한 이중배열로 만들 수 있다. int hash[26][10] 정도로 만들어서, 각각의 알파벳의 10번째 나오는데까지 위치만 미리 기억해놔도 문제가 쉬워진다. 워스트케이시를 대응하기 위해서는 int hash[26][1000] 이 되어야 하는데 이는 메모리 낭비가 심하다.  또는 int hash2[26*26][10] 으로 만들수도 있는데 - (aa ~ zz) 이 경우 해시를 만드는데는 시간이 더 걸리겠지만, 검색 속도는 월등히 빨라질 수 있다. 

예제 코드

● 추후 업데이트할 예정이다.