반응형
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 위치에 있는 과일이 아닌 종류를 빼준다.
반응형
'알고리즘 (PS) > BOJ' 카테고리의 다른 글
[백준] 1450 - 냅색문제 (0) | 2024.06.26 |
---|---|
[백준] 2179 - 비슷한 단어 (72) | 2024.06.25 |
[백준] 17472 - 다리 만들기 2 (0) | 2024.06.16 |
[백준] 1661 - 다솜이의 신발가게 (Python) (0) | 2024.05.29 |
[백준] 17780 - 새로운 게임 (Python) (1) | 2024.05.29 |