시간초과 코드
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws NumberFormatException, 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());
int[] arr = new int[n];
int[] check = new int[100001];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int start = 0;
int end = 1;
int count = 1;
int max = 0;
check[arr[start]]++;
while(true) {
check[arr[end]]++;
if(check[arr[end]] <= k) {
end++;
count++;
max = Math.max(count, max);
}
else if(check[arr[end]] > k) { //예외
start=end+1;
max = Math.max(count, max);
count=1;
}
if(end==n-1 || start==n-1) break;
}
System.out.println(max);
}
}
각 숫자가 등장한 횟수를 체크하는 check 배열 사용.
IDE에서는 잘 나왔지만 시간초과가 발생했다. 시작점인 start를 불필요하게 갱신하며, end의 범위 설정에 문제가 있다.
개선된 코드(투포인터)
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws NumberFormatException, 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());
int[] arr = new int[n];
int[] check = new int[100001];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
int start = 0, end = 0, max = 0;
while(end < n) {
if(check[arr[end]] < k) {
check[arr[end]]++;
end++;
} else {
check[arr[start]]--;
start++;
}
max = Math.max(max, end - start);
}
System.out.println(max);
}
}
현재 end 위치의 숫자가 k번을 초과하면, start 위치의 숫자 등장 횟수를 줄이고 start를 오른쪽으로 이동시킨다.
그리고 end-start로 수열의 최대 길이를 갱신시켜줌.
'Algorithms > study log' 카테고리의 다른 글
[Graph+BFS] 백준 7576 토마토 (0) | 2024.04.14 |
---|---|
그래프 이론 톺아보기 (0) | 2024.04.14 |
[백트래킹] 눈덩이 굴리기, 근손실, 1,2,3 더하기 2 (1) | 2024.04.07 |
[Greedy] 백준 2141 우체국 (0) | 2024.03.19 |
[Greedy] 연속되는 조건이 있는 문제 (1) | 2024.03.17 |