[Ch.05 - StackQueue] 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.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class asdf {
	public String solution(String str1, String str2) {
		Queue<Character> q = new LinkedList<>();
		String answer = "YES";
		char[] arr = str1.toCharArray();
		for (char a : arr) {
			q.offer(a);
		}
		char[] arr2 = str2.toCharArray();
		for (char a : arr2) {
			if (q.isEmpty())
				return answer;
			else if (q.peek() == a) {
				q.poll();
				continue;
			} else {
				if (q.contains(a)) {
					return answer = "NO";
				}
				

			}

		}
		if (!q.isEmpty())
			return answer = "NO";

		return answer;
	}

	public static void main(String[] args) {
		asdf T = new asdf();
		Scanner kb = new Scanner(System.in);
		String str1 = kb.next();
		String str2 = kb.next();
		System.out.println(T.solution(str1, str2));

	}
}

 

 

# NO가 나오는 경우 테스트 케이스 분류

(1) 교육과정 순서를 지키지 않은 경우

if (q.isEmpty())
				return answer;
			else if (q.peek() == a) {
				q.poll();
				continue;
			} else {
				if (q.contains(a)) {
					return answer = "NO";
				}

-> 큐가 비어있지않는데, (교육과정이 남아있는데도 불구하고), 교육과정 순서가 아닌데 발견된 경우

 

(2) 필수 교육과정인 str1을 str2가 모두 포함하지 않고 있을 경우

if (!q.isEmpty())
return answer = "NO";

 

 

+) 간단히

1. 큐가 비었다면 -> YES

2. 큐가 안비었다면, 확인할 문자열에서 하나씩 확인

-> peek 해서 같으면 poll, 같지 않으면, q에 포함되어있는지 확인 [순서를 체크하기 위함]

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

public class Main {
	public String solution(String str1, String str2) {
		String answer = "NO";
		Queue<Character> q = new LinkedList<>();
		for (char x : str1.toCharArray())
			q.add(x);

		for (char x : str2.toCharArray()) {
			if (q.isEmpty()) {
				return answer="YES";
			} else {
				if (q.peek() == x)
					q.poll();
				else if (q.contains(x))
					return answer;
			}
		}

		return answer;
	}

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

	}

}

 

+) 세련된 코드

 

1. 필수 과목을 큐에 offer

2. 수업설계는 하나씩 접근해서 확인 -> 해당 과목이 필수 과목인지 확인

3. 큐가 비어있으면 YES 아니면 NO

 

1. Q.offer()

2.Q.contains(x)

3.Q.isEmpty()

 

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

//x!=Q.poll, !Q.isEmpty()
public class Main {
	public String solution(String str1, String str2) {
		String answer="NO";
		Queue<Character> q = new LinkedList<>();
		for(char x : str1.toCharArray()) q.offer(x);
		for(char x : str2.toCharArray()) {
			if(q.contains(x)) {
				if(q.poll()!=x) return answer; 
			}
		}
		
		if(q.isEmpty()) return answer="YES";
		
		return answer;
	}
	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		String str1= kb.next();
		String str2= kb.next();
		System.out.println(T.solution(str1, str2));
	}

}

---

1. stack 이용

2. queue 이용

 

# stack도 contains메서드 존재

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str1=in.next();
    String str2=in.next();
    System.out.println(Solution(str1, str2));
  }
  private static String Solution(String str1, String str2){
    Stack<Character> stack1 = new Stack<>();
    char[] arr1 = str1.toCharArray();

    for(int i=arr1.length-1; i>=0; i--) stack1.push(arr1[i]);
    for(char c:str2.toCharArray()){
      if(!stack1.isEmpty()&&c==stack1.peek()) {
        stack1.pop();
      }
      if(stack1.isEmpty()) return "YES";
    }
    
    return "NO";
  }
}

 

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str1=in.next();
    String str2=in.next();
    System.out.println(Solution(str1, str2));
  }
  private static String Solution(String str1, String str2){
    Queue<Character> stack1 = new LinkedList<>();
    for(char c: str1.toCharArray()) stack1.offer(c);
    
    for(char c:str2.toCharArray()){
      if(!stack1.isEmpty()&&c==stack1.peek()) {
        stack1.poll();
      }else if(!stack1.isEmpty() && stack1.contains(c)) return "NO";
      if(stack1.isEmpty()) return "YES";
    }
    
    return "NO";
  }
}

 

#순서를 굳이 체크 안해도, stack이 빌때만 성공을 리턴한다.

import java.util.*;
  
public class Main {
  public static void main(String[] args){
    Scanner in=new Scanner(System.in);
    String str1=in.next();
    String str2=in.next();
    System.out.println(Solution(str1, str2));
  }
  private static String Solution(String str1, String str2){
    Queue<Character> stack1 = new LinkedList<>();
    for(char c: str1.toCharArray()) stack1.offer(c);
    
    for(char c:str2.toCharArray()){
      if(!stack1.isEmpty()&&c==stack1.peek()) {
        stack1.poll();
      }
      if(stack1.isEmpty()) return "YES";
    }
    
    return "NO";
  }
}