https://www.acmicpc.net/problem/30804
문제 요약
1부터 9까지의 번호가 배정된 과일이 N개 꽂혀있는 과일 탕후루가 있다.
과일을 두 종류 이하로 남기기 위해 탕후루의 앞에서 a개, 뒤에서 b개를 빼기로 했다.
이렇게 만들어질 수 있는 탕후루 중에서 과일 개수가 가장 많은 것의 과일 개수를 구하여라.
과일의 개수 N은 최대 20만이다.
과일 번호는 1 이상 9 이하다.
a와 b는 0 이상, a+b는 N 미만이다.
문제 접근
일단 시간복잡도부터 확인하면 N이 최대 20만이니까 까지 가능하다.
느낌적으로는 문제 상황을 보면 의 알고리즘을 안 쓰고 선형으로 한 번 쭉 훑는 으로 풀 수 있을 것 같다는 생각이 들었다.
내가 떠올린 접근법은 완전 탐색의 방법이었다.
탕후루를 만들 수 있는 과일 종류의 경우를 모두 만들고, 각 경우에 대해 배열을 훑으면서 가능한 최대 길이를 얻는 방식이다.
과일의 전체 종류가 9가지이고, 과일의 종류를 2가지 이하만 허용하기 때문에 9개 중에 2개를 선택하는 경우는 36가지 밖에 없어서 가능하다고 생각했다.
첫번째 풀이: 완전탐색
기본적인 아이디어는 다음과 같다.
- 가능한 과일 쌍의 경우를 모두 만들어 놓는다.
- 각 과일 쌍에 대해 배열을 훑으며 해당 과일들로 가능한 최대 길이를 기록한다.
이를 구현한 코드는 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력 받기
int N = Integer.parseInt(br.readLine());
int[] fruits = new int[N];
StringTokenizer stFruit = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
fruits[i] = Integer.parseInt(stFruit.nextToken());
}
// 가능한 과일 쌍을 모두 포함하는 리스트
ArrayList<int[]> fruitPair = new ArrayList<>();
for (int i = 1; i <= 9; i++) {
for (int j = i+1; j <= 9; j++) {
int[] nowPair = {i, j};
fruitPair.add(nowPair);
}
}
// 가능한 과일 쌍을 모두 훑으며 가장 긴 경우를 찾는다.
int answer = 0; // 정답(최대 길이)
for (int[] nowPair : fruitPair) {
int nowLength = 0;
for (int idx = 0; idx < N; idx++) {
// 과일 쌍에 포함된 경우 길이를 증가한다.
if (fruits[idx] == nowPair[0] || fruits[idx] == nowPair[1]) {
nowLength++;
}
// 과일 쌍에 포함되지 않은 경우 현재 길이를 비교하고 0으로 초기화
else {
answer = Math.max(answer, nowLength);
nowLength = 0;
}
// 마지막 인덱스인 경우 현재 길이를 또 비교해본다.
// 이는 과일 쌍에 포함된 경우로 끝나는 경우를 방지한다.
answer = Math.max(answer, nowLength);
}
}
System.out.println(answer);
}
}두번째 풀이: 투 포인터
혹시 앞선 방식이 정석 풀이인가 싶었는데, 찾아보니 역시 아니었다.
완전 탐색 풀이는 과일의 종류가 9가지가 아니라 매우 많은 경우였다면 적용할 수 없다는 문제가 있다.
투 포인터를 사용한다는 힌트를 얻었는데, 이를 어떻게 사용할 지가 문제다.
일단 투 포인터는 서로 다른 양쪽 끝에서 시작하는 방법과 같은 쪽에서 시작해서 속도를 다르게 하는 방법이 있는데, 이 문제는 당연히 동시에 시작하는 속도가 다른 투 포인터를 사용해야 할 것 같다.
그런데 현재 과일의 종류가 몇 개인지 어떻게 인식할까??
해답은 각 과일의 개수를 HashMap에 저장하는 것이었다.
여태까지 계속 과일의 위치, 인덱스에 꽂혀 있었는데, 그냥 개수가 0이 되면 해당 과일이 없는 거니까 과일의 종류를 알 수 있게 된다.
기본적인 아이디어는 다음과 같다.
- left와 right라는 투 포인터는 처음 index 0에서 같이 시작한다.
- 과일의 종류가 2가지가 넘지 않으면 right를 오른쪽으로 이동한다.
- 과일의 종류가 2가지가 넘으면 left를 오른쪽으로 이동하며 2가지가 넘지 않도록 한다.
- 이러한 과정에서 최대 길이를 꾸준히 기록한다.
이를 구현한 코드는 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 입력 받기
int N = Integer.parseInt(br.readLine());
int[] fruits = new int[N];
StringTokenizer stFruit = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
fruits[i] = Integer.parseInt(stFruit.nextToken());
}
// 사용할 변수와 자료구조 선언
int left = 0; // 왼쪽 포인터
int right = 0; // 오른쪽 포인터
int answer = 0; // 정답(최대 길이)
// 현재 포함된 각 과일의 개수
HashMap<Integer, Integer> numFruit = new HashMap<>();
// 먼저 index 0의 값은 추가해놓음
numFruit.put(fruits[left], 1);
// right가 N을 넘기 전까지 진행
while (right < N) {
// right 올리기
right++;
// 마지막 인덱스에 도달한 경우 처리
if (right == N) {
int nowLen = right - left;
answer = Math.max(answer, nowLen);
break;
}
// 과일 개수 1 더한 값으로 갱신 또는 추가
int numRight = numFruit.getOrDefault(fruits[right], 0) + 1;
numFruit.put(fruits[right], numRight);
// 과일 개수가 2개를 넘는다면 넘지 않을 때까지 left 이동으로 처리
while (numFruit.size() > 2) {
// 최대 길이 기록
int nowLen = right - left;
answer = Math.max(answer, nowLen);
// 해시맵에서 개수 낮추기
int numLeft = numFruit.get(fruits[left]) - 1;
// 만약 0이 되면 아예 지움
if (numLeft == 0) numFruit.remove(fruits[left]);
// 아니면 기록
else numFruit.put(fruits[left], numLeft);
left++;
}
}
System.out.println(answer);
}
}회고
투 포인터에서 보통 고민되는 점은 두 가지가 있는데, left가 right를 역전하는 경우, 그리고 right가 전체 길이를 넘어가는 경우이다.
이 문제에서는 조건 상 전자는 나타나지 않지만, 전체 길이를 넘어가는 경우를 처리하는 것이 살짝 까다로웠다.
또 이 문제에서는 반복문에서 시작점을 고려하지 않았기 때문에 임의로 index 0의 값을 추가했어야 했다.... 바로 생각하지 못했던 내용.
