프로그래머스 - 롤케이크자르기 (파이썬)

1. set 이용(x)

topping배열을 두조각으로 나누기 위해 set1, set2를 만들었다.

topping을 앞에서부터 돌면서 topping[i]번째 값 전까지 set1에 넣고 topping[i]번째부터 배열 끝까지의 값을 set2에 넣어 set1과 set2의 값을 비교했다. 반복문을 돌때마다 set을 만들어야 해서 시간초과가 발생했다.

def solution(topping):
    answer = 0
    for i in range(1,len(topping)):
        set1=set(topping[:i])
        set2=set(topping[i:])
        if len(set1)==len(set2):
            answer+=1
    return answer

 

2. 딕셔너리 이용

dic1, dic2를 만들어 topping의 모든 토핑 값을 key로 토핑의 개수를 value로 dic2에 넣어주었다. 그 다음 for문을 돌면서 topping의 i번째 값을 dic2에서 빼서 dic1으로 옮겨주었다. dic2에서 해당 토핑의 개수가 1개밖에 안남았으면 해당 토핑 key는 pop을 해주었다.(해당 토핑이 dic1으로 간 순간 dic2의 해당 토핑은 0개가 되므로) 각 딕셔너리의 키 개수를 비교해서 동일하면 answer을 한개 증가시켰다.

 

def solution(topping):
    answer = 0
    dic1={}
    dic2={}
    for topping_val in topping:
        if topping_val in dic2:
            dic2[topping_val]+=1
        else:
            dic2[topping_val]=1
    for topping_val in topping:
        if dic2[topping_val]>1:
            dic2[topping_val]-=1
        else:
            dic2.pop(topping_val)
        if topping_val in dic1:
            dic1[topping_val]+=1
        else:
            dic1[topping_val]=1
        if len(dic1.keys())==len(dic2.keys()):
            answer+=1
    return answer