Sherlock and valid string

생각한 것

YES의 조건이 "단 하나의 알파벳의 개수가 다른 알파벳보다 1개 많고, 다른 알파벳들의 개수를 모두 같을 것"이라고 생각했고, a-z를 나타내는 배열을 만들어 순차적으로 유일성을 체크해주는 로직을 생각했다. 그런데 예를 들어 aabbbcdd 라는 문자열이 있다면 배열로 나타냈을때 [2, 1, 3, 2...]로 표현할 수 있는데, 불가능을 구별하기 위해 2를 기준으로 잡고 순차적으로 체크했을때 1은 넘어가고 3은 안되고... 그런 많은 조건들이 필요해졌기 때문에 이 방법은 아니라고 생각했다.

다른 생각

앞에서 O(n) 시간 안에 할 수 있을거라는 생각에 미련을 버리지 못했었는데.. 정렬을 하면 정말 간단하게 체크할 수 있다. 빈도수 별로 정렬을 하고 각 요소들의 개수와 크기를 비교하면 된다.

한가지 놓쳤던 것은, 앞서 생각했던 "단 하나의 요소의 개수가 다른 요소보다 1개 많다" 라는 조건 이외에도 "단 하나의 요소가 딱 1개 밖에 없고 나머지는 같은 개수다"라는 조건에서도 YES가 될 수 있다. 이걸 놓쳐서 몇개의 테스트 케이스를 통과하지 못했었다.

결말

결국 Θ(nlogn) 시간에 해결이 되었다(자바의 Arrays.sort가 퀵정렬을 하기 때문에). 생각보다 쉽게 해결할 수 있었던 문제였는데 표기된 medium이라는 레벨이 압박을 준걸까... 좀 더 유연하게.. 유연하게...