귀걸이

1380번: 귀걸이

 

나의 풀이

import sys

def _gigori(n, sinari):
    std_dict = {i+1 : sys.stdin.readline().rstrip() for i in range(n)}
    gori_ck = {}
    for _ in range((2*n)-1):
        n_num, n_type = sys.stdin.readline().rstrip().split()
        n_num = int(n_num)
        if (n_num in gori_ck):
            gori_ck.pop(n_num)
        else:
            gori_ck[n_num] = n_type
    return f"{sinari} {std_dict[list(gori_ck.keys())[0]]}"
    
sinari = 0
while True:
    n = int(sys.stdin.readline())
    if (n == 0):
        break
    sinari += 1
    print(_gigori(n, sinari))

 

시간 복잡도

print(_gigori(n, sinari)) : 시나리오 만큼 해당 함수 반복 ( 선형 시간 복잡도 )
    _gigori 함수 내부 루프 ( 선형 시간 복잡도 )
해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n**2) )