문제
https://www.acmicpc.net/problem/6503
문제해설
상근이는 망가진 키보드를 가지고 있다.
사용할 수 있는 키보드 키는 m개이고 상근이는 키보드 레이아웃을 바꿀 수 있다.
상근이가 입력하려는 문장이 주어질 때
키보드 레이아웃을 바꾸지 않고 입력할 수 있는 문자의 최댓값을 구하면 된다.
문제풀이
처음에 문제를 봤을 때는 dp인줄 알았다.
그러다 코딩을 하려고 생각해보니 투포인터라는 걸 알아챘다.
투포인터 알고리즘에 대한 설명은 투포인터 알고리즘 에 들어가서 확인하면 된다.
시작전에 서로다른 최대 128개의 문자가 올 수 있다고 했기 때문에 128크기의 check 배열을 생성했다.
문자열을 입력받고 앞에서부터 투포인터를 시작한다.
그리고 현재 본 문자의 개수를 담은 cnt가 n보다 작다면 right를 증가시킨다.
새로 본 문자가 새로 본 문자라면 cnt를 증가시키고 아니라면 check 배열만 업데이트한다.
cnt가 n보다 크다면 left를 증가시키고 그 전 문자를 check에서 뺀다.
주의할 점은 cnt가 n과 같을 때 무조건 left를 증가시키면 안된다.
새로 볼 문자가 이미 봤던 문자라면 right를 증가시켜야 하기 때문이다.
그 부분만 주의하면서 right가 끝까지 갈때까지 탐색하며
right-left값으로 최대값을 갱신시켜주면 정답이 나온다.
전체코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static int n;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while (true) {
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
if (n == 0) break;
String arr = br.readLine();
int[] check = new int[128];
int right = -1, left = -1, cnt = 0, res = 0;
while (left <= right) { // 투포인터 알고리즘
if (cnt < n || (cnt == n && check[arr.charAt(right + 1)] > 0)) {
right++;
check[arr.charAt(right)]++;
if (check[arr.charAt(right)] == 1)
cnt++;
} else {
left++;
check[arr.charAt(left)]--;
if (check[arr.charAt(left)] == 0)
cnt--;
}
res = Math.max(right - left, res);
if (right == len - 1)
break;
}
System.out.println(res);
}
br.close();
}
}