[백준] (실패) 30804 과일 탕후루

Hyun·2025년 3월 23일

목록 보기

89/92

문제

은하는 긴 막대에
$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)$

출력

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

예제 입력 1

5
5 1 1 2 1

예제 출력 1

4
과일을 앞에서
$1$ 개, 뒤에서
$0$ 개의 과일을 빼면 남은 과일은
$1, 1, 2, 1$ 번 과일이 꽂혀있는 탕후루가 됩니다. 과일의 개수는
$4$ 개입니다.

예제 입력 2

3
1 1 1

예제 출력 2

3
탕후루가 이미 두 종류 이하의 과일로만 이루어져 있습니다.

예제 입력 3

9
1 2 3 4 5 6 7 8 9

예제 출력 3

풀이

오랜만에 정말 어려운 문제를 만났다.
투 포인터를 사용하는 문제로, 나는 투포인터 풀이를 몰랐어서 많이 헤매었다.처음엔 deq 을 이용해서 풀었으나 풀리지 않았다.

투 포인터로 푼다는 것을 검색을 통해 알게 된 후, 투 포인터 기초 문제 2개를 풀고 문제를 다시 풀어 보았다.

그래도 풀이가 생각나지 않아서 결국 타 풀이 방식을 참고했다.
알고보니 이 문제는 두 개의 포인터를 모두 제일 왼쪽에 위치시킨 후 오른쪽으로 이동해나가는 방식이었다.

그래서 2중 while 문으로 풀릴 거라고 생각해서 아래와 같이 풀었는데, 시간초과가 나왔다.

import sys
input = sys.stdin.readline

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

l, r = 0, 0
max_val = 1
while r < len(arr):
    # r 을 집합 크기가 3이 될때까지 반복
    while r != len(arr) and len(set(arr[l:r+1])) < 3:
        r+=1

    # 집합 크기가 2일때의 최대 과일 개수 
    max_val = max(max_val, r - l)
    
    # l 을 집합 크기가 2이 될때까지 반복
    while len(set(arr[l:r+1])) > 2:
        l+=1

print(max_val)

arr[ : ] 처럼 슬라이싱을 사용하면 배열을 복사하게되고, set 을 사용하면 다시 전체 배열을 한번 훑는것이라서 연산이 더 늘어난다는 것을 알게되었다.

그러나 위 방법말고는 생각이 나지 않아 그래서 결국엔 타 풀이를 자세히 참고해서 딕셔너리, Counter 를 사용해 시간복잡도를 줄이는 방법을 확인하였고 아래와 같이 풀었다.

핵심은 다음과 같다.

과일의 종류와, 갯수를 기록하기 위해 딕셔너리 또는 Counter 를 사용한다.
오른쪽 포인터(r)은 문제에서 위치할 수 있는 경우가 n 개 이므로 for 문을 n 번만 돌면서 오른쪽으로 한 칸씩 이동하면 된다.
왼쪽 포인터(l)은 r 의 위치에 따라 딕셔너리 또는 Counter 의 개수가 2 이하가 될때까지 l 을 이동 시킨다.
이때 핵심은 l 을 이동시킬때 기존 인덱스 l 의 위치에 있는 값에 대해 딕셔너리 또는 count 에서 개수를 1 감소시켜야 한다, 즉 del count(arr[l]) 을 해주는게 아니라 count(arr[l]) -= 1 을 해줘야 한다. arr[l] 종류의 과일 1개를 기록에서 제외시키는 것이지 arr[l] 종류의 과일을 모두 기록에서 제외시키는게 아니기 때문이다. 이후 count(arr[l]) 의 값이 0이라면 count 에서 arr[l] 을 삭제시켜줘야 한다. arr[l] 을 삭제해야 len(count) 에 포함되지 않기 때문이다.

예를 들어)
2 3 2 2 5 4 이 경우를 살펴 보면 인덱스 0 - 3 의 범위가 최대인데, 인덱스 3 에 위치한 r 을 4 로 이동 시킨 후 인덱스 0 에 위치한 l 을 오른쪽으로 이동 시킬 때 del count[arr[0]] 으로 제거시켜 버리면 r 이 오른쪽으로 가면서 기록한 값의 개수(여기선 2)가 아예 없어지게 되기 때문이다.
따라서 count[arr[l]] -= 1 을 하고, 값이 0 이 되면 그걸 아예 제거시킨다.

from collections import Counter
import sys
input = sys.stdin.readline
n = int(input())
arr = list(map(int,input().split()))

count = Counter()
max_val = 1
l, r = 0, 0

for i in range(n):
    # r 을 기록 후 한칸 이동
    count[arr[r]] += 1
    r += 1
    
    # 집합 길이 2가 될때까지 l 옮김
    # 이미 2면 l 안 움직이고 그다음에 바로 r 이 움직이게 됨
    while len(count) > 2:
        count[arr[l]] -= 1
        if count[arr[l]] == 0:
            del count[arr[l]]
        l += 1

    max_val = max(max_val, sum(count.values()))

print(max_val)