[백준] 겹치는 건 싫어 - 자바(Java)
문제 링크
https://www.acmicpc.net/problem/20922
문제 설명
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 𝐾개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.
이하의 양의 정수로 이루어진 길이가 𝑁인 수열이 주어진다. 이 수열에서 같은 정수를 𝐾개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.
입력
첫째 줄에 정수 𝑁(1≤𝑁≤200,000)과 𝐾(1≤𝐾≤100)가 주어진다.
둘째 줄에는 𝑎1,𝑎2,...𝑎𝑛이 주어진다 (1≤𝑎𝑖≤100,000)
출력
조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.
문제 풀이
[고려사항]
정수 N은 최대 200,000(20만)이라서 수열의 모든 정수를 돌면서 확인하면 시간초과가 될 것이다.
단순 반복해서 계산하면 안되고, 알고리즘을 사용해야한다.
[알고리즘, 구현방법]
주어진 수열에서 같은 정수를 K개 이하를 포함하는 최장 연속 부분 수열을 찾아야하므로, 두개의 포인터를 두고 조건을 확인해서 구해야한다.
즉, 투 포인터로 푸는 문제이다.
정수를 카운팅하는 배열을 두고 수열을 투 포인터(start, end)를 이용해서 확인한다.
수열의 현재 정수의 개수가 K개를 초과하면 start를 오른쪽으로 한칸씩 옮기면서 부분 수열을 확인한다.
의사코드(pseudocode)로 작성하면 아래와 같다.
while (end 포인터가 수열 원소의 개수(N)보다 작은 경우)
if (end 포인터가 가리키는 정수의 개수가 K개 초과하면)
최장 거리 갱신
while (현재 정수의 개수가 K개 이하가 될 때까지)
start 포인터가 가리키는 정수 개수 1 감소(=부분 수열의 범위를 한칸 옆으로 이동)
부분 수열 길이 1 감소
start 포인터 1 증가
else
현재 정수(=end 포인터가 가리키는) 개수 1 증가
부분 수열 길이 1 증가
최장 거리 갱신[풀이 과정]
1. 입력 값 세팅 및 수열 정수의 개수 배열 생성(int[] cnt)
2. end 포인터가 n 이상이 될때까지 반복
- 현재 수열의 숫자가 연속으로 K개 초과한 경우,
- 최장 거리 갱신
- 현재 숫자가 K개 이하가 될 때까지
- start 포인터 이동(=부분 수열의 시작 부분 이동)
- 수열 길이 1 감소 & start 포인터가 가리키는 정수의 개수 1 감소(부분 수열의 범위가 옆으로 한칸 이동하기 때문)
- K개 초과하지 않은 경우
- 현재 숫자 개수 1 증가
- 부분 수열 길이 1 증가
3. 마지막 갱신된 부분 수열의 길이를 고려하여 최장 거리 갱신 후 정답 출력
정답 코드
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine(), " ");
int[] sequence = new int[n];
for (int i=0; i<n; i++) {
sequence[i] = Integer.parseInt(st.nextToken());
}
// 숫자 개수 배열
int[] cnt = new int[100001]; // 숫자는 최대 100_000
int start = 0;
int end = 0;
int answer = 0;
int max = 0;
while (end < n) {
if (cnt[sequence[end]] + 1 > k) { // 하나의 숫자가 연속 k개 초과
if (max < answer) max = answer; // 최장 거리 갱신
// while (sequence[start] != sequence[end]) { // 1개가 늘어서 연속 k개 초과했으므로, start가 end 숫자랑 같아질때까지 이동시키기
while (cnt[sequence[end]] + 1 > k) { // 현재 숫자가 k개 이하가 될 때까지 start 이동
cnt[sequence[start]]--; // start 숫자 제외
answer--; // 수열 길이 -1
start++; // start pointer +1
}
} else { // 초과 하지 않는 경우, 1) 현재 숫자 카운팅 & 2) 숫자 연속 길이 증가
cnt[sequence[end++]]++;
answer++;
}
}
if (max < answer) max = answer; // 마지막 갱신된 길이를 고려하여 최종 max 값 갱신
System.out.println(max);
}