[Hackerrank] Sherlock and the Valid String

Sherlock and the Valid String

주어진 문자열이 "유효한 문자열(valid string)"인지 판단하는 문제입니다. 문자열이 유효하려면 다음 두 조건 중 하나를 만족해야 합니다:

1. 모든 문자의 등장 빈도가 동일해야 한다.
2. 문자 하나를 제거했을 때 나머지 문자의 등장 빈도가 동일해야 한다.

입력

• 영어 소문자로 구성된 문자열 sss (1 ≤ |s| ≤ 10⁵)

출력

• 문자열이 유효하면 "YES", 유효하지 않으면 "NO"를 출력한다.

예제 입력 및 출력

1. 입력: "aabbcc"
   출력: "YES"
   설명: 모든 문자가 2번씩 등장하므로 유효함.
2. 입력: "aabbc"
   출력: "YES"
   설명: 문자 c를 하나 제거하면 "aabb"가 되어 모든 문자의 빈도가 동일함.
3. 입력: "aabbcd"
   출력: "NO"
   설명: 한 문자를 제거해도 모든 문자의 빈도를 같게 만들 수 없음.

문제가 카운터를 이용하면 쉬울 거라고 생각했지만 예상외로 시간이 걸렸다.

먼저 counter를 import 해주고, 

from collections import Counter

다음으로 카운터에 문자열을 넣어줘서 수를 세었다. 그 후에 카운터의 value들을 다시 카운터에 넣어 주었다.

tmp = Counter(s)
value_count = Counter(tmp.values())

예를 들어서 입력이 aabbcd면, Counter({2: 2, 1: 2}) 이런 결과가 나온다. 즉 2번 나온 문자가 2개, 1번 나온 문자열이 2개라는 소리다. 여기서 만약 value_count의 길이가 3 이상, 즉 문자열의 빈도가 3개 이상이면 하나를 제거하는 것으로 절대 정답을 만족할 수 없다. 그러므로 NO를 return하고, 마찬가지로 value_count의 길이가 1이면 문자를 제거하지 않아도 정답을 만족하니 바로 YES를 return한다.

그러면 이제 문자를 하나 제거하는 것으로 정답 조건을 만족할 때를 확인해보자.

일단 value_count에는 무조건 값이 2개다. 만약 작은 빈도가 1이고, 해당 빈도가 1이라면 제거함으로서 정답이 가능하다. 예를들어서 aabbc라면 value_count는 2: 2, 1:1 이라는 결과가 나오고, c를 제거하면 정답이다.

그리고 큰 빈도가 작은 빈도보다 1크고 그 빈도가 1이라면 제거하면 정답이 된다. 예를 들어서 aaabbccdd라면 value_count는 3: 1, 2:3이고, a를 제거하면 정답이다. 이를 코드로 나타내면 다음과 같다.

def isValid(s):
    tmp = Counter(s)
    value_count = Counter(tmp.values())
    print(value_count)
    if len(value_count) > 2:
        return "NO"
    elif len(value_count) == 1 or len(value_count) == 0:
        return "YES"
    else:
        x = list(value_count.keys())
        if x[0] > x[1]:
            a = x[0]
            b = x[1]
        else:
            b = x[0]
            a = x[1]
        if (a - b) == 1 and value_count[a] == 1:
            return "YES"
        elif value_count[b] == 1:
            return "YES"
        else:
            return "NO"

정답 처리가 되었지만, 코드가 너무 더러워서 코드를 좀더 깔끔하게 만들어 주었다.

from collections import Counter

def isValid(s):
    freq = Counter(s)  # 각 문자의 등장 빈도
    freq_count = Counter(freq.values())  # 등장 빈도의 빈도

    if len(freq_count) == 1:
        return "YES"  # 모든 문자의 등장 빈도가 동일
    elif len(freq_count) == 2:
        (freq1, count1), (freq2, count2) = sorted(freq_count.items())
        
        # 1. 작은 빈도가 1이고, 해당 빈도가 1이면 제거 가능 (ex. aabbc → c 제거)
        if freq1 == 1 and count1 == 1:
            return "YES"
        # 2. 큰 빈도가 작은 빈도보다 1 크고, 그 빈도가 1개면 제거 가능 (ex. aaabbccdd → a 제거)
        if freq2 - freq1 == 1 and count2 == 1:
            return "YES"

    return "NO"