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

문제

---

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

프로그래머스

• 소요 시간 : 30분
• 난이도 : LV 2

나의 풀이

---

1차 시도

접근 방법

1. 완전탐색으로 모든 인덱스일 때 2개로 슬라이싱한다.

2. set으로 토핑의 종류 개수를 세서 비교한다. 

 

시간복잡도

O(N^2)

Python list slicing : O(N)

https://school.programmers.co.kr/questions/42508

프로그래머스

 

코드

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

 

결과 : 시간초과

 

---

2차 시도

접근 방법

1. 철수에게 모든 토핑을 다 주고, 동생에게 1개씩 준다. 

2. 철수가 모든 토핑을 가졌을 때, 각 토핑마다 개수를 dict 형태로 저장한다.

3. 철수의 토핑 개수를 센다. 

4. 동생도 마찬가지로 토핑 개수(=0)와 토핑마다 개수를 저장할 dict를 초기화한다. 

5. 토핑을 하나씩 pop하면서, 철수가 1개를 가질때까지 동생에게 넘겨준다.

5-1. 철수 토핑 dict에서 1개를 빼고 동생 토핑 dict는 1개를 더한다.

5-2. 해당 토핑이 철수는 0개를 가지고 있으면 이제 가지고 있지 않으므로 철수 토핑 개수에서 1를 뺀다.

5-3. 해당 토핑이 동생은 1개를 가지고 있으면 새로 생긴 토핑이므로 동생 토핑 개수에서 1를 더한다. 

5-4. 철수 토핑 개수와 동생 토핑 개수를 비교하여 같으면 정답에 1을 더한다. 

시간복잡도

O(N)

코드

from collections import Counter, defaultdict 

def solution(topping):
    answer = 0
    
    # 철수가 처음에 다 가지고 있을 때, 토핑 개수 세기 
    cheulsoo =  Counter(topping)
    
    # 동생 토핑 개수 
    brother = defaultdict(int)
    
    # 철수 토핑 개수
    cheulsoo_topping, brother_topping = len(cheulsoo), 0
    
    # 백만 
    while len(topping) > 1:
        t = topping.pop()
        
        # 철수 -> 동생에게 토핑 주기 
        cheulsoo[t] -= 1
        brother[t] += 1

        # 철수 map[토핑] = 0이면 철수 토핑 개수 -1 
        if cheulsoo[t] == 0:
            cheulsoo_topping -= 1
        
        # 동생 map[토핑]이면 동생 토핑 개수 +1 
        if brother[t] == 1:
            brother_topping += 1
            
        # 토핑 비교 
        if cheulsoo_topping == brother_topping:
            answer += 1
            
    return answer

 

결과 : 정답

테스트 1 〉	통과 (5.89ms, 10.6MB)
테스트 2 〉	통과 (96.36ms, 14.5MB)
테스트 3 〉	통과 (57.47ms, 10.8MB)
테스트 4 〉	통과 (71.45ms, 10.8MB)
테스트 5 〉	통과 (662.21ms, 18.5MB)
테스트 6 〉	통과 (707.41ms, 51.3MB)
테스트 7 〉	통과 (703.73ms, 51.4MB)
테스트 8 〉	통과 (680.31ms, 51.2MB)
테스트 9 〉	통과 (855.20ms, 50.5MB)
테스트 10 〉	통과 (731.42ms, 50.4MB)
테스트 11 〉	통과 (71.84ms, 10.8MB)
테스트 12 〉	통과 (10.47ms, 11.1MB)
테스트 13 〉	통과 (879.86ms, 50.6MB)
테스트 14 〉	통과 (1065.65ms, 50.6MB)
테스트 15 〉	통과 (829.97ms, 50.5MB)
테스트 16 〉	통과 (770.49ms, 50.5MB)
테스트 17 〉	통과 (657.86ms, 50.6MB)
테스트 18 〉	통과 (660.68ms, 51.3MB)
테스트 19 〉	통과 (635.97ms, 51.3MB)
테스트 20 〉	통과 (677.97ms, 51.4MB)

---

다른 사람의 풀이

---

접근 방법

위와 비슷하나 조금 차이가 있다.

1. 동생의 토핑 종류를 set으로 관리한다. 

2. 철수의 dict에서 해당 토핑 개수가 0이면 Pop을 한다.

3. dict의 길이와 set의 길이를 비교한다. 

시간복잡도

O(N)

코드

from collections import Counter

def solution(topping):
    answer = 0
    dic = Counter(topping)
    set_dic = set()
    answer = 0

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

    return answer

 

결과 : 정답

테스트 1 〉	통과 (9.56ms, 10.3MB)
테스트 2 〉	통과 (65.89ms, 14.8MB)
테스트 3 〉	통과 (70.27ms, 10.9MB)
테스트 4 〉	통과 (66.62ms, 10.9MB)
테스트 5 〉	통과 (685.01ms, 18.6MB)
테스트 6 〉	통과 (925.79ms, 51.3MB)
테스트 7 〉	통과 (852.37ms, 51.2MB)
테스트 8 〉	통과 (922.38ms, 51.4MB)
테스트 9 〉	통과 (689.49ms, 50.5MB)
테스트 10 〉	통과 (715.50ms, 50.6MB)
테스트 11 〉	통과 (78.76ms, 10.8MB)
테스트 12 〉	통과 (10.88ms, 11.5MB)
테스트 13 〉	통과 (736.44ms, 50.5MB)
테스트 14 〉	통과 (663.44ms, 50.6MB)
테스트 15 〉	통과 (658.01ms, 50.5MB)
테스트 16 〉	통과 (616.20ms, 50.6MB)
테스트 17 〉	통과 (575.67ms, 50.5MB)
테스트 18 〉	통과 (599.56ms, 51.4MB)
테스트 19 〉	통과 (581.86ms, 51.4MB)
테스트 20 〉	통과 (549.11ms, 51.4MB)

 

테스트 14의 경우 1065.65ms -> 663.44ms로 확 줄었다.

딕셔너리에 접근해서 += 연산을 수행하는 과정이 줄었기 때문에 더 빨라진 것 같다. 

정리

---

Python list slicing에 O(N)이 걸린다는 점을 알게 되었다..! 조금만 생각해보면 당연한 이야기였는데 ㅠㅠ

아래 글을 참고해서 숙지해야겠다. 

https://wayhome25.github.io/python/2017/06/14/time-complexity/

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그