[Inflearn] 자바 알고리즘 문제풀이 #05-07 7. 교육과정 설계

문제

설명

현수는 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“를 출력하는 프로그램을 작성하세요.

 

입력 

첫 줄에 한 줄에 필수과목의 순서가 주어집니다. 모든 과목은 영문 대문자입니다.

두 번 째 줄부터 현수가 짠 수업설계가 주어집니다.(수업설계의 길이는 30이하이다)

 

출력 

첫 줄에 수업설계가 잘된 것이면 “YES", 잘못된 것이면 ”NO“를 출력합니다.

예시 입력 1 

CBA
CBDAGE

예시 출력 1

YES

 

 

 

내 풀이

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

public class Main5_7 {
    public String Solution(String k, String n) {
        String answer="NO";
        Queue<Character> Q = new LinkedList<>();
        for (int i = 0; i < n.length(); i++) Q.offer(n.charAt(i));

        int cnt=0;
        for (int i = 0; i < n.length(); i++) {
            if(cnt<k.length() && Q.peek()==k.charAt(cnt)){
                Q.offer(Q.poll());
                cnt++;
            }
            else Q.poll();
        }
        String tmp="";
        Iterator iter = Q.iterator();
        while(iter.hasNext())
            tmp+=iter.next();
        if(tmp.equals(k)) answer="YES";

        return answer;
    }
    public static void main(String[] args) {
        Main5_7 T = new Main5_7();
        Scanner sc = new Scanner(System.in);
        String k = sc.next();
        String n = sc.next();
        System.out.println(T.Solution(k, n));
    }
}

cnt를 이용해 어떻게든 O(n)으로 풀었다.... Q에 익숙하지가 않아서 좀 오래 걸렸다.

 

 

 

선생님 풀이

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

public class Main5_7 {
    public String Solution(String need, String plan) {
        String answer="YES";
        Queue<Character> Q = new LinkedList<>();
        for(char x : need.toCharArray()) Q.offer(x);
        for(char x : plan.toCharArray()) {
            if(Q.contains(x))
                if(x!=Q.poll()) return "NO";
        }
        if(!Q.isEmpty()) return "NO";
        return answer;
    }

    public static void main(String[] args) {
        Main5_7 T = new Main5_7();
        Scanner sc = new Scanner(System.in);
        String a = sc.next();
        String b = sc.next();
        System.out.println(T.Solution(a, b));
    }
}

나는 Q에 현수가 짠 수업 설계 과목들을 넣어놓고 순서대로 필수과목과 비교했다면,

선생님은 Q에 필수과목들을 넣어놓고 현수가 짠 수업 설계 과목들을 하나씩 비교해 푸는 점이 다르다.

 

 

 

결과