[백준 16472] 고냥이(java)-투포인터

문제보러가기

16472번: 고냥이

이 문제는 투 포인터 알고리즘을 접해봤다면 이 알고리즘을 써야겠구나 라고 바로 알 수 있다. 신경 써줘야 할 점은 중복이 가능한 문자열이라는 점!

 

 

 

 

 

 

문제풀이

- 왼쪽 시작 포인터 s와 오른쪽 끝 포인터 e를 이동해가면서 최대 길이를 찾는다

- 알파벳의 종류의 수를 체크하기 위해 Map을 이용한다

- Map의 size()가 주어진 종류의 수 보다 크다면 s++하고 해당 문자열을 key로 갖는 value를 -1 해준다. 

   만약, -1 했을 때 value==0이라면 map에서 제거해준다.

 

- map.put 부분에서 문제가 있었는데 s포인터만 움직였는데 e를 중복해서 담는 과정이 있었다. -> preS를 통해 확인해주며 접근하여 해결!

 

 

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Ex_16472 {

	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		//고양이 투포인터
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		String[] str = br.readLine().split("");
		
		int s=0;//시작
		int e=0;//끝
		int max=0;//최대길이 반환
        //주어진 문자열 길이가 주어진 알파벳 종류 보다 짧다면 바로 return
		if(n>=str.length) {
			System.out.println(str.length);
			return;
		}
		Map<String,Integer> map = new HashMap<>();
		int preS = s; //s포인터만 움직였을 경우를 판단
        
		while(s<=e && e < str.length) {
        	//s==e 이거나 s++이 되어 preS!=s일 경우에는 e가 중복으로 들어가게 됨.
            //이를 해결하기 위한 조건문
			if((s!=e || e==0) && preS==s)
				map.put(str[e], map.getOrDefault(str[e], 0) + 1);
			
            //알파벳 종류가 넘지 않을 경우 최대 길이 갱신
			if(map.size() <= n) {
				max = Math.max(max, e-s+1);
				e++;
				preS = s;
			}
            //넘는 다면 s++하고 해당 알파벳의 value값 -1
			else {
				int num = map.get(str[s])-1;
				if(num== 0)
					map.remove(str[s]);
				else
					map.put(str[s], num);
				s++;
			}
		}
		System.out.println(max);
	}

}