[파이썬]programmers: 롤케이크 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

---

초기구현

 

topping 전체를 돌며 왼쪽과 오른쪽을 나누어 매번 set형태의 값을 만들어주었다.

 

정확성은 맞지만.. 시간초과가 많이 되었음ㅠ (아마 매번 set을 만들어 해결하다 보니 그런듯 합니다)

def solution(topping):
    answer = 0
    end = len(topping)
    for i in range(len(topping)):
        left=set(topping[0:i])
        right = set(topping[i:end])
        print(left, right)
        if len(left) == len(right):
            answer +=1

    print(answer)
    return answer

---

solution

 

매번 set을 만드는게 많은 시간을 잡는다는걸 알게되었다.

 

그래서 기준점의 오른쪽과 왼쪽의 토핑가지수를 나눌 방법을 찾다가 고안해 낸 방법

 

전체를 딕셔너리로 변환한 뒤, 기준점을 옮기면서 빈 set배열에 값을 넣으며 토핑가지수가 일치한지 아닌지 확인하면 된다!

def solution(topping):
    answer = 0
    dic = dict()
    for i in range(len(topping)):
        if topping[i] not in dic:
            dic[topping[i]] = 1
        else:
            dic[topping[i]] +=1

    set_dic = set()
    for i in range(len(topping)):
        dic[topping[i]] -=1
        set_dic.add(topping[i])
        if dic[topping[i]] ==0:
            dic.pop(topping[i])
        if len(dic) == len(set_dic):
            answer +=1
    return answer