🍓 백준 30804번: 탕후루

문제 링크

문제 소개

  • 입력:
    • 첫째 줄: 과일의 개수 N (1 <= N <= 200,000)
    • 둘째 줄: N개의 과일 종류를 나타내는 정수
  • 출력:
    • 두 종류 이하의 과일로 만들 수 있는 가장 긴 탕후루의 길이
  • 알고리즘 분류:
    • #구현 #브루트포스 #투-포인터 #슬라이딩-윈도우

첫 번째 시도: 브루트포스 👊

Idea

처음엔 N의 범위가 200,000이라 완전 탐색은 안될거라 생각했다

하지만 혹시나 하는 마음에 이중 반복문으로 모든 부분 배열을 확인하는 방법을 떠올렸다

right_end로 오른쪽 끝 범위를 정해놓고, left_end를 1씩 늘려가며 과일의 종류를 세는 방식이었다

Counter를 사용하면 과일 종류를 쉽게 셀 수 있을 것 같았다

Code

import sys
from collections import Counter

n = int(sys.stdin.readline().rstrip())
fruits = list(map(int, sys.stdin.readline().split()))
answer = -1

for right_end in range(1, n):
    left_end = 0
    while left_end < right_end:
        c = Counter(fruits[left_end:right_end+1])
        fruit_len = right_end - left_end + 1
        left_end += 1

        if len(c) <= 2:
            if answer < fruit_len:
                answer = fruit_len
            break

print(answer)

Result

결과는 역시나 시간 초과 ⏳

아무래도 이중 반복문과 반복문 내에서 매번 Counter를 새로 생성하는 과정이 시간 복잡도를 O(N^2)으로 만들어 시간 초과가 발생한 것 같았다

두 번째 시도: 투 포인터 ✨

Idea

시간을 줄이기 위해 투 포인터(슬라이딩 윈도우) 기법을 사용하기로 했다

오른쪽 포인터(right_end)를 계속 이동시키면서 과일 종류를 확인하고

과일 종류가 2개를 초과하면 왼쪽 포인터(left_end)를 이동시켜 윈도우 크기를 조절하는 방식으로 개선하려했다

이렇게 하면 한 번의 순회로 정답을 찾을 수 있을거라 생각했다

Code

import sys
from collections import Counter

n = int(sys.stdin.readline().rstrip())
fruits = sys.stdin.readline().split()
answer = -1
left_end = 0
c = Counter(fruits[0:1])

for right_end in range(1, n):
    
    if fruits[right_end] in c:
        c[fruits[right_end]] += 1
    else:
        c[fruits[right_end]] = 1
        
        while len(c) > 2:
            c[fruits[left_end]] -= 1
            if c[fruits[left_end]] == 0:
                del c[fruits[left_end]]
            left_end += 1
    answer = max(answer, c.total())

print(answer)

Result

결과는 97%에서 틀렸습니다 ❌

무엇이 문제일까 곰곰히 생각해보니

과일이 한 종류만 주어지는 엣지 케이스를 고려하지 않았다는 것을 깨달았다

세 번째 시도: 엣지 케이스 처리 ✅

Idea

기존 코드에서 answer의 초기값을 1로 설정해서

과일이 하나만 들어와도 길이는 최소 1이 보장되도록 수정했다

아주 간단한 수정이었지만, 핵심적인 부분이었다

Code

import sys
from collections import Counter

n = int(sys.stdin.readline().rstrip())
fruits = sys.stdin.readline().split()
answer = 1
left_end = 0
c = Counter(fruits[0:1])

for right_end in range(1, n):
    
    if fruits[right_end] in c:
        c[fruits[right_end]] += 1
    else:
        c[fruits[right_end]] = 1
        
        while len(c) > 2:
            c[fruits[left_end]] -= 1
            if c[fruits[left_end]] == 0:
                del c[fruits[left_end]]
            left_end += 1
    answer = max(answer, sum(c.values()))

print(answer)

Result

드디어 성공! 🎉

개선할 부분 🤔

Counter를 사용하지 않고, 딕셔너리나 배열을 직접 사용하여 과일 종류를 카운트하면 메모리 사용량을 조금 더 최적화할 수 있을 것 같다