백준 16472 JAVA : 고냥이

문제

https://www.acmicpc.net/problem/16472

16472번: 고냥이

 

풀이 예상

투포인터를 이용해서 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);

    }
}

 

 

결과