백준 16472 JAVA : 고냥이
문제
https://www.acmicpc.net/problem/16472
16472번: 고냥이
고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고
www.acmicpc.net
풀이 예상
투포인터를 이용해서 startPoint와 endPoint의 차이로 길이를 구한다.
풀이방법 (접근 방법 & 시간복잡도)
1. isHave[] 배열에 해당 알파벳이 나오면 수를 증가시킨다. a(0), b(1), c(2), ...
2. count(알파벳 종류의 개수) 가 N개 보다 적다면 endPoint를 늘리고 처음 나온 알파벳이라면 count도 +1해준다.
3. count(알파벳 종류의 개수) 가 N개이고 endPoint가 이미 나온 알파벳이라면 endPoint 를 +1 해준다.
4. count(알파벳 종류의 개수) 가 N개이고 endPoint가 처음 나온 알파벳이라면 startPoint를 +1 해준다.
예제를 예시로 들어보면,
2
abbcaccba
1. 초기 세팅
startPoint, endPoint = 0, count = 0, answer = 0
2. while문 - 1
startPoint = 0, endPoint = 1, count = 1, answer = 1
3. while문 - 2
startPoint = 0, endPoint = 2, count = 2, answer = 2
4. while문 - 3
startPoint = 0, endPoint = 3, count = 2, answer = 3
5. while문 - 4
startPoint = 1, endPoint = 3, count = 1, answer = 3
6. while문 - 5
startPoint = 1, endPoint = 4, count = 2, answer = 3
...
위의 로직대로 코드를 짜면 아래와 같다.
시간복잡도 => O(N)
startPoint와 endPoint는 한번의 반복으로 최대 N까지 이동한다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[] isHave = new int[26];
String str = br.readLine();
int startPoint = 0;
int endPoint = 0;
int count = 0; //알파벳 종류 개수
int answer = 0;
while(true) {
int endNum = str.charAt(endPoint)-'a';
int startNum = str.charAt(startPoint)-'a';
if(count < N) {
if (isHave[endNum] == 0) {
//가지고 있지 않은 경우
count++;
}
answer = Math.max(answer, endPoint - startPoint+1);
endPoint++;
isHave[endNum] +=1;
}else if(isHave[endNum] > 0) {
//다음 문자가 이미 나온 문자이면
answer = Math.max(answer, endPoint - startPoint+1);
endPoint++;
isHave[endNum] +=1;
}else {
//startPoint를 증가
if(isHave[startNum] == 1) {
count--;
}
isHave[startNum] -= 1;
startPoint++;
}
if(endPoint == str.length()) {
break;
}
}
System.out.println(answer);
}
}
결과
