728x90
알고리즘 스터디 (투포인터)
https://www.acmicpc.net/problem/20922
# 문제
홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K 개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다.
100000 N 인 수열이 주어진다. 이 수열에서 같은 정수를 K 개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자.
이하의 양의 정수로 이루어진 길이가
# 예제
입력 :
첫째 줄에 정수 N (1≤N≤200000 )과 K (1≤K≤100 )가 주어진다.
둘째 줄에는 a1,a2,...an 이 주어진다 (1≤ai≤100000 )
9 2
3 2 5 5 6 4 4 5 7
출력 : 조건을 만족하는 최장 연속 부분 수열의 길이를 출력
7
# 필요개념
투포인터는 start와 end 두 개의 지점에서 일정 조건에 따라 이동하며 문제를 해결하는 방식이다. 해당 문제도 투포인터를 이용하여 풀 수 있다.
신경쓸 조건은 두가지이다.
- 같은 원소가 몇개 들어있는가
- start와 end의 위차가 배열길이를 넘어는가
이 두 가지 조건에 걸리지 않으면 end를 한 칸씩 이동시키고, 해당 위치의 원소 개수를 카운트한다.
만약 조건에 걸린다면, 길이를 측정한다.
start가 1, end가 4라면 길이가 3인 수열이 되는 것이다. 길이는 계속 길이의 최대값을 따로 저장해 나가며 되고, 다시 위 두 가지 조건을 만족할 때까지 start를 한 칸씩 이동시킨다. 쉽게 말하면 end 위치에 있는 값과 같은 값이 나올 때까지 start를 이동시키면 되는 것이다.
# Code
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int limit = Integer.parseInt(st.nextToken());
int[] inputs = new int[N];
int[] cnt = new int[100001];
st = new StringTokenizer(br.readLine());
for (int i = 0 ; i < N ; i++) {
inputs[i] = Integer.parseInt(st.nextToken());
}
int start = 0;
int end = 0;
int max = -1;
while (end < N) {
while (end < N && cnt[inputs[end]] < limit) {
cnt[inputs[end]]++;
end++;
}
int length = end - start;
max = Math.max(max, length);
cnt[inputs[start]]--;
start++;
}
System.out.println(max);
}
}
# 결과
'코딩테스트 > 백준 브론즈,실버' 카테고리의 다른 글
[백준] 2193: 이친수 (DP) - JAVA (1) | 2024.09.08 |
---|---|
[백준] 11727: 2×n 타일링 2 (DP) - JAVA (1) | 2024.09.07 |
[백준] 1309: 동물원 (DP) - JAVA (1) | 2024.08.23 |
[백준] 1495: 기타리스트 (DP) - JAVA (0) | 2024.08.22 |
[백준] 1660: 캡틴 이다솜 (DP) - JAVA (0) | 2024.08.22 |