문제 링크: https://www.acmicpc.net/problem/30804

Thumbnail: Photo by Yevhen Buzuk (Unsplash)

​

풀이

과일의 종류별 개수 세기

정답을 구하기 위해서는, 현재 탕후루에 포함된 과일의 개수를 세는 방법이 필요합니다. 이는 Map 형태의 자료구조를 활용하면 됩니다.

투 포인터

​투 포인터란, 이름처럼 두개의 포인터(배열의 인덱스)를 가지고 부분 배열을 동적으로 조정하며 탐색하는 방법입니다.

• 연속된 부분 수열을 탐색할 때 효과적입니다.
• 배열의 한쪽 끝에서 반대쪽 끝까지 이동하며 조건을 만족하는 가장 긴 구간을 찾는데 유리합니다.

이 문제도 탕후루의 양 끝에서 적절히 조절하며 조건(과일 종류가 2개 이하)을 만족하는 가장 긴 구간을 찾아야 하므로, 투 포인터 방식으로 풀 수 있습니다.

어떻게 탐색할 것인가?

Map 자료구조(count)로 과일의 개수를 관리하며, 우측 포인터(right)를 0부터 \(N-1\)까지 증가시켜가며 배열을 탐색합니다. 이때, right가 증가하게 되면 새로 포함된 과일의 종류도 count에 반영합니다.

right가 증가한 이후, count에 포함된 과일의 개수가 2개 이하가 될 때까지 왼쪽 포인터(left)를 증가시킵니다. left가 증가할 때 마다 제외된 과일을 count에서도 제거하며, 이때 해당 과일의 개수가 0개가 된다면 count에서 그 과일(key)를 삭제합니다.

이후, 이번 부분 수열에서의 최대 길이를 max_length에 갱신합니다. 이전 최대 길이와 현재 부분 수열의 길이(right - left + 1)를 비교해 더 큰 쪽을 사용합니다.

이 과정을 모두 반복한 뒤의 max_length값이 정답이 됩니다.

fruits = tuple(map(int, input().split()))
max_length = 0
left = 0
count = {}
for right in range(N):
    try:
        count[fruits[right]] += 1
    except KeyError:
        count[fruits[right]] = 1
    while len(count) > 2:
        count[fruits[left]] -= 1
        if count[fruits[left]] == 0:
            del count[fruits[left]]
        left += 1
    max_length = max(max_length, right - left + 1)

전체 코드

input = open(0).readline
N = int(input())
fruits = tuple(map(int, input().split()))
max_length = 0
left = 0
count = {}
for right in range(N):
    try:
        count[fruits[right]] += 1
    except KeyError:
        count[fruits[right]] = 1
    while len(count) > 2:
        count[fruits[left]] -= 1
        if count[fruits[left]] == 0:
            del count[fruits[left]]
        left += 1
    max_length = max(max_length, right - left + 1)
print(max_length)