⌨️ Algorithms/백준

[Python] 백준 15786번_Send me the money

monzheld 2023. 6. 6. 22:12

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

 

15786번: Send me the money

입력의 첫째 줄에 석규가 기억하는 원본 알파벳의 수 N(1 ≤ N ≤ 100)과 포스트잇의 개수 M(1 ≤ M ≤ 1000)이 주어진다. 다음 줄에 길이가 N인 알파벳 대문자로 이루어진 문자열 S가 주어진다. 이 후 M

www.acmicpc.net

 

  • 석규는 센트비 비밀번호를 까먹어버렸고 돈을 보내주지 못함
  • 비밀번호는 알파벳 대문자로만 구성이 되어있으며 석규는 이 중 일부를 정확히 기억하고 있음
  • 포스트잇은 여러 장 존재했고 이 중 어떤 포스트잇이 센트비 비밀번호가 적힌 포스트잇인지 모름
  • 석규는 센트비 비밀번호의 알파벳 중 등장하는 순서대로 N글자만 정확히 기억하고 있으며 포스트잇 중에 이 순서를 갖는 포스트잇이 센트비 비밀번호일 가능성이 있는 포스트잇
  • 예를 들어, 석규가 ABB를 기억한다면
    • BBAB이 적힌 포스트잇은 비밀번호일 가능성이 없고
    • HAEBBC가 적힌 포스트잇은 비밀번호일 가능성이 있음
  • 석규가 기억하는 알파벳 N글자와 포스트잇 M개가 주어질 때, 해당 포스트잇에 적힌 알파벳이 비밀번호일 가능성이 있는지 여부를 판단하기
  • 입력
    • 입력의 첫째 줄에 석규가 기억하는 원본 알파벳의 수 N(1 ≤ N ≤ 100)과 포스트잇의 개수 M(1 ≤ M ≤ 1000)이 주어짐
    • 다음 줄에 길이가 N인 알파벳 대문자로 이루어진 문자열 S가 주어짐
    • 이 후 M개의 줄에 알파벳 대문자로 이루어진 판별해야 할 포스트잇들이 주어짐
    • 모든 포스트잇에 적힌 문자열은 1000자 이하
  • 출력
    • M개의 줄에 가능성 여부를 “true” , “false”로 답하기
  • 시간 제한: 1초
  • 메모리 제한: 512 MB

 

"""
입출력 예시)

(예제 입력 1) 
4 5
PPAP
PPAPP
PPPPA
APPPP
PPPAP
PAPAP
        -> true
           false
           false
           true
           true

(예제 입력 2) 
3 2
CTP
P
CHALLENGETHEPROGRAMING
                        -> false
                           true
"""

 

 

## 의사코드 ##

# 비밀번호의 알파벳 중 등장하는 순서대로 N글자만 정확히 기억
# -> 석규가 기억하는 원본 알파벳을 큐로 사용

# 포스트잇에 적힌 문자열의 알파벳을 하나씩 확인하면서
# 현재 알파벳이 원본 알파벳 리스트의 첫 글자랑 같으면 새로 생성할 문자열에 추가 + 원본 알파벳 리스트에서 pop(0)

# 새로 생성한 문자열이 원본 알파벳이랑 동일하면 true

 

 

 

 

n, m = map(int, input().split())
# 석규가 기억하는 원본 알파벳
original_s = input()
for _ in range(m):
    # 포스트잇에 적힌 문자열
    postit = input()
    # 원본 알파벳 리스트 초기화
    s = list(original_s)
    res = '' # 새로 생성할 문자열
    # 포스트잇에 적힌 문자열의 알파벳 하나씩 확인
    for p in postit:
        # 원본 알파벳 리스트의 모든 알파벳이 pop되었으면 종료
        if s == []:
            break 
        else: 
            # 현재 알파벳이 원본 알파벳 리스트의 첫 번째 알파벳과 같다면 새로 생성할 문자열에 추가하고, 원본 알파벳 리스트에서 pop
            if p == s[0]:
                res += p
                s.pop(0)
    # 새로 생성한 문자열이 원본 알파벳과 같다면 true
    if res == original_s:
        print('true')
    else:
        print('false')

 

 

  • 석규가 기억하는 원본 알파벳의 순서를 지켜야 함 
    • -> 석규가 기억하는 원본 알파벳을 선입선출 개념인 '큐'라고 생각
    • 포스트잇에 적힌 문자열의 현재 알파벳과 원본 알파벳의 첫 번째 글자가 동일하면 원본 알파벳에서 첫 글자를 pop

 

 

  • 과정 확인
