문제
시간 제한 : 1초, 메모리 제한 : 512MB
고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다.
현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다.
고양이와 소통할 수 있도록 우리도 함께 노력해보자.
인식할 수 있는 알파벳 종류의 최대 개수 N
입력
N
문자열(알파벳 소문자만 포함)
인식할 수 있는 알파벳의 종류(N)가 2개인 경우, abbcaccba라는 문자열에서는 'cacc'가 알파벳 종류 2개만을 지닌 최대 문자열의 길이이다.
풀이
포인터 두 개를 사용하여 start, end 따로 늘려가며 진행하면 될 것 같다.
start = 0; end = 0; max = 0;
while end가 문자열의 길이보다 작은 동안
map에 문자열[end]의 값이 없는 경우 새롭게 추가
이후 map의 사이즈(알파벳 종류)가 N보다 크면 start를 늘려야 하므로
while map.size()>N && start<end
map.get(key)의 값 == 1이면 remove, 아니면 -1, start++;로 map.size()<=N이 될 때까지 반복한다.
이후 map.size() <= N이 되면 max = Math.max(max, end-start+1)로 max의 값을 구한다.
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String str = br.readLine();
HashMap<Character, Integer> map = new HashMap<>();
int start = 0;
int end = 0;
int max = 0;
while(str.length() > end) {
char curr = str.charAt(end);
map.put(curr, map.getOrDefault(curr, 0) + 1);
while(map.size() > N && start < end) {
if(map.get(str.charAt(start)) == 1) { // 현 start의 알파벳이 1개 있으면
map.remove(str.charAt(start)); // 해당 알파벳을 map에서 제거
} else {
map.put(str.charAt(start), map.get(str.charAt(start))-1); // 아닌 경우 해당 알파벳을 한 개 줄인다
}
start++;
}
max = Math.max(end-start + 1, max);
end++;
}
System.out.print(max);
}
}while문 안에 while문이 또 있어 시간 초과가 날 것 같지만, 슬라이딩 윈도우 알고리즘을 사용하면 O(n^2)가 아니다. start, end 포인터가 문자열을 한 번씩만 순회하므로 전체 시간 복잡도가 O(n)이다.
문제를 풀며
처음에 map.size() < N일 때는 답이 아니라 생각하고, start++와 end++의 위치를 잘못 두는 등 때문에 몇 번 틀렸다...
그리고 hashMap 너무 좋아하는 것 같다.. alphabet은 개수가 정해져있으니 배열로 풀어볼까 했는데... .size()로 개수를 구하고 싶어서 포기하지 못 했다. 만약 배열로 푼다면 풀이는 이렇게...
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
String str = br.readLine();
int[] alphabet = new int[26];
Arrays.fill(alphabet, 0); // 초기화
int start = 0;
int end = 0;
int max = 0;
int count = 0; // 종류를 세는 변수
while(str.length() > end) {
char curr = str.charAt(end);
if(alphabet[curr-'a'] == 0) count++; // 0이면 종류 한 개 추가된 거니 ++;
alphabet[curr-'a']++; // 배열 내의 값 증가
while(count > N && start < end) {
if(--alphabet[str.charAt(start++)-'a'] == 0) {
// alphabet[start]의 값을 하나 빼서 0일 때
count--;
}
}
max = Math.max(end-start + 1, max);
end++;
}
System.out.print(max);
}
}이렇게 쓰고 보니 배열이 훨씬 간단하잖아??...
배열을 아껴줘야겠다...