[백준 9549 🥈] 암호화된 비밀번호

문제

새로운 암호화 알고리즘이 개발되었다.

우선, 모든 비밀번호는 항상 알파벳 소문자로만 이루어진다고 가정하자.

암호화 알고리즘은 다음과 같이 진행된다.

1. 비밀번호의 서로 다른 두 글자를 교환한다. 이 과정은 0번 또는 원하는 만큼 얼마든지 할 수 있다.
2. 1번 과정의 결과물 앞부분에 0개 혹은 그 이상의 문자를 삽입한다.
3. 2번 과정의 결과물 뒷부분에 0개 혹은 그 이상의 문자를 삽입한다.

3번 과정의 결과물이 암호화된 비밀번호이다.

청호는 사용하던 비밀번호들을 위 알고리즘대로 다 암호화했다.

하지만 수작업이었던 탓에 실수가 있을 지도 모르기 때문에 프로그램을 작성하여 제대로 암호화했는지 확인해보려 한다.

암호화된 비밀번호와 원래의 비밀번호가 주어지면, 암호화된 비밀번호가 원래의 비밀번호를 위의 알고리즘대로 암호화한 결과물일 수 있는지 혹은 없는지를 알아내 보자.

입력

첫 줄에 테스트 케이스의 수 T가 주어진다. ( 1 ≤ T ≤ 100 )

각 테스트 케이스는 두 줄로 구성된다.

첫 줄엔 암호화된 결과물이 주어진다.

두 번째 줄엔 원래의 비밀번호가 주어진다.

암호화된 비밀번호와 원래의 비밀번호는 1개 이상 10만개 이하의 문자로 이루어져 있으며, 항상 알파벳 소문자만을 포함한다.

암호화된 비밀번호의 길이는 항상 원래 비밀번호의 길이보다 크거나 같다.

출력

각 테스트 케이스마다, 원래의 비밀번호를 문제에서 설명한 알고리즘대로 암호화했을 때 주어진 결과물이 나올 수 있다면 YES를, 그렇지 않다면 NO를 출력한다.

문제 풀이

import sys
from collections import deque

n=int(sys.stdin.readline())
for _ in range(n):
    # 암호화된 문자열
    encode=list(sys.stdin.readline().strip())
    # 기존 문자열
    decode=list(sys.stdin.readline().strip())
    encode_numbers=[0]*(26)
    decode_numbers=[0]*(26)
    stack=deque()
    for idx in range(len(decode)):
        # 'a'의 아스키코드
        encode_numbers[ord(encode[idx])-97]+=1
        stack.append(encode[idx])
        decode_numbers[ord(decode[idx])-97]+=1

    if len(encode)==len(decode):
        if encode_numbers == decode_numbers:
            print('YES')
        else:
            print('NO')
        continue

    for i in range(len(decode),len(encode)):
        # 제일 앞 문자열 빼고 문자 개수 삭제
        encode_numbers[ord(stack.popleft())-97]-=1
        # 다음 문자열 넣고 문자 개수 추가
        stack.append(encode[i])
        encode_numbers[ord(encode[i])-97]+=1
        if encode_numbers==decode_numbers:
            print('YES')
            break
    else:
        print('NO')

• 암호화된 문자열에서 기존 문자열 길이의 substring 중 각 알파벳의 개수가 같은 substring이 있으면 가능한 경우이다.
• 이를 위해서 알파벳의 아스키코드를 이용해서 알파벳별로 몇 개가 있는지 저장할 수 있는 encode_numbers와 decode_numbers를 사용했다.
• 소문자 알파벳의 개수가 총 26개이므로 [0]*26으로 초기화했다.
• 처음에 기존 문자열이 저장된 decode 배열의 길이만큼 돌면서 decode 문자열의 각 알파벳 개수를 decode_numbers에 저장하고, encode_numbers에 encode 문자열에서 처음부터 decode 배열만큼의 substring의 각 알파벳 개수를 저장하고, stack에 넣어준다.
• 이때 인덱싱하는 방법은 ord()를 이용해서 알파벳을 아스키코드로 바꾸고, 'a'의 아스키코드인 97을 빼준다.
• 이제 초기 stack에 저장된 encode[:len(decode)]를 다음 알파벳부터 하나씩 넣어주고(append) 제일 앞에 알파벳을 빼주면서(popleft) encode_numbers를 업데이트한다.
• 업데이트된 encode_numbers가 decode_numbers와 같은 경우가 발생하면 'YES'를 출력하고 for문을 빠져나온다.
• 이 for문이 모두 돌 때까지 위 조건을 만족하는 substring이 없다면 'NO'를 출력한다.
• 여기서, 예외적으로 encode와 decode의 길이가 같은 경우 for문을 돌기 전에 encode_numbers와 decode_numbers를 비교해서 같으면 'YES', 다르면 'NO'를 출력한다. 
• 이러한 방식을 그려보면 다음과 같다.