[HackerRank][Python3] Happy Ladybugs

Problem :

https://www.hackerrank.com/challenges/happy-ladybugs/problem

My Solution :

#!/usr/bin/env python3


def happy_lady_bugs(b):
    index_dic = {}
    for i, char in enumerate(b):
        index_dic.setdefault(char, []).append(i)
    count_set = {len(v) for k, v in index_dic.items() if k != '_'}
    if 1 in count_set:
        return 'NO'
    if '_' not in index_dic:
        for indexes in index_dic.values():
            if indexes[0] + len(indexes) - 1 != indexes[-1]:
                return 'NO'
    return 'YES'


g = int(input())
for _ in range(g):
    n = int(input())
    b = input()
    result = happy_lady_bugs(b)
    print(result)

Comment :

우선 처음에는 위와 같이 접근하였다. 각 문자열의 index를 list에 저장해놓고, 만약 '_'를 제외하고 list의 길이가 1인 경우가 존재하면 탈락. 그리고 '_'가 존재하지 않는 경우는 각 list에 존재하는 index들이 1씩 증가하지 않으면 탈락.

그런데 위 방법은 결국 두번의 for문과 set()을 만드는 과정이 있어 시간 복잡도상 비 효율적이다. 따라서 아래와 같이 1회만 순회하는 방식으로 바꾸었다. 대신 실패하는 조건을 만드는 flag를 활용하였다. 코드는 길어졌지만 시간 복잡도는 개선되었다.

My Solution2 :

#!/usr/bin/env python3


def happy_lady_bugs(b):
    last_index = {chr(x): -1 for x in range(65, 91)}
    empty_need = False
    empty_exist = False
    singles = set()
    for i, char in enumerate(b):
        if char != '_':
            if last_index[char] == -1:
                singles.add(char)
            else:
                if char in singles:
                    singles.remove(char)
                if not empty_need and i - last_index[char] != 1:
                    empty_need = True
            last_index[char] = i
        else:
            empty_exist = True
    if singles:
        return 'NO'
    if empty_need and not empty_exist:
        return 'NO'
    return 'YES'


g = int(input())
for _ in range(g):
    n = int(input())
    b = input()
    result = happy_lady_bugs(b)
    print(result)