백준 / 과일 탕후루 / 30804번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 과일 탕후루 / 30804번 (실버 2단계)

문제 사이트: https://www.acmicpc.net/problem/30804

 

문제 설명

---

나의 풀이

def two_pointer(fru, n):
    left = 0
    right = len(fru) - 1
    max_total = 0
    count_break = False

    while left < right:
        visited = [False] * 10
        total = 0
        count = 0
        center = (right - left) // 2
        left_find = left
        right_find = right
        while left_find <= right_find:
            if left_find == right_find:
                count_break = True
            if left_find < center:
                if not visited[fru[right_find]]:
                    count += 1
                    visited[fru[left_find]] = True  # 방문 체크 추가
                if count > 2:
                    left += 1
                    max_total = max(max_total, total)
                    break
                total += 1
                left_find += 1

            if center <= right_find:
                if not visited[fru[right_find]]:
                    count += 1
                    visited[fru[right_find]] = True
                if count > 2:
                    right -= 1
                    max_total = max(max_total, total)
                    break
                total += 1
                right_find -= 1
        if count_break:
            max_total = max(max_total, total)
            return max_total

    return max_total

# 과일의 개수
n = int(input())

# 과일
fruit = list(map(int, input().split()))

# 최대 과일 개수 출력
print(two_pointer(fruit, n))

처음 투 포인터의 알고리즘을 생각해서 left, right 지점을 나눠 증가하면서 검사하는 방식을 사용했다.

하지만 이 풀이는 반례가 있게 된다.

반례 1: 앞에서부터 두 종류만 남기기

10

1 1 1 1 2 2 3 3 4 4

이 예시가 들어왔을 때 1, 2가 남아야 최댓값을 갱신하지만 위 코드는 6이아닌 4를 출력한다.

반례 2: 뒤에서부터 두 종류만 남기기

10

4 4 3 3 2 2 1 1 1 1

위와 동일하게 1, 2가 남아야 최댓값을 갱신하지만 위 코드는 6이 아닌 4를 출력한다.

즉 위 코드의 문제는 양끝에서만 과일을 빼면서 두 종류만 남기기에 초점을 맞추고 있지만, 전체적으로 어디서든 두 가지 과일만 남도록 만들어야하는 규칙을 적용하지 못하고 있다.

답안

def two_pointer(fru, n):
    left = 0
    fruit_count = [0] * 10  # 과일의 번호가 1~9 이므로 길이 10인 리스트
    max_total = 0
    unique_fruits = 0  # 현재 슬라이딩 윈도우 안에 있는 과일의 종류 개수

    for right in range(n):
        # 현재 과일의 개수를 추가
        if fruit_count[fru[right]] == 0:
            unique_fruits += 1
        fruit_count[fru[right]] += 1

        # 과일 종류가 2개를 초과하면 왼쪽 포인터를 이동
        while unique_fruits > 2:
            fruit_count[fru[left]] -= 1
            if fruit_count[fru[left]] == 0:
                unique_fruits -= 1
            left += 1

        # 두 종류 이하의 과일만 남은 최대 길이를 계산
        max_total = max(max_total, right - left + 1)

    return max_total

# 과일의 개수
n = int(input())

# 과일 리스트
fruit = list(map(int, input().split()))

# 최대 과일 개수 출력
print(two_pointer(fruit, n))

위 코드는 윈도우 슬라이싱 알고리즘을 이용한다. 뒤에서 빼지 않고 앞에서 검사해나가는 풀이를 이용하면 된다.

5 1 1 2 1 / 1 1 2 1 5 예제가 들어와도 올바른 답안을 제공한다.

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/192

[알고리즘] 투 포인터(Two Pointer)