https://www.acmicpc.net/problem/20922
사용 알고리즘
- 투 포인터
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n, k; // n: 정수 , k: k개 이하 겹치는 수
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());
k = Integer.parseInt(st.nextToken());
int [] arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int hi = 0;
int result = 0;
int[] counts = new int[100002];
for(int lo = 0; lo < n; lo++) {
while(hi < n && counts[arr[hi]] < k) {
counts[arr[hi]]++;
// System.out.println(arr[hi] + " " + counts[arr[hi]]);
hi++;
}
// 같은 원소 갯수가 K가 넘을 때 루프를 빠져나온다
result = Math.max(result, hi - lo);
counts[arr[lo]]--;
}
System.out.println(result);
}
}
회고
같은 원소를 K개 이하일 때 체크하는 자료구조를 뭐를 써야하지? 에서 고민이 많았다.
- 맵을 사용하여 등장 횟수를 저장
- 리스트를 사용하여 contains 일 때 등장 횟수를 증가시켜줌
리스트를 사용한 방식은 특정 원소에 대한 등장 횟수를 계산할 수 없기 때문에 틀린 방식이다. 맵을 사용하는 방식은 생각 자체는 옳았으나 계산 과정에 있어서 로직이 틀렸어서 남의 코드를 보고 배열로 풀이하게 되었다.
기존 코드에선, 루프를 빠져 나왔을 때
if (hi == n) break;
counts[arr[hi]]--;
이런식으로 로직을 구현해서 OOB에러가 발생하지 않도록 설정했는데,
10 1
1 1 2 1 2 1 3 4 5 6
이 예제 케이스에 대해서 돌려보면 최장 수열은 [2,1,3,4,5,6]라서 답은 6인데, 2가 나오게 된다.
while 문 안에서 hi가 n-1인 동안 동작하고, n이 된 순간 루프를 빠져 나온다.
그런데, 루프 밖에서 hi == n일 때 break를 터트려버리기 때문에 마지막 원소까지 도달하지 못하는 것이다.
그렇기 때문에 break 조건을 없애주고, 등장 횟수를 줄여주는 인덱스를 hi가 아닌 lo로 설정해야한다.
counts[arr[lo]]--;
시작점이 어떻게 변하는지, 또 원소의 등장 횟수를 어떻게 감소시킬 것인지 생각을 더 깊게 해야겠다.
'Algorithm > 백준' 카테고리의 다른 글
[백준] Gold IV. 합이 0 (0) | 2024.07.20 |
---|---|
[백준] Gold V. 가장 긴 짝수 연속한 부분 수열 (large) (0) | 2024.07.19 |
[백준] Gold V. 입국 심사 (0) | 2024.07.15 |
[백준] Silver II. 랜선 자르기 (0) | 2024.07.12 |
[백준] Silver III. 선분 위의 점 (0) | 2024.07.10 |