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; } }
'알고리즘 > Two Pointer' 카테고리의 다른 글
[백준] 1522 문자열 교환 - 슬라이딩 윈도우(Sliding Window) JAVA (0) | 2024.09.25 |
---|---|
[백준] 14465 소가 길을 건너간 이유 5 - 투포인터(Two Pointer) JAVA (0) | 2024.09.06 |
[백준] 12891 DNA 비밀번호 - 투포인터(Two Pointer) JAVA (0) | 2024.09.04 |
[LeetCode] 88. Merge Sorted Array - Two Pointer(투포인터) JAVA (0) | 2023.12.23 |
[백준] 2473 세 용액 - 투포인터(Two Pointer) JAVA (0) | 2023.11.13 |