728x90
300x250
https://www.acmicpc.net/problem/16472
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
'알고리즘 > 투 포인터' 카테고리의 다른 글
백준 3078번: 좋은 친구 [슬라이딩 윈도우][투 포인터] -Java (0) | 2024.02.14 |
---|---|
백준 15831번: 준표의 조약돌 [투 포인터][구간합][누적합] -Java (0) | 2023.09.15 |
백준 17609번: 회문 [투 포인터][문자열] -Java (0) | 2023.09.13 |
백준 11728번: 배열 합치기 [정렬][투 포인터] -Java (0) | 2023.09.13 |
백준 12891번: DNA 비밀번호 [투 포인터][누적합][구간합] -Java (4) | 2023.09.07 |