[알고리즘] 프로그래머스 롤케이크 자르기 - Python

문제 : 프로그래머스 롤케이크 자르기 문제

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

프로그래머스

 

이 문제는 중복을 포함하지 않고 배열에서 요소를 세는 것이 가장 중요하다고 생각했다. 중복 제거를 위해서는 set을 이용하도록 했다. 가장 단순하게 구현한 코드는 다음과 같다.

 

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

  

이 코드에서는 슬라이싱을 직접 해가면서 각 케이크에 있는 중복 제거 토핑 개수를 비교하는 방법이다. 문제점은 매 반복마다 topping을 슬라이싱하고 그걸 set으로 지정한다는 것이다. 따라서 시간 복잡도는 슬라이싱에 O(n), set에서 O(n)이 발생하므로 O(n²)이 된다. 따라서 이 방법 대신 dictionary를 활용할 방법을 생각해보았다. 

 

def solution(topping):
    answer = 0
    dict={}
    for i in topping:
        if i in dict:
            dict[i]+=1
        else:
            dict[i]=1
    temp=set()
    for i in range(len(topping)):
        temp.add(topping[i])
        dict[topping[i]]-=1
        if dict[topping[i]]==0: del dict[topping[i]]
        if len(dict)==len(temp):
            answer+=1
    return answer

 

dictionary인 dict를 선언해주고 그 안에 전체 topping의 개수를 넣는다. 그리고 temp라는 set을 두어 슬라이싱을 해가면서 왼쪽 케이크의 토핑 중 중복을 제거한 토핑 집합을 유지한다. 그리고 오른쪽으로 인덱스 i를 옮겨 가며 dict에서 해당 토핑 개수를 1 빼준다. 만약 dict에서 해당 요소가 0이 되면 그 요소를 제거해준다. 

 

이 경우의 시간 복잡도를 생각해보면 topping을 dict에 넣는 과정에서 dictionary에서 in, 조회, 삽입 모두 O(1)이므로 첫번째 반복문의 시간복잡도는 O(1)이다. 두번째 반복문에서는 set에 add, dict의 삭제 모두 O(1)이기 때문에 n회 반복에서는 시간 복잡도 O(n)이다. 따라서 최종적으로는 O(n)을 만족한다. 

 

마지막으로 이 문제를 풀며 파이썬 문법 중 헷갈리는 것을 정리해보았다.

• set 삭제 : s.remove(a)
• dictionary 삭제 : del dict['a']