섹션 5. Stack, Queue - 7. 교육과정 설계

📌 문제 설명

1년 과정의 수업 계획을 세우는 현수는 필수 과목의 순서를 반드시 지켜야 합니다. 필수 과목은 특정 순서로 반드시 이수되어야 하며, 수업 계획표에 포함된 모든 과목은 무조건 이수한다고 가정합니다.

예를 들어, 필수 과목이 "CBA"이고 수업 계획이 "CBDAGE"라면, C → B → A의 순서가 유지되므로 올바른 설계입니다. 반면, "CGEADB"처럼 순서가 어긋나면 잘못된 설계입니다.

---

📝 입력 & 출력

입력

• 첫 줄: 필수 과목의 순서 (ex. CBA)
• 두 번째 줄: 현수가 세운 수업 계획 (ex. CBDAGE)

출력

• 계획이 올바르면 "YES", 그렇지 않으면 "NO"

---

🔹 예제 입력 & 출력

예제 입력 1

CBA
CBDAGE

 

예제 출력 1

YES

---

💡 해결 방법

• 필수 과목을 Queue로 저장하여 순서를 관리합니다.
• 수업 계획을 앞에서부터 순회하면서 필수 과목이 나올 때마다 Queue에서 순서대로 제거합니다.
• 만약 필수 과목 순서와 맞지 않게 등장하거나 끝까지 처리하지 못한 필수 과목이 있다면 "NO"를 반환합니다.

---

💻 코드 구현 (Java)

package partStackQueue;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Problem7 {
	public String solution(String requiredSubjects, String plan) {
		Queue<Character> queue = new LinkedList<>();
		for (char subject : requiredSubjects.toCharArray()) {
			queue.offer(subject);
		}

		for (char course : plan.toCharArray()) {
			if (queue.contains(course)) {
				if (course != queue.poll()) return "NO";
			}
		}
		return queue.isEmpty() ? "YES" : "NO";
	}

	public static void main(String[] args) {
		Problem7 T = new Problem7();
		Scanner kb = new Scanner(System.in);
		System.out.print(T.solution(kb.next(), kb.next()));
		kb.close();
	}
}

---

📖 코드 설명

Queue<Character> queue = new LinkedList<>();
for (char subject : requiredSubjects.toCharArray()) {
	queue.offer(subject);
}

• 필수 과목을 Queue에 담아 순서를 관리합니다.

for (char course : plan.toCharArray()) {
	if (queue.contains(course)) {
		if (course != queue.poll()) return "NO";
	}
}

• 수업 계획을 순회하며 필수 과목 순서에 맞게 처리되는지 확인합니다.
• 현재 과목이 필수 과목이면서 순서가 맞지 않으면 바로 "NO" 반환

return queue.isEmpty() ? "YES" : "NO";

• 모든 필수 과목이 순서대로 처리되었는지 확인하고 결과 반환

---

⏳ 시간 복잡도 분석

• 수업 계획 순회: O(N)
• Queue에서의 contains, poll 연산: 최악의 경우 O(N) → 전체적으로 O(N^2) 가능
• 하지만 필수 과목이 26자를 넘지 않으므로 실질적으로는 O(N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런