[Python] 백준/BOJ 30804번: 과일 탕후루 (Silver 2)

💻 Problem

문제 보러 가기

 

은하는 긴 막대에 N개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1부터 9까지의 번호가 붙어있고, 앞쪽부터 차례로 S1, S2,⋯, SN번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해 보니 과일을 두 종류 이하로 사용해 달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a개, 뒤에서 b개의 과일을 빼면 Sa+1,Sa+2,⋯,SN−b−1,SN−b번 과일, 총 N−(a+b)개가 꽂혀있는 탕후루가 됩니다. (0≤a,b; a+b < N)

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

 

💡 Approach

과일 종류를 세기 위해 딕셔너리를 이용하는 것이 좋을 것 같았다.

처음에는 Counter를 이용하는 쪽으로 생각했다.

그렇게 자연스럽게 투포인터를 사용할 때, s = 0, e = n -1로 생각해서 점점 가운데로 좁힌다고 생각을 했는데.. 어느 기준으로 s나 e를 밀고 당길지 애매했다.

 

그래서 s, e 모두 0에서 시작하고 e를 뒤로 미는 식으로 진행했다.

즉, 앞뒤로 과일을 빼보는 형식이 아니라 일단 제일 왼쪽 과일을 제외한 모든 과일을 뺀 후, 뒤에 과일을 추가하고 조건에 맞지 않으면 앞에 과일을 빼보고 하며 탐색하는 형식이다.

 

1.    s, e 모두 0에서 시작한다.
2.    e에 해당하는 과일을 탕후루에 꽂는다
3.    현재 탕후루에 꽂혀 있는 과일 종류가 2 이하가 될 때까지 가장 왼쪽에 꽂혀 있는 과일을 뺀다. (s + 1)
4.    현재 탕후루의 가장 오른쪽에 과일을 추가한다. (e + 1)

 

✏️ Solution

import sys
from collections import defaultdict
input = sys.stdin.readline

N = int(input())
tanghulu = list(map(int, input().split())) # 처음 입력받은 과일 탕후루
fruits = defaultdict(int) # 현재 꽂혀 있는 과일 탕후루
cnt = 0
s, e = 0, 0

while e < N:
    fruits[tanghulu[e]] += 1

    # 과일 종류가 두 종류 이하가 될 때까지 s를 오른쪽으로 이동시킨다
    while len(fruits) > 2:
        # 가장 왼쪽에 있는 과일을 뺀다
        fruits[tanghulu[s]] -= 1
        # 과일을 빼면서 해당 과일이 현재 탕후루에 없으면 key를 삭제한다
        if fruits[tanghulu[s]] == 0:
            del fruits[tanghulu[s]]
        s += 1

    # 과일 개수의 최댓값을 갱신하다
    cnt = max(cnt, e - s + 1)
    # e를 오른쪽으로 이동시킨다
    e += 1

print(cnt)

시간복잡도는 s의 이동 횟수 N번과 e의 이동 횟수 N번이다.

N의 최댓값이 2 * 10^5이므로 총 시간복잡도는 4 * 10^5이 된다.