[문제후기] leetcode-1647

이 문제는 214 주간 대회의 2번째 문제이다.

문제의 요구사항

문제의 요구사항은 그다지 좋은 편이 아니고, 설명도 친절하지 않다. 하지만 문제를 푸는 과정에서 필요한 아이디어는 매우 참신한 착안이 필요한 편이다. 하나의 문자열에 있는 알파벳 문자 별로 나타나는 회수 중 같은 회수가 없도록 제거해야 한다. 이때 제거해야하는 문자 수를 최소화 하는 회수를 출력하는 문제이다.

1647. Minimum Deletions to Make Character Frequencies Unique A string s is called good if there are no two different characters in s that have the same frequency. Given a string s, return the minimum number of characters you need to delete to make s good. The frequency of a character in a string is the number of times it appears in the string. For example, in the string "aab", the frequency of 'a' is 2, while the frequency of 'b' is 1.

 

예제 설명

먼저 문제에서 주는 2번째 예를 보면...s = "aaabbbcc" 즉 a 가 3회, b도 3회 그리고 c가 2회의 빈도수(frequency)로 나온다. 이 경우 a 나 b 중 하나는 2개를 제거해야만 한다. 즉 (a 를 2개 제거한다고 할 때) 각각 a : 1, c : 2, b : 3 개가 되어, 더 이상 같은 횟수를 가진 알파벳이 존재하지 않게 된다.

조금 더 복잡해 보이는 예를 들어보자.

s ="ceaxxyyzzttttssss"

이 경우는 {'t': 4, 's': 4, 'x': 2, 'y': 2, 'z': 2, 'c': 1, 'e': 1, 'a': 1} 이고 t 나 s 가 각각 4개 이므로 이 중 하나는 3개가 되도록 조정할 수 있다. 마찬가지로 각각 2개씩 있는 x,y,z 과 1개씩 있는 a,c,e  역시 조정을 해야한다. 이 문제의 해답을 자세하게 말로 설명하는 것은 별로 도움이 되지 않는다고 생각한다.

하지만 기본적인 아이디어는 일단 리스트에 가장 큰 빈도수가 나온 역순으로 배열을 하는 것이다.

N = [0, 3, 3, 0, 2] 

여기에서 리스트 N[4] (즉 N의 4번째 인자 값)이 2 라는 것은 4개의 빈도수를 가진 알파벳이 2개 (t와 s)라는 뜻이다. 그리고 1번째와 2번째 인자 값이 N[1] = 3,  N[2] = 3라는 것은 각각 a,c,e 가 하나씩, 그리고 x,y,z가 2개씩 있다는 의미이다.

그리고 이 리스트 값이 최종적으로 N = [0, 1, 1, 1, 1] 이 되도록 조정을 하면서 경우 수를 헤아리면, 원하는 최소한의 회수를 구할 수 있다.

 

한 일본인 코드의 예

(이렇게 말은 했지만, 이 글만 읽고 내가 말한 의도를 이해할 수 있으리라 기대하지 않는다.) 단지 아래 코드를 보면, 우측이 내가 급하게 짜고 나서.. 제출을 해서 통과를 한 코드이다. (솔직하게 말하면 짜고 통과를 하면서도 내가 만든 코드의 지저분함에 불만이 많았다.) 

하지만, 좌측의 아래 부분이 똑 같은 로직이지만 최적화된 코드이다. 이 코드는 일본인 Loxis 라는 친구가 짠 코드를 조금 보완한 것인데, 처음에는 어떤 의도인지 몰랐다가 ... 30분 가량 디버깅을 하며 분석을 하고 나서 감탄을 했다.

마치 바둑에서 묘수 풀이와 같이, 똑 같은 문제 해결을 하는 방식도 "이렇게 아름다울 수 있구나" 하는 생각과, 특히 50번 라인에 wait = max(0, wait -1) 부분은 wait 라고 이름 붙은 변수가 살아 있는 듯한 느낌마저 받았다.

아마도 이런 문제의 해결 방식은 정식으로 알고리듬 교과서에 나오지는 않지만, 수 없는 코딩 대회에서 자주 반복하는 방식에 대한 일본인 특유의 정리를 잘 해두는 결과라고 생각한다. 실제로 전혀 경험이 없는 사람이 문제 해결 당시에 10 분 이내로 좌측에 있는 이런 문제 해결 방식으로 풀었다는 것은 믿기가 힘들다.

각종 코딩 대회에서 절대 다수가 중국인들이 많은 상황에서, 일본인들은 많이 출전하지는 않지만 대다수가 상위권에 진입하는 것 역시 눈 여겨 볼 만한 상황이다.

 

[leetcode] 원 문제

leetcode.com/contest/weekly-contest-214/problems/minimum-deletions-to-make-character-frequencies-unique/

[]