반응형
문제
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 |
반응형
문제
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 |