[백준] 30804 과일 탕후루

J. Hwang·2025년 3월 3일

coding test

목록 보기

106/108

문제

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

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

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

입력

첫 줄에 과일의 개수 $N$ 이 주어집니다. $(1 \le N \le 200\,000)$

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 $N$ 개의 정수 $S_1, \cdots, S_N$ 이 공백으로 구분되어 주어집니다. $(1 \le S_i \le 9)$

출력

문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.

내 풀이

import sys
input = sys.stdin.readline

n = int(input())
candy = list(map(int, input().split()))

a = 0
b = len(candy)

iters = n//2 if n%2==1 else n//2-1

answer = []
while len(candy[a:b])!=0:        
    for _ in range(iters):
        check = set(candy[a:b])
        if len(check) <= 2:
            answer.append(len(candy[a:b]))
        a += 1
        for _ in range(iters):
            check = set(candy[a:b])
            if len(check) <= 2:
                answer.append(len(candy[a:b]))
            b -= 1

print(max(answer))

위는 어떻게든 풀어봤지만 시간 초과를 받은 코드...

아래는 다른 풀이를 참고하여 정답을 받은 코드이다. (코멘트 참조)

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

n = int(input())
candy = list(map(int, input().split()))

dict1 = defaultdict(int)

left = 0
right = 0
max_length = 0
while right < n:
	# 오른쪽 포인터가 가리키는 과일 추가
    dict1[candy[right]] += 1
   
   # 과일 종류가 2개를 초과하면 왼쪽 포인터 이동
    while len(dict1) > 2:
        dict1[candy[left]]-= 1
        if dict1[candy[left]]==0:
            del dict1[candy[left]]
        left += 1
        
    max_length = max(max_length, right-left+1)
    right += 1
    
print(max_length)

코멘트

브루트포스로 모든 경우의 수를 탐색하다가 조건을 만족할 때를 찾아내는 문제인 걸 느끼고 그렇게 구현해보았다. 나의 경우 양 끝에 포인터 하나씩을 배치하고 왼쪽 포인터(a)는 +1씩, 오른쪽 포인터(b)는 -1씩 인덱스를 조절해서 점점 중앙으로 좁혀지도록 탐색했다. 이 때 왼쪽 포인터와 오른쪽 포인터를 동시에 +1, -1씩 조절하면 탐색하지 못하는 경우가 생겨버리므로 이중 for문을 돌려서 a를 조절할 때는 a만, b를 조절할 때는 b만 조절하도록 했으나 이 때문에 시간 초과를 받게 되었다ㅠ

그래서 다른 풀이를 참고해서 다시 풀어보았다. 이 풀이에서도 포인터를 2개 사용하되 둘 다 왼쪽부터 시작해서 인덱스를 늘려나가는데, defaultdict를 이용해서 두 포인터 사이의 과일이 두 종류를 초과하게 되면 더 left의 인덱스를 키우는 방식으로 이중 for문 없이도 과일이 두 종류 이하일 때만 탐색할 수 있게 구현했다. defaultdict는 기본값을 자동으로 할당해서 KeyError를 방지할 수 있는 딕셔너리이다. 이번 문제처럼 어느 위치에 몇 번 과일이 나올지 바로 등록하기 어려울 때 유용한 자료형이다.

문제를 보고 브루트포스로 풀어야겠다고 생각할 수 있을 정도로 성장해서 좋긴 하지만, 여전히 다른 코드를 보며 저리 명료하게 코드를 짤 수 있다니 부럽다는 생각이 든다ㅠ 더 열심히 해서 저 명료한 코드도 내 머리에서 바로 생각할 수 있도록 해야지...