반응형

문제

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


코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int[] fruits = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            fruits[i] = Integer.parseInt(st.nextToken());
        }

        Map<Integer, Integer> count = new HashMap<>();
        int left = 0;
        int result = 0;

        for (int right = 0; right < N; right++) {
            count.put(fruits[right], count.getOrDefault(fruits[right], 0) + 1);

            while (count.size() > 2) {
                int leftFruit = fruits[left];

                count.put(leftFruit, count.get(leftFruit) - 1);

                if (count.get(leftFruit) == 0) {
                    count.remove(leftFruit);
                }

                left++;
            }
            result = Math.max(result, right - left + 1);
        }

        System.out.println(result);
    }
}

풀이

문제를 읽자마자 뭘 써야할지 감이 왔다. 슬라이딩 윈도우 문제이다. 

 

Map<Integer, Integer> count = new HashMap<>();

 

  • 슬라이딩 윈도우에서 각 과일의 등장 횟수를 HashMap에 저장한다.

 

for (int right = 0; right < N; right++) {
    // 새 과일 추가
    count.put(fruits[right], count.getOrDefault(fruits[right], 0) + 1);

    // 두 종류 초과하면 left 이동
    while (count.size() > 2) {
        int leftFruit = fruits[left];
        count.put(leftFruit, count.get(leftFruit) - 1);
        if (count.get(leftFruit) == 0) {
            count.remove(leftFruit);
        }
        left++;
    }

    // 최대 구간 길이 갱신
    result = Math.max(result, right - left + 1);
}
  • 새 과일 추가
    • rigth를 한 칸씩 증가시키며 새 과일을 count에 추가
    • 새 과일이 이미 있으면 카운트만 증가
  • 두 종류 초과 시
    • left 위치의 과일을 하나씩 제거(카운트 감소)
    • 카운트가 0이 되면 Map에서 완전히 제거
    • left를 오른쪽으로 한 칸 이동
  • 최대 길이 갱신
    • 현재 윈도우의 길이(right - left + 1)와 result 중 큰 값 선택
반응형

'백준' 카테고리의 다른 글

[백준] 1764: 듣보잡  (1) 2025.05.27
[백준] 7569: 토마토  (1) 2025.04.29
[백준] 28702: FizzBuzz  (0) 2025.04.23
[백준] 15829: Hashing  (0) 2025.04.22
[백준] 2667: 단지번호붙이기  (0) 2025.04.21