Algorithm - 교육과정 설계(큐)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[교육과정 설계(큐)]

 

현수는 1년 과정의 수업계획을 만들고자 한다.

수업 중에는 필수과목이 있으며, 필수과목은 반드시 정해진 순서대로 모두 이수해야 한다.

 

예를 들어, 총 과목이 A~G까지 있고 여기서 필수과목이 C, B, A로 주어지면 반드시 이 순서대로 수업계획을 만들어야 한다. 여기서 순서란 B과목은 C과목을 이수한 후에 들어야 하고, A과목은 C와 B과목을 이수한 후에 들어야 한다는 것을 의미한다.

 

현수가 만약 C, B, D, A, G, E로 수업계획을 만들었다면 이는 제대로 된 계획이지만 C, G, E, A, D, B로 계획을 만들었다면 잘못된 계획을 만든 것이 된다. 수업계획은 그 순서대로 앞의 수업이 이수되면 다음 수업을 이수한다는 것을 의미한다. 또한, 수업계획서 상의 각 과목은 무조건 이수된다고 가정한다.

 

필수과목 순서가 주어지면 현수가 만든 N개의 수업설계가 잘된 것인지, 잘못된 것인지를 출력하는 프로그램을 작성하시오. (단, 수업설계가 잘되었으면 "YES"를 출력, 잘못된 것이면 "NO"를 출력함)

 

 

*입력 설명

첫 번째 줄에 필수과목의 순서가 주어진다. (단, 모든 과목은 영문 대문자임)

두 번째 줄에는 N(1 ≤ N ≤ 10)이 주어진다.

세 번째 줄부터 현수가 만든 N개의 수업설계가 주어진다. (단, 수업설계의 길이는 30이하임)

수업설계는 같은 과목을 여러 번 이수하도록 설계해도 된다.

 

*출력 설명

수업설계가 잘된 것이면 "YES", 잘못된 것이면 "NO"를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
from collections import deque 
sys.stdin = open('AA/input_38.txt', 'rt')

need = input()
n = int(input())

for i in range(n):
    plan = input()
    dq = deque(need)
    for x in plan:
        if x in dq:
            if x != dq.popleft():
                print('#%d NO' %(i+1))
                break
    else:
        if len(dq) == 0:
            print("#%d YES" %(i+1))
        else:
            print('#%d NO' %(i+1))
            
            
'''
출력 :
#1 YES
#2 NO
#3 YES
#4 YES

'''

 

input_38.txt(입력)

CBA
4
CBDAGE 
FGCDAB 
CTSBDEA
EFCGBAH

 

 

중요내용

1. x in dq:는 변수 x가 deque 자료형(dq) 안의 데이터로 존재하는지를 확인하는 코드이다.
2. 필수과목을 이수하는 순서가 맞더라도 필수과목이 모두 포함되지 않으면 조건을 만족하는 것이 아니므로, 마지막 else문에서 len() 함수를 활용하여 deque 자료형(dq)의 길이를 확인하는 것이다. (해당 자료형의 길이가 1이상이면 필수과목이 남아있다는 의미이므로 조건에 만족하지 않음)