[큐] 7. 교육과정 설계

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

 

<<풀이>>

-나의 풀이-

 

시간 복잡도 : O(N)

 

처음에 런타임 에러가 났다. 필수과목을 아예 다 넣지 않은 경우를 고려못해서 생긴 문제이다. 비교하면서 큐에서 poll을 하는데 필수과목을 다 넣지 않은 경우에는 다 비교하기전에 이미 큐에 데이터가 없는 상황이 발생한다. 근데 이 상태에서도 poll을 하기 때문에 NullPointerException 에러가 발생하게 된다.

 

이를 고려하니 정답을 맞출 수 있었다.

 

또한 String.valueOf() 를 활영하여 String 메서드인 contains를 활용할 수 있었다. String.valueOf() 이게 없었으면 문자를 문자열로 바꿀 수가 없어서 contains를 활용하지 못한다.

import java.util.*;

class Main {
    private String solution(String target, String str) {
        Queue<Character> Q = new LinkedList<>();
        for(char x : str.toCharArray()) {
            if(target.contains(String.valueOf(x))) {
                Q.offer(x);
            }
        }
        for(char y : target.toCharArray()) {
            if(!Q.isEmpty()) {
                if (y != Q.poll()) return "NO";
            } else return "NO";
        }
        return "YES";
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String target = in.next();
        String str = in.next();
        System.out.println(T.solution(target, str));

    }
}

 

-강사님 풀이-

 

시간 복잡도 : O(N)

 

강사님은 나와 접근 방식이 반대이다. 나는 실제 넣은 강좌를 실제 해야하는 순서의 값과 비교하면서 큐에 넣었다면, 강사님은 미리 지정해둔 해야하는 순서를 넣어두고 실제 신청한 것과 비교하면서 poll을 하며 데이터를 비워나갔다. 그 중에 값이 같지 않으면 "NO" 반환하게 했다.

 

이후에 isEmpty() 메서드로 0이면 "YES"를 반환하도록 아니면 "NO"를 반환하도록 했다.

 

import java.util.*;

class Main {
    private String solution(String target, String str) {
        String answer = "YES";
        Queue<Character> Q = new LinkedList<>();
        for(char x : target.toCharArray()) Q.offer(x);
        for(char x : str.toCharArray()) {
            if(Q.contains(x)) {
                if(x != Q.poll()) return "NO";
            }
        }
        if(!Q.isEmpty()) return "NO";
        
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        String target = in.next();
        String str = in.next();
        System.out.println(T.solution(target, str));

    }
}

 

특히나, 큐 의 메서드 중에 contains()가 있는데 이를 잘 활용하면 코드를 좀 더 쉽고 짧게 구성할 수 있다. 

 

이렇게 같은 방식을 사용하더라도 무엇을 기준으로 잡을지 그리고 어떤 메서드를 이용할지에 따라 풀이 형태가 많이 바뀐다. 

 

이번 문제 같은 경우 더 효율적인 풀이를 생각하지 못한 이유는 두 가지가 있다고 본다.

 

첫째, 지식의 부족이다. 내가 큐에 대해 아직 많이 알지 못해서 생각하지 못한 것이다. 특히 contains가 큐의 메서드인지 몰랐다.

 

둘째, 아직 코드를 짜는 것이 미숙하다는 것이다. 이는 꾸준히 의사코드를 짜서 내가 풀어보고 강사님의 풀이의 팁을 받아 좀 코드를 다듬어서 그 문제와 방식을 내 것으로 만드는 과정이 필요하다. 이런 것들이 자꾸 쌓여가면 언젠가 최적으로 효율적인 코드를 짜고 있을 것이라 확신한다 !! 

 

오늘도 많이 배우고 간다 ㅎㅎ