[코딩테스트] 고냥이

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

문제 분석

해당 문제는 시간 제한이 1초, 메모리 제한이 512MB입니다. 메모리 제한만 보면 꽤나 넉넉하기 때문에 DP를 해가면서 할 필요는 없어보입니다.

그리고 문자열 길이가 100000까지 제한이 되어있습니다. 이를 통해 알수있는 것은, $O(N^2)$ 복잡도를 절대 사용할 수 없다는 것입니다.

그런데 이 문제는 투포인터로 문제가 분류되어있음에도, 선형탐색으로도 문제를 충분히 해결할 수 있습니다. 이제부터 그 이유를 알아봅시다.

이 문제를 어떻게 선형탐색으로 해결했어요?

이 문제는 List of Unique Numbers 와 문제 풀이 방식이 매우 흡사합니다. 따라서 이것도 같이 보시면 도움이 많이 됩니다.
링크: https://velog.io/@18k7102dy/coding-test-fifth-1

일단은 우리가 저 문제를 직접 풀 때 어떻게 푸는지부터 생각해봅시다. 저 같은 경우에는 문제를 보고 이렇게 생각했습니다.

1. abb 까지는 가능하네?
2. abbc는 안되네?
3. bbc는 가능하네. 그런데 bbca는 안되네
4. bca도 안되고, cacc까지는 되네!
.
.
.

사실 이 생각 자체는 선형탐색과 다를 바가 없습니다. 다만 버퍼 역할을 할 리스트가 필요하고, 특정 알파벳이 이미 몇 번 등장했는지만 기억을 하면 될 뿐입니다.

위의 생각이 핵심입니다. 위의 방법으로는 선형탐색으로 코드 상으로도 구현이 가능하기 때문입니다. 그래서 저는 이렇게 풀기로 생각을 했습니다.

• 버퍼 역할을 수행할 sequence라는 list 변수를 하나 둔다
• 특정 알파벳이 몇 개 등장하였는지 기억해줄 수 있는 checked라는 dict형 변수를 둔다.
• checked의 각 원소는 key로 알파벳 정보를, value로는 해당 알파벳이 몇 개 등장했는지 저장을한다.
• checked의 key 개수를 매번 세서 다음의 문자를 읽어낼 수 있는지 파악을 하자.

그런데 이렇게 생각하실 수도 있습니다.

checked의 key 개수를 매번 센다는건데, 복잡도가 크게 증가하지 않아요?

우려할 사태는 발생하지 않을겁니다. 어차피 checked의 key 개수는 절대로 2를 넘어서지 않을겁니다. sequence에 맨 앞 알파벳을 pop시킬 때마다 checked를 검사하여 key를 삭제하거나, value를 1을 깎는 방식으로 처리를 할 것이기 때문입니다.

이제부터 위의 생각을 코드로 옮겼는지 같이 감상을 해봅시다.

코드를 감상합시다.

import sys

input = sys.stdin.readline

# 16472 고오냥이
N = int(input())
cat_str = input().strip()

max_len = 0
start, end = 0, len(cat_str) - 1

checked = {} # 특정 알파벳이 몇 개가 등록되어있는지 검사하기 위한 dict
sequence = [] # 버퍼 역할을 하는 리스트

start, end = 0, len(cat_str) - 1
max_len = 0

while start <= end:
    count = len(checked.keys())
    read_ch = cat_str[start]
    
    # 새로운 알파벳의 등장 && count가 N보다 작은 경우: 추가할 수 있다.
    if read_ch not in sequence and count < N:
        checked[read_ch] = 1
        sequence.append(read_ch)
        start += 1
    # 새로운 알파벳 등장 && count가 N인 경우: 못 넣는다.
    elif read_ch not in sequence and count == N:
        if max_len < len(sequence):
            max_len = len(sequence)
        
        # 수열 맨 앞 원소 잘라내기
        remove_ch = sequence.pop(0)
        
        if checked[remove_ch] == 1:
            del checked[remove_ch]
        else:
            checked[remove_ch] -= 1
    # 기존에 존재하던 알파벳 등장 -> 추가할 수 있다!
    elif read_ch in sequence:
        checked[read_ch] += 1
        sequence.append(read_ch)
        start += 1
        
# 짬처리
if len(sequence) > max_len:
    max_len = len(sequence)
    
print(max_len)

코드를 설명해드리겠습니다. 코드는 길어도 로직은 간단해요!

저는 문자를 읽어낼 때마다 수행해야할 로직의 분기를 3개로 나눴습니다. 분기의 내용은 다음과 같습니다.

• 버퍼에 없던 새로운 알파벳을 읽어내려고 하고있고, 버퍼에 있는 서로 다른 알파벳 개수가 N 미만인 경우
• 버퍼에 없던 새로운 알파벳을 읽어내려고 하고있고, 버퍼에 있는 서로 다른 알파벳 개수가 N개인 경우
• 기존에 버퍼에 있던 알파벳을 읽어내려고 하는 경우

일단, 첫번째 분기와 세번째 분기는 버퍼에 문자를 추가할 수 있는 경우입니다. 그리고 두번째 분기의 경우 버퍼에 문자를 넣을 수 없는 경우입니다.

첫번째 분기에서 취해야 할 행동을 말씀드리겠습니다. 첫번째 분기에서는 checked에 새로운 알파벳이 등장했다는 것을 표시해야합니다. 그리고 버퍼에 문자를 붙여넣고 다음 문자를 읽을 준비를 해야합니다.

세번째 분기에서는 checked[read_ch] 의 값을 1 증가시키고 버퍼에 문자를 붙여넣고, 다음 문자를 읽을 준비를 하면 됩니다.

그러나 두번째 분기에서는 좀 다릅니다. 문자를 읽어낼 수 없기 때문에 start를 증가시켜서는 안됩니다. 대신에 버퍼의 길이가 기존의 max_len보다 큰지 검사를 해서 max_len을 갱신하고 sequence의 맨 앞 문자를 날려야합니다.
sequence의 맨 앞 문자를 날렸다면, checked에다가 그 사실을 통보해야합니다. checked에 정보를 갱신하는건 이렇게 하면 됩니다.

• 만약에 checked[read_ch]가 1보다 큰 경우에는 값을 1 깎는다
• checked[read_ch]가 1인 경우에는 key값을 checked에서 삭제시킨다. 이 경우 del checked[read_ch]를 통해서 수행할 수 있다.

그런데 탐색이 끝나도 문제가 있습니다. 버퍼에는 문자열이 남아있다는 겁니다. 문제에서 제시한 예시를 통해 설명을 드리겠습니다.

예제 입력

2
abbcaccba

마지막에 남는 버퍼 정보

['b', 'a']

그런데 이것도 검사를 해줘야합니다. 왜냐면 만에 하나, 버퍼에 남아있는 길이가 max_len보다 큰 경우도 충분히 발생할 수 있기 때문입니다. 따라서 방심하지 않고 다음의 코드를 작성해서 코드를 마무리해주면 됩니다. 저는 이걸 짬처리라고 부르기로 했어요

if len(sequence) > max_len:
    max_len = len(sequence)

마지막에는 max_len을 출력해서 문제를 종결짓습니다.