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

문제보기

 

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

프로그래머스

 

 

 

풀이 및 코드

 

해당 문제는 예전에 풀다가 시간초과로 풀지 못했던 문제였다. 푸는 방법은 많지만 대부분의 방법은 시간초과가 날 것이다.

 

필자는 처음에 두개의 left, right array들을 구성해, 좌우에서 하나씩 추가하면서 left, right 어레이에 토핑의 종류들을 추가해가면서 비교했다. left =[], right = [], l=0, r= len(topping) 로 시작해 left의 개수와 right의 개수가 같다면 l += 1해주고 left > right라면 r-=1하는 식으로 빵을 구역을 정했고 이를 기반으로 문제를 해결하고자 했다. 하지만 시간초과가 발생했다. l, r의 값이 변할 때마다 새로운 토핑이 해당 left, right에 있는지 확인을 해야했고 매번 어레이의 크기만큼 시간이 소모되었기 때문에 시간 초과가 된것으로 예상된다. 따라서 필자는 다른 방식으로 접근했다. 

 

 

 

먼저 모든 빵을 오른쪽으로 모아두고 왼쪽에 빵을 추가하면서 topping의 개수를 구분했다. left, right라는 set을 만들어 토핑의 개수를 구분하고자 했다. 왼쪽에 빵을 추가할 때 기존 토핑 여부를 판단하는 것은 left안에 이미 토핑이 있는지만 보면 된다. 따라서 단순하게 left.add(topping)이라는 코드로 구현하였다. 하지만 right에서 topping을 제거하기 위해서는 그 이외에 또 사용되었느지를 확인해야 하는 과정이 필요했다. 이 과정에서의 시간 소모를 위해서 사전에 topping들 별로 개수를 세어 두었다. 따라서 왼쪽에 빵을 추가해줄 때마다 사전에 세어둔 곳에서 체크해 오른쪽에 해당 토핑이 몇개 남았는 지 알 수 있도록 하였다.