[프로그래머스]롤케이크 자르기

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/132265

프로그래머스

코드를 작성하기 위한 순서는 다음과 같다.

1. 배열의 크기가 백만개이므로 런타임 에러를 막기 위해 튜플와 딕셔너리를 사용한다.

2. 우선 딕셔너리에 모든 topping 원소와 그에 해당하는 갯수를 넣어준다.

3. 딕셔너리에서 원소를 하나씩 빼면서 튜플에 넣어준다.

4. 딕셔너리의 key의 갯수와 튜플의 길이가 같다면 answer+=1을 해준다.

def solution(topping):
    answer = 0
    first=set() #1번
    second={}
    for i in topping: #2번
        if i not in second:
            second[i]=1
        else:
            second[i]+=1
    for i in topping:
        second[i]-=1 #3번
        if second[i]==0: #딕셔너리의 key 갯수로 중복 제거를 할 것이기 때문에 0이면 원소 자체를 삭제한다.
            del second[i]
        first.add(i)
        if len(first)==len(second.keys()): #4번
            answer+=1
    return answer

문제의 정확성 난이도는 어렵지 않았으나 효율성을 찾는데 시간을 많이 썼던 것 같다.

덕분에 튜플이라는 개념을 잘 알게 되었다.

해당 문제처럼 중복 제거를 여러 번 해야할 때는 리스트 내의 set함수보다 튜플을 우선적으로 사용해야 시간복잡도가 줄어들 것 같다.