[Algorithm/Java] 백준 30804번 - 과일 탕후루
https://www.acmicpc.net/problem/30804
📌 문제
문제 유형
- 구현
- 브루투포스
- 투 포인터
문제 설명
N개의 과일이 순서대로 꽂힌 막대에서 앞과 뒤에서 몇 개를 제거해,
과일 종류가 최대 2종류인 연속 부분을 만들려고 한다.
과일의 개수가 가장 많은 경우의 수를 구하시오.
입력
첫 줄에 과일의 개수
둘째 줄에 탕후루에 꽂힌 과일을 의미하는 n개의 정수
5
5 1 1 2 1
출력
문제의 방법대로 만들 수 있는 과일을 두 종류 이하로 사용한 탕후루 중에서, 과일의 개수가 가장 많은 탕후루의 과일 개수를 첫째 줄에 출력하세요.
4
⚠️ 문제에서는 “앞과 뒤에서 과일을 몇 개 빼서” 과일 종류가 최대 2개인 구간을 만들라고 했지만,
- 나는 “슬라이딩 윈도우(투 포인터)”를 이용해 전체 배열에서 과일 종류가 2개 이하인 가장 긴 연속 구간을 찾는 방식으로 해결했다.
- 따라서 슬라이딩 윈도우 방식을 사용하면 문제처럼 앞·뒤에서 자르지 않고 해결이 가능하다.
🔍 문제 풀이
과일 종류가 2개 이하인 가장 긴 연속 부분 수열을 구하면 된다.!
- Map을 사용해 과일의 종류와 등장 횟수 저장
- 만약 key(과일 종류의 개수)가 3이 되면 -> 구간 축소 시작
- 현재 구간의 맨 앞 과일의 개수를 1 줄이기
- 과일 개수가 0이 되면, 해당 과일은 현재 구간에 더 이상 존재하지 않으므로 ->
fruitKind맵에서 완전히 제거 (과일 종류 감소) - 그 후,
left++를 통해 윈도우의 시작 위치를 한 칸 오른쪽으로 이동
- 현재 구간 길이(
right - left + 1)와 최대값 비교 후 갱신
예제1:
fruits = [1, 1, 1, 2, 3]
- 초기 상태:
fruitKind = {1=3, 2=1, 3=1}→ 종류 3개 → while 진입 - while 루프 흐름
left = 0,fruits[left] = 1- => count 3 → 2
- => left++ 구간: [1, 1, 2, 3]
left = 1,fruits[left] = 1- => count 2 → 1
- => left++ → 구간: [1, 2, 3]
left = 2,fruits[left] = 1- => count 1 → 0 → map에서 제거,
- => left++ → 구간: [2, 3]
⚠️ left++는 반드시 count 감소 이후에 실행되어야 함 -> 그렇지 않으면 구간 맨 앞의 과일을 카운트에서 누락하게 됨
예제 2:
fruits = [5, 1, 1, 2, 1, 5]
📌 놓친 점
과일 개수 감소는 곧바로 종류 감소가 아님
처음에는 과일 종류가 3개가 되었을 때, 한 번만 과일을 제거하면 바로 종류가 줄어든다고 생각했다.
하지만 count 값이 1 이상인 상태에서 1만 줄이면 여전히 구간에 존재하기 때문에 kind는 그대로 유지된다.
처음엔
left++만으로 종류가 줄어들 거라 생각했지만, value가 0이 되어야 Map에서 remove가 일어나며 종류 수 감소가 일어난다.
fruitKind.put(fruits[left], fruitKind.get(fruits[left]) - 1);- 맨 앞 과일의 개수(value) 를 줄이는 작업이다.
- e.g.,
{5=2}→{5=1}
left++;- 구간의 시작 위치를 오른쪽으로 한 칸 이동하는 것
- e.g.,
5 1 1 2 1→1 1 2 1(5가 제거됨)
과일 종류가 2개를 초과했을 때, 이 둘은 같이 실행되어 윈도우를 축소한다.
이 두개가 헷갈려 이해하는데 많은 시간이 소요됐다.
left++는 무조건 반복
과일 개수를 줄이더라도 종류가 여전히 3개이면 left++는 계속 수행되어야 한다.
결국 특정 과일의 개수가 0이 되어야 종류가 감소하고 while을 빠져나올 수 있다.
💻 전체 코드
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());
}
int left = 0;
int maxLan = 0;
// key: 과일 종류, value: 해당 과일의 빈도 수
// e.g., 입력이 5 1 1 2 1일 때 → fruitKind = {5:1, 1:3, 2:1}
HashMap<Integer, Integer> fruitKind = new HashMap<>(); // 과일 종류별 개수 저장
for(int right = 0; right<n; right++){
// 현재 과일 추가 (없으면 0으로 시작해서 +1 해주기)
fruitKind.put(fruits[right], fruitKind.getOrDefault(fruits[right], 0) + 1);
// 과일 종류가 2 초과할경우 -> 왼쪽부터 줄이기
while(fruitKind.size() > 2){
// 현재 구간의 맨 왼쪽 과일 개수 1 감소
fruitKind.put(fruits[left], fruitKind.get(fruits[left]) - 1); // 예: {5:1} → {5:0}
// 개수가 0이 되면 map에서 제거 -> 종류수 감소
if(fruitKind.get(fruits[left]) == 0) fruitKind.remove(fruits[left]); // 예: {5:0} → 제거 → 남은 구간: 1 1 2 1
// 왼쪽 포인터 오른쪽으로 이동 -> 구간축소
left++;
}
// 현재 구간의 최대 길이 갱신
maxLan = Math.max(maxLan, right - left + 1);
}
System.out.println(maxLan);
}
}
댓글남기기