[백준] 고냥이 16472 - JAVA

1. 문제

 

 

2. 접근

이 문제는 알파벳 N개를 사용해서 최대 연속된 문자열의 길이를 구하는 것이다. 처음에 N이 2로 고정된 줄 알고 완탐 돌릴려고 했는데 1부터 26까지 주어지는 것이었다.

 

그래서 생각한 아이디어는 set과 투 포인터를 이용한 풀이었다. 중복이 허용되지 않는 set으로 알파벳을 저장하고 set의 사이즈가 N을 넘어가면 사이즈가 N이 될 때가지 빼주면 되겠구나 했다. 

 

하지만 'cacc' 처럼 c가 연속적으로 나오지 않는 경우를 고려하지 못한 풀이였다. 단순히 c를 만나면 다음 문자열이 c가 아닐 때까지 빼주고 c를 set에서 삭제했더니 a 뒤에 나오는 cc를 삭제하지 않고 있었다.

 

그래서 `HashMap`을 이용해서 카운팅한 문자의 카운트를 저장하고, 값이 0이 될 때 map에서 삭제해주었다. 이렇게 풀니 맞았는데 생각해보니 알파벳의 개수는 26개로 정해져 있으니 무거운 map보다는 1차원 배열로 카운트 값을 저장하는 걸로 바꿨다.

 

배열과 HastMap 이용했을 때 차이

 

메모리와 수행 시간이 꽤 차이가 난다.

 

3. 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.HashSet;


class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {

        int N = Integer.parseInt(br.readLine());
        String str = br.readLine();

        int start = 0;

        // init
        int maxCount = 0;
        int curCount = 0;

        int selectCount = 0;
        int [] alphas = new int[27];


        for(int end =0; end < str.length(); end++){
            char endChar = str.charAt(end);

            // 새로운 문자인지 확인
            if(alphas[endChar -'a'] == 0){
                selectCount++;
            }
            // 현재 문자를 추가
            alphas[endChar -'a']++;
            curCount++;

            // 서로 다른 문자가 N+1일 때 N개가 될 때까지 빼기
            while(selectCount > N){
                char removeAlpha = str.charAt(start);

                while(str.charAt(start) == removeAlpha){
                    start++;
                    curCount--;
                    alphas[removeAlpha -'a']--;
                }

                if(alphas[removeAlpha -'a'] == 0){
                    selectCount--;
                }
            }

            // 최대 길이 갱신
            maxCount = Math.max(curCount, maxCount);
        }

        bw.write(maxCount+"");
        bw.flush();
    }
}