백준 30804 과일 탕후루 / python

문제 : 30804

풀이 point

일반적으로 두 포인터 하면 양 끝에서 가운데로 모인다고 생각하는데 이 문제는 그렇게 푸는 것이 아니라 같은 지점에서 시작하여 과일 종류가 2보다 많아질 때 과일을 없애나가며 푸는 문제이다.

풀이 방법

예를 들어 예제 입력 3에
1 2 3 4 5 6 7 8 9 라면
i = 0, j = 0으로 시작하여 i를 먼저 증가시킨다.

이때 과일의 종류와 그 과일이 몇개인지 파악하기 위해 딕셔너리에 값을 저장해둔다.
{과일종류 : 과일 개수}이래야지 나중에 어떤 과일을 만났을 때 이미 저장해둔 과일인지 아닌지 파악을 쉽게 할 수 있다.(딕셔너리 없으면 매번 for문 돌아서 확인해야함)

i=3이 됐을때는 딕셔너리의 길이가 3이되고, 이는 과일의 종류가 3개가 됐다는 뜻이므로 과일을 줄여야한다. 아직까지 j=0인 상태이다.

j를 1칸씩 늘려서 과일의 개수를 줄이고, 2이하로 줄여졌다면 다시 i를 증가시킨다.

이렇게 해서 가장 길이가 클 때를 매번 갱신해나가며 최대 과일의 개수를 구한다.

코드

import sys
input = sys.stdin.readline

N = int(input().rstrip())

fruit = list(map(int, input().rstrip().split()))

j = 0
diffFruit = {}
maxL = 0
for i in range(len(fruit)):
    if fruit[i] in diffFruit:
        diffFruit[fruit[i]] += 1
    else:
        diffFruit[fruit[i]] = 1
    
    while len(diffFruit) > 2:
        diffFruit[fruit[j]] -= 1
        if diffFruit[fruit[j]] == 0:
            del diffFruit[fruit[j]]
        j += 1

    maxL = max(maxL, i-j+1)

print(maxL)

아쉬운 점

일단 투포인터를 양 끝에서 진행한다는 틀에 박혀있었고, 문제 자체가 양 옆에서 제거해나간다고 생각을 유도해서 그 사고방식에만 막혀있었다. 그래서 이거 DP아닌가... 라는 생각이 자꾸 들었다. 근데 전혀 아니었고, 슬라이딩 윈도우 방식으로 푸는 것이었다. 아마 슬라이딩 윈도우라고 적혀있었으면 생각이 갔을 거 같기도 하다.

다양한 방면으로 생각하는 방식을 길러야겠다...