[Silver II] 과일 탕후루 - 30804

문제 링크

성능 요약

메모리: 35568 KB, 시간: 328 ms

분류

브루트포스 알고리즘, 구현, 두 포인터

제출 일자

2024년 10월 21일 13:48:18

문제 설명

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

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

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

입력

첫 줄에 과일의 개수 N이 주어집니다. (1≤N≤200000)

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

출력

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

풀이

첫 번째 풀이

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

while True:
    if len(set(fruit)) <= 2:
        print(len(fruit))
        break
    fruit.pop(0)
    if len(set(fruit)) <= 2:
        print(len(fruit))
        break
    fruit.pop()

원래는 이러한 방식으로 `set` 자료구조를 사용하여 리스트를 빼주는 방식으로 문제를 풀이했었다.

시간 초과가 발생하였고 이렇게 해결하는 것이 아니라고 판단했다.

밑의 알고리즘 분류를 확인해보니 투 포인터를 사용하여 문제를 풀이하는 것 같다.

두 번째 풀이

from collections import defaultdict

n = int(input())
fruit = list(map(int, input().split()))
s, e = 0, 0
count = defaultdict(int)

while e < n:
    count[fruit[e]] += 1

    while len(count.keys()) > 2:
        count[fruit[s]] -= 1
        if count[fruit[s]] == 0:
            del count[fruit[s]]
        s += 1
    e += 1
print(sum(count.values()))

각 과일의 개수를 입력값으로 받기 때문에 이를 종류 별로 개수를 세어 줄 `dictionary`를 하나 만들어주었다.

개수를 계속 세어주면서 과일의 종류가 2개가 넘는다면 왼쪽 인덱스의 과일을 줄이고 과일의 개수가 0개가 되면 필요가 없기 때문에 제거해준다. 그리고 왼쪽 인덱스를 1 증가시켜준다.

모든 과정을 다 시나면 오른쪽 인덱스를 1 증가시켜준다.

그리고 남은 과일 모든 과일의 개수를 더하여 출력해주도록 했다.

이렇게 하니 틀렸다고 나온다.

생각해보니 이렇게 되면 종류가 2개 이하일 때의 과일의 개수 최댓값을 반환할 수가 없었고 마지막 결과의 개수만 출력되는 것이었다.

from collections import defaultdict

n = int(input())
fruit = list(map(int, input().split()))
s, e = 0, 0
count = defaultdict(int)
max_count = 0

while e < n:
    count[fruit[e]] += 1
    
    while len(count.keys()) > 2:
        count[fruit[s]] -= 1
        if count[fruit[s]] == 0:
            del count[fruit[s]]
        s += 1
    e += 1
    max_count = max(max_count, sum(count.values()))
print(max_count)