개발일지/Algorithm
백준 - 16472 고냥이 [투포인터]
E-room
2023. 10. 23. 17:34
728x90
16472번: 고냥이
고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고
www.acmicpc.net
1. 문제 요약
n과 문자열이 주어지고,
문자열에서 최대 n개의 종류의 알파벳을 포함한 문자열의 길이를 구하라.
2. 접근 방법
- 투포인터 알고리즘을 사용하여 문자열을 순차적으로 검사합니다.
- j(끝) 위치의 알파벳이 새로운 알파벳일 경우 count += 1을 하고 사용 중인 알파벳으로 표시합니다.
- 사용 중인 알파벳의 종류가 n보다 클 경우 줄어들 때까지 i(시작) 위치의 알파벳을 이동합니다.
- 사용 중인 알파벳 종류가 하나 줄어들 경우 count -= 1 표시를 해줍니다.
- 현재 answer 값과 생성한 문자열의 길이(j-i)를 비교하여 큰 값을 취합니다.
3. 파이썬
def solution(n:int, arr:str):
alphbet = [0] * 26
answer, count, i, j = 0, 0, 0, 0
while j < len(arr):
if alphbet[ord(arr[j])-97] == 0:
count += 1
alphbet[ord(arr[j])-97] += 1
while count > n and i < j:
alphbet[ord(arr[i])-97] -= 1
if alphbet[ord(arr[i])-97] == 0:
count -= 1
i += 1
j += 1
answer = max(answer, j-i)
return answer
4. 자바
private static int solution(int n, char[] arr) {
int[] alphabet = new int[26];
int answer = 0;
int count = 0;
int i = 0;
int j = 0;
while (j < arr.length) {
if (alphabet[arr[j] - 'a'] == 0) { // 새로운 알파벳일 경우
count += 1;
}
alphabet[arr[j] - 'a'] += 1;
while (count > n && i < j) { // count가 n보다 클경우 줄어들때까지 i위치를 이동
alphabet[arr[i] - 'a'] -= 1;
if (alphabet[arr[i] - 'a'] == 0) { // 사용중인 알파벳 하나를 없앴을 경우
count -= 1;
}
i += 1;
}
j += 1;
answer = Math.max(answer, j - i);
}
return answer;
}
5. 전체 코드
728x90