[백준] 16472번 고냥이 JAVA 풀이 + 해설

백준 16472번 고냥이 JAVA 풀이 및 해석

문제

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

16472번: 고냥이

문제 요약

인식할 수 있는 알파벳 개수 N 개와 알파벳 소문자로 이루어진 문자열이 입력으로 들어온다. 이때, N개의 알파벳으로 이루어진 부분 문자열 중 최대인 것의 길이를 구하여라.

 

문제 입출력

 

문제 접근1

이중 for문으로 start와 end를 반복 순회한다. start가 0일 때 end 는 1,2,3 ..... 문자열의 길이까지 돌면서 N개의 알파벳을 갖는 최대 길이의 문자열을 확인한다.

start: 0 - end: 0,1,2,3, .... string length()

start: 1 - end: 1,2,3, ...string length ()

start: string length() - end: string length()

 

시원~~하게 시간초과가 난 이중 for문 로직 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N;
//    static char[] alphas;
    static boolean[] selected;
    public static void main(String[] args) throws IOException {
        BufferedReader br=  new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String alpha = br.readLine();
        int start_idx=0;
        int end_idx=alpha.length();
        int count=0;
        int max_result =0;
        if(N>=alpha.length()) {
            System.out.println(alpha.length());
            return;
        }
        for(int i=0; i<alpha.length(); i++){
            start_idx=i;
            selected = new boolean[26];
            for(int j=start_idx; j<alpha.length(); j++){
                if(count>N){
                    end_idx = j - 1;
                    count=0;
                    break;
                }
                int idx = alpha.charAt(j) - 'a' ;
                if(!selected[idx]){
                selected[idx]= true;
                count++;
                }
            }
            max_result= Math.max(max_result,end_idx-start_idx);
        }
        System.out.println(max_result);
    }
}

78% 에서 시간초과가 발생했으며, 실제로 문제의 최대 input인 10만 길이의 문자열을 넣어보니 대략 10초 정도 걸렸다. ..

그래서 시간을 단축하기 위해 문제를 파악해보았다.

 

 시간초과 문제 파악

이중 for문을 사용하면 아래와 같이 동작한다. 

1

2

3

4

5 ( 4번째 동작에서 알파벳의 종류가  N=2 를 넘었기 때문에 1번 인덱스로 돌아가서 수행)

6

7

보시다시피, 이미 첫번째 반복에서 이미 bbc 를 선택했는데, 두번째 반복에서 이를 다시 하나씩 선택해주어야 한다.

이런 문제가 로직을 무겁게 만들었을 것이라 생각한다.

 

문제 접근 2

이를 해결하기 위해 아래와 같은 방법을 구상했다.

1,2,3

4

5

한 번 선택했던 것들을 뭉탱이로 갖고 있도록 한다. 

 

우선 start, end 라는 두 개의 포인터가 필요했다. start는 시작점, end는 끝점으로, 끝점이 가리키는 알파벳이 새로운 알파벳이고, N 값을 넘어가는 경우에 start와 count를 1 증가시키도록 한다.

이때, 현재 start ~ end 까지 어떤 알파벳이 몇 개나 문자열에 속해있는지 알기 위해서 사이즈가 26인 1차원 배열을 생성한다. 이 배열에 a -> 0, b-> 1 c->2 .... z -> 25 인덱스로 치환하여, 알파벳 a 가 들어오면 v[0] = v[0] + 1 을 해준다. 

bbca 의 경우처럼, start를 1 증가시키고, 배열에서 시작점인 알파벳 b의(v[1]) 값을 하나 줄이더라도 문자열에 b가 또 존재하는 경우는 count를 올리지 않는다. 이 과정을 끝점이 문자열의 끝에 도달할 때 까지 반복한다.

그리고 시작점이 0이고 끝점이 문자열의 끝인 경우, 모든 문자열을 인식할 수 있는 것이기 때문에 문자열의 length를 출력한다. ( 이 경우에는 if(count==N) 에 도달할 수 없어서 result가 0이다.)   

전체코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    static int N;
    static int[] selected;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        String alpha = br.readLine();
        int start=0;
        int end=1;
        int result =0;
        int count=0;

        selected = new int[26];
        int st =alpha.charAt(0) - 'a'; //start 인덱스 설정, alpha의 0번째 알파벳이 a 라면 st는 0, b라면 1 ....
        count++; //start 알파벳을 지정했으니 count = 1
        selected[st]++; // 시작 알파벳의 개수를 1개 늘림

        while(end<alpha.length()) { //문자열의 끝에 도달할 때 까지 반복
            if(count==N){ //만약 인식할 수 있는 알파벳을 최대로 포함중이라면
                if(result<end-start){
                    result = end-start;
                }
            }
            if(count>N){ //N개의 알파벳을 이미 쓰고 있는데 새로운 알파벳이 선택됐다면
                int d_idx = alpha.charAt(start) - 'a'; //시작점의 알파벳 인덱스 가져오기
                selected[d_idx]--; //시작점의 알파벳 개수를 하나 줄임
                if(selected[d_idx]==0){ //하나를 줄임으로써 더는 그 알파벳이 포함되지 않는다면
                    count--; //사용중인 알파벳 개수를 줄임
                }
                start++; //시작점 포인터를 한 칸 옮김
                continue;
            }
            int idx = alpha.charAt(end) - 'a'; //끝점의 인덱스 설정

            if(selected[idx] == 0){ //만약 끝점의 알파벳이 처음 등록되는 알파벳이라면
                count++; //사용 개수 늘려줌
            }
            selected[idx] ++; //알파벳 포함 개수 늘려줌
            end++; //끝점 포인터 한칸 옮김
        }
        //로직 끝
        if(start==0 && end==alpha.length()){ //만약 start가 0이고, end가 alpha의 길이라면 들어온 문자열의 길이를 모두 인식할 수 있는 경우
            System.out.println(alpha.length());
        }
        else System.out.println(result);
    }
}