[백준] 30804 과일 탕후루 - 투포인터(Two Pointer) JAVA

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

코드설명

투포인터(Two Pointer)  를 활용합니다.

 

처음에 문제를 보고, 어떻게 접근해야할지 감이 오지 않았습니다.

 

우선 N은 2 * 10^5 로써, O(N^2)의 시간복잡도라면 시간초과가 발생함을 알 수 있습니다.

그렇기에, 떠오른 아이디어는

1. 분할정복

2. 투포인터

3. 정렬 ??

 

과 같은 아이디어가 떠올랐습니다.

투포인터를 사용하는것인가? 라고 의심은 했지만, 막대의 앞쪽과 뒤쪽에서 빼야한다는 관점에서 투포인터 방식을 맨 앞, 맨 끝 을 기준으로 가운데로 실제로 좁혀나가는 과정을 거쳐야하나? 라는 생각이 들었습니다.

하지만, 만약 양끝에서 가운데로 오면서 최적화 방안을 찾기는 불가능합니다. 이유는 어떨 떄 오른쪽에서 과일을 뺴고, 어떨떄 왼쪽에서 과일을 뺴야하는지 판단이 불가능하기 때문입니다.

처음에는 해당 아이디어가 떠오르지 않아 어쩔 수 없이 분할정복으로 방향을 틀었습니다.

하지만, 분활정복으로도 여전히 왼쪽에서 과일을 뺴야하는지 오른쪽에서 뺴야하는지의 기준이 필요합니다. 결국 이 분할정복도 완전탐색으로 구현하면 시간초과가 발생하기 때문입니다.

 

투포인터를 사용할 수 있었던 이유는, 탕후루를 만들떄 막대의 앞쪽과 뒤쪽에서 몇 개의 과일을 빼기 떄문입니다.

이떄 중요사항은 막대의 앞쪽과 뒤쪽이라는 점이지요.

만약 10개의 과일 중 앞에서 연속 과일 4개가 선택되었다면, 뒤쪽에서 과일 6개를 뺐다고 생각하면 되는 것 입니다.

 

이 문제를 어떻게 풀어야할지 떠올리는게 상당히 어려웠던 문제입니다.

코드

투포인터를 활용한 코드입니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, P, K, A, B, X, R;
	static int answer = 0;
	static int[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		solve();
		System.out.println(answer);
	}
	
	static void solve() {
		HashMap<Integer, Integer> hashmap = new HashMap<Integer, Integer>();
		HashSet<Integer> hashset = new HashSet<>();
		int left = 0;
		int right = 0;
		int ret = 0;
		
		//right를 오른쪽으로 한칸씩 옮겨가면서 탕후루를 만든다.
		while(right < N) {
			hashmap.put(arr[right], hashmap.getOrDefault(arr[right], 0) + 1);
			hashset.add(arr[right++]);
			ret += 1;
			
			//만약 right를 더했는데 size가 2보다 크다면, left를 오른쪽으로 옮긴다.
			//이떄 중요사항은, left를 제거하며 hashset이 <= 2 이하가 될떄까지 계속해서 옮겨야 한다는 것 이다.
			if(hashset.size() == 3) {
				while(hashset.size() > 2) {
					hashmap.put(arr[left], hashmap.get(arr[left]) - 1);
					if(hashmap.get(arr[left]) == 0) {
						hashset.remove(arr[left]);
						hashmap.remove(arr[left]);
					}
					left += 1;
					ret -= 1;
				}
			}
			answer = Math.max(answer, ret);
		}
		
	}
}

처음에 분할정복으로 접근한 코드입니다.

이때는 양옆에서 짜르는 것이 아닌 가운데에서 선택하는 것을 생각했습니다.

하지만, 역시나 과일을 mid부분에서 오른쪽으로 갈지 왼족으로 갈지 기준이 없습니다.

package Main;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Main {
	static int N, M, S, P, K, A, B, X, R;
	static int answer = 0;
	static int[] arr;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		System.out.println(answer = divideAndConquer(0, N-1));
		System.out.println("answer:"+answer);
		
	}
	
	//병합정렬을 쓸까, 아니면 퀵정렬을 슬까.
	static int divideAndConquer(int left, int right) {
		if(left == right) {
			return 1;
		}
		
		int ret = 0;
		int mid = (left + right) / 2;
		ret = Math.max(ret, divideAndConquer(left, mid));
		ret = Math.max(ret, divideAndConquer(mid + 1, right));

		System.out.println("left:"+left+"right:"+right);
		//가운데 연산.
		HashSet<Integer> hashset = new HashSet<>();
		int leftPos = mid - 1;
		int rightPos = mid + 1;
		hashset.add(mid);
		int cnt = 0;
		while(leftPos >= left && rightPos <= right) {
			for(int v : hashset) {
				System.out.print(v+" ");
			}
			
			if(hashset.size() <= 2) {
				hashset.add(arr[leftPos--]); cnt += 1;
			}
			if(hashset.size() > 2) {
				cnt -= 1; break;
			}
			if(hashset.size() <= 2) {
				hashset.add(arr[rightPos++]); cnt += 1;
			}
			if(hashset.size() > 2) {
				cnt -= 1; break;
			}
		}
		
		while(leftPos >= left) {
			for(int v : hashset) {
				System.out.print(v+" ");
			}
			if(hashset.size() <= 2) {
				hashset.add(arr[leftPos--]); cnt += 1;
			}
			if(hashset.size() > 2) {
				cnt -= 1; break;
			}
		}
		while(rightPos <= right) {
			for(int v : hashset) {
				System.out.print(v+" ");
			}
			if(hashset.size() <= 2) {
				hashset.add(arr[rightPos++]); cnt += 1;
			}
			if(hashset.size() > 2) {
				cnt -= 1; break;
			}
		}
		
		
		return cnt; 
	}
}