[백준] 30804 과일 탕후루 (python 파이썬)

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

 

---

실버2 라는 게 믿기지 않는 문제. 내가 슬라이딩 윈도우 개념을 몰랐다면 못 풀었을 거 같다.

이건 왜 실버에 있을까 

---

아이디어

- 문제에서 제시하는 과일 두개로 만들 수 있는 최대 길이를 구하기 위해 투 포인트 개념을 사용했다. 

생각보다 작은 N의 크기(200000), 널널한 시간제한(2초), 그리고 적은 과일 개수(최대 9개)를 보고 모든 경우를 계산해도 괜찮다고 생각했다. 그래서 슬라이딩 윈도우를 생각하며 왼쪽에서 오른쪽으로 탐색하면서 가장 길이가 긴 경우를 찾았다.

 

-  과일 종류의 개수를 구할 때 편하려고 딕셔너리를 사용했다.

---

전체 코드

N = int(input())
tangList = list(map(int, input().split()))

visited = {}

maxLen = 0
leftPoint = 0
rightPoint = 0

while rightPoint < N:
    nowTang = tangList[rightPoint]

    if nowTang in visited:
        visited[nowTang] += 1
    else:
        visited[nowTang] = 1

    while len(visited) > 2:
        removeTang = tangList[leftPoint]

        visited[removeTang] -= 1

        if visited[removeTang] == 0:
            del visited[removeTang]

        leftPoint += 1
    maxLen = max(maxLen, rightPoint - leftPoint + 1)
    rightPoint += 1

print(maxLen)

---

코드 설명

if nowTang in visited:
    visited[nowTang] += 1
else:
    visited[nowTang] = 1

 

과일이 이미 딕셔너리에 있으면 과일 개수만 늘려주고 없으면 딕셔너리에 과일을 추가해 준다.

 

while len(visited) > 2:
    removeTang = tangList[leftPoint]

    visited[removeTang] -= 1

    if visited[removeTang] == 0:
        del visited[removeTang]

    leftPoint += 1

 

오른쪽 포인터를 점점 늘려주다가 과일이 3개가 되면 while문으로 과일 개수를 줄여준다. 왼쪽 포인터를 오른쪽으로 한 칸씩 당기며 과일 개수를 줄여준다. 과일 개수가 0이 된 과일은 사전에서 지워주면 된다.

 

maxLen = max(maxLen, rightPoint - leftPoint + 1)
rightPoint += 1

 

오른쪽 포인터 위치마다 정답 값을 업데이트해 주면 된다.