백준 16472번: 고냥이 [투 포인터] -Java :: 매운코딩
728x90
300x250

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

 

16472번: 고냥이

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

www.acmicpc.net

 

 

 

2가지 방법으로 풀어봄

포인터 2개선언, 1개선언+for문

 

<첫 번째 풀이>

포인터 두개 선언

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

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

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		
		st= new StringTokenizer(br.readLine());
		String str = st.nextToken();
		
		int alphabetCnt[] = new int[26]; //현재기준 각 알파벳의 총 갯수 (a~z)
		
		//투 포인터
		int i = 0;
		int j = 0;
		
		int ans = 0;
		int alCnt = 0; //현재 i~j범위에서의 알파벳 종류의 가짓수
		
		alphabetCnt[str.charAt(i)-'a']++;
		alCnt++;
		
		while(j < str.length()-1) {
			j++;
			alphabetCnt[str.charAt(j)-'a']++; //현재기준 j의 알파벳 갯수
			if(alphabetCnt[str.charAt(j)-'a'] == 1)
				alCnt++;
			while(alCnt > N && i < j) {
				//종류 가짓수가 너무 많으니 가장 앞문자부터 제외시켜 보자 (i를 늘림)
				alphabetCnt[str.charAt(i)-'a']--;
				if(alphabetCnt[str.charAt(i)-'a']==0)
					alCnt--;
				i++;
			}
			
//			System.out.println("i = "+i+", j = "+j + ", ans = "+(j-i+1));
			
			//N 범위 안에 안착한다면.. 총길이 계산
			ans = Math.max(ans, j-i+1);
			
		}
		
		System.out.println(ans);
		
	}

}
728x90

 

<두 번째 풀이>

for문에 포인터하나

이런식으로 풀겠지.,. 시간복잡도는 O(문자열길이)

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

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

		//System.setIn(new FileInputStream("Test.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		
		st= new StringTokenizer(br.readLine());
		String str = st.nextToken();
		
		int alphabetCnt[] = new int[26]; //현재기준 각 알파벳의 총 갯수 (a~z)
		
		
		int ans = 0;
		int alCnt = 0;
		
		int j = 0;
		
		for (int i = 0; i < str.length(); i++) {

			while(j < str.length()) {
				alphabetCnt[str.charAt(j)-'a']++;
				if(alphabetCnt[str.charAt(j)-'a'] == 1) //방금 카운팅 함으로써 없던 알파벳이 새로 생긴거라면?
					alCnt++;
				j++;
				if(alCnt > N) {
					//j++ 계산한것 원복
					j--;
					alphabetCnt[str.charAt(j)-'a']--;
					if(alphabetCnt[str.charAt(j)-'a'] == 0) {
						alCnt--;
					}
					break;
				}
				
			}
			//다음에 i++될거니 현재 i가 갖고있는 알파벳 카운팅 제거
			alphabetCnt[str.charAt(i)-'a']--;
			if(alphabetCnt[str.charAt(i)-'a'] == 0)
				alCnt--;
			ans = Math.max(ans, j-i);
			
		}
		
	
		
		System.out.println(ans);
		
	}

}
728x90

+ Recent posts