Happy Ladybugs

https://www.hackerrank.com/challenges/happy-ladybugs/problem?isFullScreen=true

Happy Ladybugs | HackerRank

 

나의 코드

#!/bin/python3

import math
import os
import random
import re
import sys

def happyLadybugs(b):
    if (len(b)==1) and (b!='_'):
        return 'NO'
    
    b_dict = {}
    for i in b:
        if i not in b_dict:
            b_dict[i] = 1
        else:
            b_dict[i] += 1
    if '_' in b_dict:
        for k,v in b_dict.items():
            if k != '_':
                if v==1:
                    return 'NO'
    else:
        for b_v in range(len(b)):
            if (b_v == 0) and (b[b_v] != b[b_v+1]):
                return 'NO'
            elif (b_v == len(b)-1) and (b[b_v] != b[b_v-1]):
                return 'NO'
            else:
                if (b[b_v] != b[b_v-1]) and (b[b_v] != b[b_v+1]):
                    return 'NO'
       
    return 'YES'

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')
    g = int(input().strip())
    for g_itr in range(g):
        n = int(input().strip())
        b = input()
        result = happyLadybugs(b)
        fptr.write(result + '\n')
    fptr.close()

 

시간 복잡도

for i in b : b를 순회하며 b_dict 생성 ( 선형 시간 복잡도 )
for k,v in b_dict.items() : b_dict를 순회하며 Happy Ladybugs을 만들수 없는 경우 필터 ( 선형 시간 복잡도 ) 
for b_v in range(len(b)) : b을 순회하며 Happy Ladybugs을 만들수 없는 경우 필터 ( 선형 시간 복잡도 ) 
해당 알고리즘 시간복잡도는 선형 시간 복잡도 ( O(n) )