[Hackerrank] [Medium] Sherlock and the Valid String

https://www.hackerrank.com/challenges/sherlock-and-valid-string/problem

Sherlock and the Valid String | HackerRank

풀이

• 입력으로 string이 주어지고, 각 문자의 빈도 수가 같거나, 하나의 문자를 제거했을 때 빈도 수가 같으면 valid string으로 정의.
• 먼저 입력 string에 대해 frequency를 세고, 해당 정보를 dictionary에 저장.
• 그리고 frequency에 대한 빈도 수를 count_dict에 따로 저장.
  • 입력 string에 대해 각 문자가 같은 빈도 수로 나왔음 -> len(count_dict) == 1 -> return "YES"
  • 문자의 출연 빈도 수가 2개일 때 'YES' 조건은 2가지가 있음.
    • 일단 max_val, min_val은 문자 출현 frequency의 빈도 수이고, count_dict을 만들 때 계산됨.
    • 가장 많이 등장한 문자를 삭제할 경우, max_val - min_val은 1이 되야하고 count_dict[max_val] = 1이어야 함.
      • 'aabbbcc'의 count_dict = {2:2, 3:1} , b를 삭제하면 됨.
    • 가장 적게 등장한 문자를 삭제할 경우, count_dict[min_val] = 1이고 min_val = 1이면 됨.
      • 'abbcc'의 count_dict = {1:1, 2:2}, a를 삭제.

def isValid(s):
    from collections import defaultdict
    char_dict = defaultdict(int)
    max_val = 0
    min_val = 99
    # frequency 저장
    for char in s:
        # key : character, val : frequency
        char_dict[char] += 1
    cnt = 0
    count_dict = defaultdict(int)
    # frequency의 빈도 수를 count_dict에 저장.
    for v in char_dict.values():
        count_dict[v] += 1
        # max_val : frequency의 최댓값, min_val : frequency의 최솟값
        max_val = max(v, max_val)
        min_val = min(v, min_val)
    # 모든 문자가 같은 빈도 수로 입력받았을 경우
    if len(count_dict) == 1: return 'YES'

    if len(count_dict) == 2:
        # max_val을 삭제하는 경우
        if count_dict[max_val] == 1 and max_val - min_val == 1:
            return 'YES'
        # min_val을 삭제하는 경우
        elif count_dict[min_val] == 1 and min_val == 1:
            return 'YES'
    # 그 외의 경우 "NO"
    return "NO"