[인프런] 교육과정 설계

난이도

• Easy

문제 설명

현수는 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 순서로 짰다면 잘 못 설계된 수업계획이 됩니다.
수업계획은 그 순서대로 앞에 수업이 이수되면 다음 수업을 시작하다는 것으로 해석합니다.
수업계획서상의 각 과목은 무조건 이수된다고 가정합니다.

입력 형식

• 문자열

출력 형식

• YES OR NO

예제 입력 및 출력

**예제 1:**
입력: 
CBA
CBDAGE
출력: YES

접근 방법

• 필수 과목을 set으로 만든다
• 필수 과목을 순차적으로 들어야하므로, 설계된 수업을 순차적으로 순회하면서 순서대로 수강되는지 확인
• 필수 과목의 set에 포함되면 set에 해당 값을 삭제
• set의 필수 과목이 없으면 성공적인 교육과정 설계로, 아니면 실패

시간 및 공간 복잡도

• 시간 복잡도: O(n + m) - 필수 과목을 추가(m), 수업 계획 순회 (n)
• 공간 복잡도 : O(m) - Set을 사용해 필수 과목 저장

코드 구현

import java.util.*;

public class App {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String mustClass = sc.nextLine();
        String classes = sc.nextLine();
        Set<Character> classSet = new HashSet<>();
        for (char c : mustClass.toCharArray()) {
            classSet.add(c);
        }

        for (char classText : classes.toCharArray()) {
            if (classSet.contains(classText)) {
                classSet.remove(classText);
            }
        }
        if (classSet.size() > 0) {
            System.out.println("NO");
        } else {
            System.out.println("YES");
        }

    }
}