백준 16472 (고냥이) - java

문제

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

고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고양이의 언어로, 고양이의 언어를 사람의 언어로 바꾸어 주는 희대의 발명품이 될 것이다.

현재 고양이말 번역기의 베타버전이 나왔다. 그러나 이 베타버전은 완전 엉망진창이다. 베타버전의 번역기는 문자열을 주면 그 중에서 최대 N개의 종류의 알파벳을 가진 연속된 문자열밖에 인식하지 못한다. 굉장히 별로지만 그나마 이게 최선이라고 사람들은 생각했다. 그리고 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다.

고양이와 소통할 수 있도록 우리도 함께 노력해보자.

 

유형 : 해시 + 투 포인터

 

접근 방식

• 입력값이 최대 100,000이기 때문에 O(N)의 시간 복잡도로 문제를 해결해야 한다.
• 연속된 문자열을 지속적으로 관리해야 하기 때문에 투 포인터를 사용하면 가능하다.
  • Hash에 <현재 문자, 갯수>를 저장하여 r을 한칸 씩 오른쪽으로 이동하여 추가한다.
  • 만약 Hash의 size 즉 현재 가지고 있는 문자의 개수가 n보다 크다면 조건을 만족할 때까지 l을 한칸 씩 오른쪽으로 이동하며 삭제한다.

 

전체 코드

import java.util.*;
import java.io.*;

public class Main {

    static int n;
    static char[] arr;

    static HashMap<Character,Integer> map = new HashMap();

    static int result = 0;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());

        arr = br.readLine().toCharArray();


        int l = 0;
        int r = 0;

        while(l <= r && r < arr.length) {
            char next = arr[r];

            if(!map.containsKey(next)) {
                map.put(next,1);
            }else {
                map.put(next,map.get(next) + 1);
            }

            if(map.size() <= n) {
                result = Math.max(result, r - l + 1);
            }else {
                while(map.size() > n) {
                    int nextNum = map.get(arr[l]) - 1;

                    if(nextNum == 0) {
                        map.remove(arr[l]);
                    }else {
                        map.put(arr[l],nextNum);
                    }

                    l++;
                }
            }

            r++;
        }

        System.out.println(result);

        br.close();
    }
}