[python 백준] 30804 번 : 과일 탕후루 (실버 2)

 

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

문제

은하는 긴 막대에 N$N$개의 과일이 꽂혀있는 과일 탕후루를 만들었습니다. 과일의 각 종류에는 1$1$부터 9$9$까지의 번호가 붙어있고, 앞쪽부터 차례로 S1,S2,⋯,SN$S_1, S_2, \cdots, S_N$번 과일이 꽂혀있습니다. 과일 탕후루를 다 만든 은하가 주문을 다시 확인해보니 과일을 두 종류 이하로 사용해달라는 요청이 있었습니다.

탕후루를 다시 만들 시간이 없었던 은하는, 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼서 두 종류 이하의 과일만 남기기로 했습니다. 앞에서 a$a$개, 뒤에서 b$b$개의 과일을 빼면 Sa+1,Sa+2,⋯,SN−b−1,SN−b$S_{a+1}, S_{a+2}, \cdots, S_{N-b-1}, S_{N-b}$번 과일, 총 N−(a+b)$N-(a+b)$개가 꽂혀있는 탕후루가 됩니다. (0≤a,b;$(0 \le a, b;$ a+b<N)$a+b < N)$ 

이렇게 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 구하세요.

입력

첫 줄에 과일의 개수 N$N$이 주어집니다. (1≤N≤200000)$(1 \le N \le 200\,000)$ 

둘째 줄에 탕후루에 꽂힌 과일을 의미하는 N$N$개의 정수 S1,⋯,SN$S_1, \cdots, S_N$이 공백으로 구분되어 주어집니다. (1≤Si≤9)$(1 \le S_i \le 9)$ 

출력

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

예제 입력 1 복사

5
5 1 1 2 1

예제 출력 1 복사

4

 

예제 입력 2 복사

3
1 1 1

예제 출력 2 복사

3

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

예제 입력 3 복사

9
1 2 3 4 5 6 7 8 9

예제 출력 3 복사

2

 

해당 문제는 계속 틀려서 검색해봐도 이해가 안가서 시간이 오래 걸린 문제이다.

일단 나의 틀렸던 풀이과정을 이러하다.

맨 앞과 맨 뒤에서 과일을 제거했을때 가장 길이가 긴 경우를 구해야 하므로

일단 과일의 갯수를 세서 갯수를 기준으로 오름차순을 해준다. 그리하면 사과 : 1 , 망고 : 3 , 바나나 : 5 이런식으로 정렬이 되는데 여기서 탕후루에 꽃혀있는 맨 앞과 맨 뒤에 과일과 갯수가 제일 적은 과일을 순차적으로 비교하여 일치하면 제거해주는 방식으로 풀었다. 해당 방식으로 풀면 테스트 케이스는 맞지만 정답이 아니라고 하였다. 그래서 테스트케이스를 직접 만들어서 해보았더니 문제가 발생했다.

16
1 2 1 2 3 1 2 1 2 1 2 3 1 2 1 2

해당 테스트 케이스에서는 3과 3 중간에 있는 1 2 1 2 1 2 의 여섯개가 가장 길이가 긴 경우이다. 하지만 밑에 코드로 하면  1 2 1 2 로 4개가 출력이 된다. 그래서 내가 작성한 코드로는 정답으로 갈 수 없다는 것을 알고 다른 방법을 찾기 위해 검색을 하였다.

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
tang = deque(list(map(int,input().split())))
fruits = dict()
for i in tang:
    if i in fruits:
        fruits[i] += 1
    else:
        fruits[i] = 1

sortedfruits = list(sorted(fruits,key=fruits.get))
index = 0
while len(sortedfruits) > 2:
    if tang[0] == sortedfruits[index]:
        if fruits[tang[0]] > 1:
            fruits[tang.popleft()] -= 1
        else:
            fruits[tang.popleft()] -= 1
            sortedfruits.pop(index)
        index = 0
    elif tang[-1] == sortedfruits[index]:
        if fruits[tang[-1]] > 1:
            fruits[tang.pop()] -= 1
        else:
            fruits[tang.pop()] -= 1
            sortedfruits.pop(index)
        index = 0
    else:
        index += 1

print(len(tang))

 

검색을 하니 투 포인터로 문제를 풀어야 한다고 하는데 처음에는 이것이 왜 되는지 이해가 안가서 이틀동안 계속 생각해 보고 코드를 한줄씩 읽어보니 이유를 알게되었다.

left pointer 와 right pointer 로 두고 right pointer 을 과일이 두종류만 있을때까지 오른쪽 포인터로 이동한다.그렇게 했을때 왼쪽 포인터와 오른쪽 포인터 사이에 거리가 가장 긴 경우를 출력하는 것이다.

이렇게 말하니까 쉬운데 코드만 보고 이해하려 했을때는 이해가 안갔다..

 

아래는 성공한 코드이다.

from collections import deque
import sys
input = sys.stdin.readline
n = int(input())
tang = deque(list(map(int,input().split())))
fruits = dict()
left_pointer = 0
right_pointer = 0
maxlen = 0
for right_pointer in range(len(tang)):
    fruit = tang[right_pointer]
    if fruit in fruits:
        fruits[fruit] += 1
    else:
        fruits[fruit] = 1

    while 2 < len(fruits):
        fruits[tang[left_pointer]] -= 1
        if fruits[tang[left_pointer]] == 0:
            fruits.pop(tang[left_pointer])
        left_pointer += 1

    # leftpointer 에 인덱스와 rightpointer 의 인덱스 사이에는 2가지 종류의 과일만 있으며 left부터 right 까지 
    # 예를들어 left = 2 right = 4 일경우 해당 인덱스에 포함된 숫자는 2,3,4, 3개 이므로 4-2= 2 가 나오므로 + 1 을 해줘야 정확한 갯수를 계싼할수있다.
    maxlen = max(maxlen, right_pointer - left_pointer + 1)
            
print(maxlen)