[프로그래머스] 코딩테스트 연습 Lv2> 연습문제 > 롤케이크 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/132265?language=python3

프로그래머스

 

이 문제를 처음 접했을 때는 인덱스 슬라이싱을 먼저 떠올렸다.

그래서 for 문을 돌리며 인덱스를 기준으로 left와 right를 자르고 len(), set()을 통하여 포함되어 있는 토핑 갯수를 확인하였다.

그러나 시간초과 문제를 직면하였다.

 

그 다음에는 deque를 활용해서 큐 자료구조를 활용하였다.

최대한 연산을 줄이고 길이를 나타내는 변수(check, count)를 만들어서 비교하였다.

절반만 맞고, 절반은 시간초과가 떴다.

from collections import deque

def solution(topping):
    answer = 0
    check = len(set(topping))
    count = 0
    dq1 = deque()
    dq2 = deque(topping)

    for i in topping:
        dq2.popleft()
        if (not i in dq1):
            dq1.append(i)
            count += 1

        if (not i in dq2):
            check -= 1
        
        if (count < check):
            continue
        elif (count > check):
            break
        else:
            answer += 1
    return answer
    
topping = [1, 2, 1, 3, 1, 4, 1, 2]

print(solution(topping))

 

가장 마지막 방식으로는 딕셔너리를 활요해 문제를 풀었다.

확실히 딕셔너리로 풀었을 때 가장 시간이 단축되었다.

문제의 형태에 따라 좋은 방식을 선택한다면 풀이하는 시간을 많이 줄일 수 있다.

주석 부분은 처음에는 사용했지만, 없어도 문제가 풀리기 때문에 주석처리 했다.

처음에 이 코드를 이해하려면 필요하기에 남겨두었다.

def solution(topping):
    answer = 0
    left_dic = {}
    right_dic = {}
    left_len = 0
    right_len = 0

    for d in set(topping):
        right_dic[d] = 0
        right_len += 1
    
    for i in topping:
        right_dic[i] += 1
        
    for j in topping:
        
        if (not j in left_dic):
            left_dic[j] = 0
            left_len += 1
        
        # left_dic[j] += 1
        right_dic[j] -= 1
        
        if right_dic[j] == 0:
            # del right_dic[j]
            right_len -= 1
            
        if (left_len < right_len):
            continue
        elif (left_len > right_len):
            break
        else:
            answer+=1
    
    return answer
    
topping = [1, 2, 1, 3, 1, 4, 1, 2]

print(solution(topping))