[알고리즘] 교육과정 설계 (Queue)

(문제) 교육과정 설계

---

1년 과정의 수업계획을 짜야 합니다.

수업중에는 필수과목이 있습니다.
이 필수과목은 반드시 이수해야 하며, 그 순서도 정해져 있습니다.

만약 총 과목이 A, B, C, D, E, F, G가 있고, 여기서 필수과목이 CBA로 주어지면 필수과목은 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“를 출력합니다.

테스트케이스

입력예제	출력예제
CBA 3 CBDAGE FGCDAB CTSBDEA	#1 YES #2 NO #3 YES
AFC 1 AFFDCCFF	#1 YES
AKDEF 5 AYKGDHEJ AQKWDERTFYP CTFKSBDEA ASKGHDEF WOPASFKGHDEF	#1 NO #2 YES #3 NO #4 YES #5 NO
QWERTY 8 AYKGDHEJF QASWDFEGRHTCJVYK ZCTSBDEA KJHDGAFQZWXECRVTBY WOPASFKGHDEF MQASWDFEGRHTCJVYK MZCTSBDEA NKJHDGAFQZWXECRVTBY	#1 NO #2 YES #3 NO #4 YES #5 NO #6 YES #7 NO #8 YES

---

해결방법

• 입력으로 받은 필수 교육과정을 리스트로 만든다.
• 선택한 교육과정을 반복문으로 순회를 시켜 해당 문자가 리스트안에 있는 문자이면서 리스트의 출구 쪽에 있는 요소를 pop시켜서 해당 요소를 순회시키면서 만난 문자와 다를 경우 반복문을 종료 시켜킨다.
• 만약 리스트의 출구 쪽에 있는 요소를 pop 시켜서 해당 요소를 순회시키면서 만난 문자와 같을 경우, 리스트에 있는 요소는 전부 사라져서 리스트는 빈 리스트가 된다.
• 리스트의 길이가 0 일 경우 커리큘럼을 지킨 것이여서 YES를 출력한다.
• 리스트의 길이가 0 보다 클 경우 커리큘럼을 지키지 못한 것이 되어 NO를 출력한다.

  동작 시각화

  예)
  AKDEF
  2
  AQKWDERTFYP
  WOPASFKGHDEF

---

코드

req = input()
Q = list(req)
n = int(input())

a = [input() for _ in range(n)]

for num, x in enumerate(a):
    for word in x:
        # 큐안에 문자가 있지만(선실행), 출구에 있는 값과 다를 경우(선실행 참일 경우만 후실행)
        # 어차피 pop 되서 같 경우는 같을 경우여서 pop하는 것이 맞다
        if (True if word in Q else False) and word != Q.pop(0):
            break
        
    if Q:
        print(f"#{num+1} NO")
    else:
        print(f"#{num+1} YES")

    Q = list(req)