2018 KAKAO BLIND RECRUITMENT [3차] 자동완성 (Swift)

이 문제에서 가장 중요하며, 가장 판단하기 어려운 것이 "사전순 정렬"하는 것 이라고 생각한다.

이 문제를 처음 봤을 때, 가장 먼저 떠오른 풀이방법중에 "사전순 정렬하기"가 포함되어있었다면, 당신은 알고리즘 실력자라고 생각한다.

 

순차적으로 접근해보자.

우리는 각 단어들에 대하여, "본인이 distinct해지는 최소 index를 찾아야한다" 

즉, 여기까지 치면 무조건 "나"를 지칭하는거야! 라고 판단할 수 있는 위치(index)를 찾아야하는 것이다.

 

처음 마주치면, 각 단어들에 대하여 "다른 모든 단어"들과 비교하여 distinct해지는 위치를 찾아야 할 것만 같은 생각이 들기 쉽다.

 

하지만, 우리는 이 단어들을 '내림차순' 혹은 '오름차순'으로 정렬한다면 양 옆에 붙어있는 단어들과 겹치는 부분만 체크하여 자신이 전체에서 distinct해지는 index를 알아낼 수 있다.

 

이 생각을 하고나서도, 가시적으로 이를 증명하라고 하면, 설명 방법을 생각해내는데 시간이 좀 걸릴 것 같았고, 실제로 그랬다.

 

가설을 세우고, 이 가설이 맞는지 확인을 하는 식으로 증명을 할 것이다.

가설: "자신과 다른 단어가 '겹치는 부분의 길이'는, 사전순 정렬 후 앞뒤 단어와 비교하여 구한 것이 다른 단어와 비교해 구한 것보다 작을 수 없다"

=> 이게 참이라면,

"각 단어가 전체집합에서 Distinct해지는 index는, 자신의 앞뒤 단어와 비교하여 본인이 distinct해지는 index와 동일하다"

이 가설도 참이 된다.

 

ab

abb

abce

abcf

 

위의 예시에서, abcf와 abce가 겹치는 부분은 3개이다.

abcf와 abb가 겹치는 부분은 2개이다.

만약 abcf와 겹치는 부분의 길이에 관하여, abb가 abce보다  높은 값을 가지려면 3번째 자리가 c로 변경되어야하고, abc가 될 것이다.

여기서 또 한자리 더 겹치고싶다면, abcf가 되어야하는데, 

그렇게 될 경우 abb( => abcf)와 abce가 순서가 바뀌어야한다.

즉, 어떤 단어가 다른 단어와 겹치는 부분의 길이는, 해당 단어와 가까울수록 더 크거나 같다 (작지 않다)

 

따라서 이 문제는,

1. 주어진 Words배열을 사전순으로 정렬하고,

2. 각 단어들에 대하여 앞뒤 단어들과 비교하여 본인이 다른 단어와 겹치는 부분의 "최댓값" ( equals  자신이 앞뒤 단어와 distinct해지기 위한 "최소 index")를 구해 배열에 저장한다.

3. 배열의 모든 값을 더해 출력한다

끝