[programmers lv2.python] 롤케이크 자르기 풀이

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

프로그래머스

문제 

 

1차 풀이 (완전 탐색) 👉 실패

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

 

오.. 머야 꽤나 쉬운데? 하면서 호기롭게 완전 탐색으로 풀어본 풀이.

for문으로 순회하면서, 슬라이싱으로 리스트를 잘라준 다음 set 에 넣어서 중복을 없앤 후 len 으로 길이를 측정해 비교해 주는 풀이다.

 

테스트 두 개를 쉽게 통과하기에 바로 제출을 눌렀더니 .. ㅋㅋ 

시간 초과 ending

 

그렇다 .. 문제의 제한 사항 리스트의 길이 '백만개' 를 못 봄

 

이 코드의 경우 생각해보면 시간 복잡도가 O(n^2)이다.  for문을 순회하면서 각 위치에서 서브 리스트를 매번 생성하고, 해당 서브 리스트의 요소를 반복해서 set을 하면? 리스트의 길이에 대해 이중 반복문을 사용하게 되는 셈이기 때문.

즉 토핑 리스트의 길이가 커질 수록 무조건 불리한 풀이다.

 

2차 풀이 (Counter 객체 사용) 👉 성공

무조건 1차 풀이에서 시간 복잡도를 줄일 수 있는 방법이 없을까.. 하다가 모든 가능한 분할을 시도하는 방식 말고, 그냥 각 위치에서의 토핑을  오른쪽에 하나씩 추가하고 왼쪽에서 제거하면서 공평한 분할을 찾아보는 방식으로 해보기로 했다.

 

그래서 리스트 같은 iterable 객체 요소의 갯수를 세주는 collections의 Counter 객체를 쓰기로 당첨!

from collections import Counter

def solution(topping):
    answer = 0
    # 우선 왼쪽이 모든 토핑을 갖고 있음
    left = Counter(topping)
    # 오른쪽은 아직 토핑이 없음
    right = {}
    
    # 순회하면서 오른쪽한테 하나씩 토핑을 나눠줌
    for i in range(len(topping)):
        if topping[i] in right:
            right[topping[i]] += 1
        else:
            right[topping[i]] = 1
            
        left[topping[i]] -= 1
        
        # 왼쪽에 해당 토핑이 없으면 왼쪽 Counter에서 토핑 제거
        if not left[topping[i]]:
            del(left[topping[i]])
        
        # 왼쪽이 가진 토핑 갯수 == 오른쪽이 가진 토핑 갯수가 같으면 1 더함
        if len(left) == len(right):
            answer += 1
    return answer

주석에 붙여 둔 설명 대로, 우선 왼쪽이 모든 토핑을 다 가지고 있다고 가정하고, 왼쪽의 전체 토핑 갯수에서 하나씩 빼서 오른쪽으로 옮겨준다.

그 이후 각자가 가진 토핑 갯수가 같으면 답을 + 1 씩 갱신해준다.

 

이 코드의 경우 한 번의 반복으로 리스트를 탐색하고, 각 위치에서의 토핑을 왼쪽에서 제거하고 오른쪽에 추가하는 로직이기 때문에 시간 복잡도는 O(n)이 된다. (리스트의 길이 n에 선형적으로 비례)

 

 

통과 완료 🥹

---

 

++ 파이썬 내장 클래스 collections의 Counter 객체

from collections import Counter

# 리스트의 요소 개수 세기
my_list = ['a', 'b', 'c', 'a', 'b', 'a']
counter_list = Counter(my_list)
print(counter_list)  # Counter({'a': 3, 'b': 2, 'c': 1})

# 문자열의 문자 개수 세기
my_string = 'hello'
counter_string = Counter(my_string)
print(counter_string)  # Counter({'l': 2, 'h': 1, 'e': 1, 'o': 1})

 

---

마치며

풀기 전에 제한사항을 잘 보자(^^), 또 시간 복잡도를 비교해보면서 문제를 풀자.