자바 알고리즘 문제 풀이 입문. ch05. Stack, Queue (자료구조) : 교육과정설계

 

https://hyejin.tistory.com/1237

자바 알고리즘 문제 풀이 입문. ch05. Stack, Queue (자료구조) : 공주 구하기

-> 이전 문제 풀이 

 

 

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

 

 

문제 풀이 1

public String solution(String sub, String design)
{
   Queue<Character> queue = new LinkedList<>();
   
   for (char c : design.toCharArray())
   {
      queue.add(c);
   }
   
   String tmp = "";
   for (Character character : queue)
   {
      for (char c : sub.toCharArray())
      {
         if (character == c) {
            tmp += character;
         }
      }
   }
   
   return tmp.equals(sub) ? "YES" : "NO";
}

👩🏻‍💻 : 우선 나는 수업 설계 문자열 design이 주어지면 이를 문자 배열로 만들어서 queue에 넣어주고, 그 다음 tmp 문자열 하나를 초기화해주고, 그 다음 queue를 반복문으로 돌면서 필수 과목 sub의 문자 배열과 queue에 들어간 문자를 비교하면서 둘이 같으면 tmp 문자열에 추가를 해주고, 반복문을 종료한다. 그 다음 tmp 문자열이 sub이랑 같으면 필수 과목을 순서대로 들어서 같다는 의미이므로 YES를 리턴하고 아니면 NO를 리턴하도록 했다. 

 

C, B, D, A, G, E 이 수업 설계의 tmp는 CBA이므로 sub랑 같아서 YES를 리턴하지만, 

C, G, E, A, D, B 이 수업 설계의 tmp는 CAB이므로 sub이랑 달라서 NO를 리턴한다. 

 

 

문제 풀이 2

public String solution2(String need,String plan) {
   String answer = "YES";
   Queue<Character> queue = new LinkedList<>();

   for (char c : need.toCharArray()) {
      queue.offer(c); // 필수 과목 세팅
   }

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

   if (!queue.isEmpty()) {
      return "NO";
   }

   return answer;
}

👾 : 강사님은 우선 answer를 YES로 초기화하고, 주어진 필수 과목 need를 Queue에 넣어줬다. 

그 다음, 짠 수업 설계 문자열 plan을 문자 배열로 만들어 반복문을 돌면서 문자 c 가 queue에 들어있는지 contains 메서드를 사용해서 queue에 포함되어 있다는 건 필수 과목이라는 것이고, 그 문자 c가 queue에서 poll 해서 꺼낸 값과 같으면 계속 반복문을 진행하면 되지만, 만약 다르면 필수 과목 순서대로 수업을 설계한 것이 아니기 때문에 더 반복문을 돌지 않고 바로 NO를 리턴해주면 된다. 

 

이렇게 반복문을 다 돌고 나서 만약 queue가 비어있지 않다는 것은 필수 과목을 모두 포함해서 수업을 설계하지 않았다는 것이기 때문에 return "NO"를 해주고, queue가 비어있다면 YES 를 리턴해주면 된다.