[백준] 30804 - 과일 탕후루

https://www.acmicpc.net/problem/30804

 

탕후루 꼬치에서 앞 뒤로 몇개의 과일을 빼 2가지 종류 이내로 구성된 가장 긴 길이의 탕후루 꼬치를 만드는 문제다.

처음에는 단순 구현을 해야하나 싶어서 한참 고민했는데, 앞 뒤로 과일을 뺀다는 것은 남은 과일이 연속적이라는 점에서 힌트를 얻어 투 포인터를 생각해낼 수 있었다.

 

앞에서부터 과일을 하나씩 살펴보면서 2가지 종류가 되지 않았다면 연속된 길이에 포함하고, 2가지가 넘는 종류가 나오는 순간 그때까지 담은 길이를 정답 후보로 체크한다.

그리고 그 이전에 담았던 과일 중, 제일 마지막에 나왔던 종류가 아닌 과일을 2가지 종류에서 제외하고, 새로 나온 종류를 2가지 종류에 추가한 뒤 위 과정을 반복한다.

 

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

left, right = 0, 1
kind = [fruit[0]]
answer = 0
next_left = 0
while right < n:
    if len(kind) == 1:
        if fruit[right] not in kind:
            kind.append(fruit[right])

    else:
        if fruit[right] not in kind:
            answer = max(answer, right - left)

            # next_left에 있는 과일과 다른 종류의 과일을 kind 에서 제거
            for i in range(len(kind)):
                if kind[i] != fruit[next_left]:
                    kind.pop(i)
                    break

            kind.append(fruit[right])
            left = next_left

    if fruit[right - 1] != fruit[right]:
        next_left = right
    right += 1

answer = max(answer, n-left)
print(answer)

 

전체 코드는 위와 같다.

 

현재와 다른 과일이 나오는 순간, 그 위치를 다음에 left 포인터가 이동할 위치로 지정해주고, 과일 종류를 바꿀 땐, next_left 위치에 있는 과일이 아닌 종류를 빼준다.