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

롤케이크 자르기

프로그래머스

 

• 첫 풀이 - 시간 초과 fail
  • 1 ≤ topping의 길이 ≤ 1,000,000
  • set(topping[:i])와 set(topping[i:])를 반복적으로 생성
  • -> 각 i에 대해 리스트 슬라이싱과 집합 생성이 필요하므로, 매번 O(n) 시간이 걸림
  • -> for문 * if문 해서 O(n^2)시간 복잡도를 가지게 됨

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

 

• 두번째 풀이 - 시간초과 fail
  •  counter 사용했으나 그래도 fail
  • list 에 추가하고 left도 + 하는 시간이 생각보다 큰듯
  • 원인
    • set이 아닌 list를 사용한 점
    • while문 돌면서 pop(0)을 한 점
      
      • 📍pop(0)은 리스트의 첫 요소를 제거한 후 나머지 요소를 앞으로 한 칸씩 이동시키기 때문에, O(n) 시간이 걸림
      • 이 과정을 n번 반복하면 O(n^2)의 복잡도가 발생

from collections import Counter

def solution(topping):
    n=len(topping)
    answer = 0
    checked=[]
    left=0
    count_lst=Counter(topping)
    
    while topping:
        tmp=topping.pop(0)
        count_lst[tmp]-=1
        if count_lst[tmp]<=0:
            del count_lst[tmp]
        
        if tmp not in checked:
            checked.append(tmp)
            left+=1
        if left==len(count_lst):
            answer+=1
        
    return answer

 

 

• 풀이 수정 - success
  • list대신 set 사용
    • left로 따로 세지않고 set의 길이로계산
  • 매번 pop 하지 않고 for문으로 확인해서 counter_lst를 변경해가면서 체크
    • 리스트가 계속 변경되지 않는다는 점이 중요!!

from collections import Counter

def solution(topping):
    answer = 0
    checked=set()
    count_lst=Counter(topping)
    
    for tp in topping:
        count_lst[tp]-=1
        if count_lst[tp]<=0:
            count_lst.pop(tp)
        
        if tp not in checked:
            checked.add(tp)
            
        if len(checked)==len(count_lst):
            answer+=1
        
    return answer