[Java] 백준 30804.과일 탕후루

➡️문제 링크

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

 

💡아이디어

지름길이 있는 문제인가 계속 생각해봐도 아이디어가 안나서 혹시 그냥 완-탐인가 싶어서 알고리즘 유형 확인 해보니

완-탐이었다

 

 

✏️문제 풀이

1.  HashMap-  성공

처음에는 입력받을 때, HashMap도 같이 입력받아야 하나 싶었지만 단순하게 과일 종류별 개수가 아니라, 현재 위치까지 과일의 종류가 몇개 있는지를 판단할 때 쓰는 자료구조라는 걸 깨달았다.

즉, map.size()를 이용해서 과일 종류가 2개 초과인지를 판단하면 되는 거였다.

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [] arr = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i= 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		HashMap<Integer, Integer> hmap = new HashMap<>();	// 과일 종류별 분류 
		int start = 0;
		int result = 0;
		
		for(int end = 0 ; end < N; end++) {
			hmap.put(arr[end], hmap.getOrDefault(arr[end], 0)+1);
			
			while(hmap.size() > 2) {
				// 두 종류 이상 -> 과일 조절 -> 앞에서부터 제거
				hmap.put(arr[start], hmap.get(arr[start])-1);	// 앞의 과일 하나 제거
				if(hmap.get(arr[start]) == 0) hmap.remove(arr[start]);	// 과일 개수 0 -> 해당 과일 삭제
				
				start++;	// 앞의 과일 삭제했으니까, 남아있는 과일중 맨 앞 위치 변경
			}
			
			result = Math.max(result, end-start+1);	
		}
		
		// 정답 출력 
		System.out.println(result);


	}

}

 

 

2. 배열 - 성공

다른 사람들의 풀이를 보다 배열로만으로도 해결할 수 있어 나도 해봤다

문제를 다시 읽어보면 과일의 종류는 1~9까지이므로 이를 배열로 만들어 각 과일의 종류를 인덱스로 해 값을 1씩 증가하면 해당 과일 종류의 개수를  count 할 수 있다.

그렇다면, 현재 종류는 어떻게 판단?

-> 정수형 변수를 선언해서 새로운 과일이 등장할 때 증가하고, 과일의 종류가 초과하는 상황이 발생할 때는 맨 앞에 있는 과일을 감소한 후의 수가 0이라면 그 때는 감소하면 된다.

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

public class Main {

	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int [] arr = new int[N];
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i= 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		int [] count = new int[10];		//과일 종류 카운트
		int curCount = 0;	// 현재 구간 내 과일 종류 수
		int left = 0;
		int result = 0;	// 결과
		
		for(int right = 0 ; right < N; right++) {
			int num = arr[right];	// 현재 과일 종류 
			
			if(count[num] == 0) curCount++;		// 현재 구간에서 아직 등장 하지 않음 -> 증가
			count[num]++;		// 해당 과일 종류에 대해 빈도수 증가
			
			while(curCount > 2) {
				// 두 종류 이상 -> 왼쪽 포인터(left) 이동
				int minusNum = arr[left];
				count[minusNum]--;
				if(count[minusNum] == 0) curCount--;	// 이동한 구간에 해당 값이 존재 X -> 종류 1감소
				
				left++;	// 앞의 과일 삭제했으니까, 남아있는 과일중 맨 앞 위치 변경
			}
			
			result = Math.max(result, right-left+1);	
		}
		
		// 정답 출력 
		System.out.println(result);


	}

}