"""
원본 알파벳: PPAP 

포스트잇에 적힌 문자열: PPAPP
원본 알파벳 리스트: ['P', 'P', 'A', 'P'] 

현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P', 'P', 'A', 'P']
새로 생성된 문자열: P
pop된 원본 알파벳 리스트: ['P', 'A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P', 'A', 'P']
새로 생성된 문자열: PP
pop된 원본 알파벳 리스트: ['A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: A
남아있는 원본 알파벳 리스트: ['A', 'P']
새로 생성된 문자열: PPA
pop된 원본 알파벳 리스트: ['P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P']
새로 생성된 문자열: PPAP
pop된 원본 알파벳 리스트: []
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: []
true
--------------------------------------------------------------------------------

포스트잇에 적힌 문자열: PPPPA
원본 알파벳 리스트: ['P', 'P', 'A', 'P'] 

현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P', 'P', 'A', 'P']
새로 생성된 문자열: P
pop된 원본 알파벳 리스트: ['P', 'A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P', 'A', 'P']
새로 생성된 문자열: PP
pop된 원본 알파벳 리스트: ['A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: A
남아있는 원본 알파벳 리스트: ['A', 'P']
새로 생성된 문자열: PPA
pop된 원본 알파벳 리스트: ['P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
false
--------------------------------------------------------------------------------

포스트잇에 적힌 문자열: APPPP
원본 알파벳 리스트: ['P', 'P', 'A', 'P'] 

현재 알파벳: A
남아있는 원본 알파벳 리스트: ['P', 'P', 'A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P', 'P', 'A', 'P']
새로 생성된 문자열: P
pop된 원본 알파벳 리스트: ['P', 'A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P', 'A', 'P']
새로 생성된 문자열: PP
pop된 원본 알파벳 리스트: ['A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
false
--------------------------------------------------------------------------------

포스트잇에 적힌 문자열: PPPAP
원본 알파벳 리스트: ['P', 'P', 'A', 'P'] 

현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P', 'P', 'A', 'P']
새로 생성된 문자열: P
pop된 원본 알파벳 리스트: ['P', 'A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P', 'A', 'P']
새로 생성된 문자열: PP
pop된 원본 알파벳 리스트: ['A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: A
남아있는 원본 알파벳 리스트: ['A', 'P']
새로 생성된 문자열: PPA
pop된 원본 알파벳 리스트: ['P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P']
새로 생성된 문자열: PPAP
pop된 원본 알파벳 리스트: []
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
true
--------------------------------------------------------------------------------

포스트잇에 적힌 문자열: PAPAP
원본 알파벳 리스트: ['P', 'P', 'A', 'P'] 

현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P', 'P', 'A', 'P']
새로 생성된 문자열: P
pop된 원본 알파벳 리스트: ['P', 'A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: A
남아있는 원본 알파벳 리스트: ['P', 'A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P', 'A', 'P']
새로 생성된 문자열: PP
pop된 원본 알파벳 리스트: ['A', 'P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: A
남아있는 원본 알파벳 리스트: ['A', 'P']
새로 생성된 문자열: PPA
pop된 원본 알파벳 리스트: ['P']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
현재 알파벳: P
남아있는 원본 알파벳 리스트: ['P']
새로 생성된 문자열: PPAP
pop된 원본 알파벳 리스트: []
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
true
--------------------------------------------------------------------------------
"""