자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Stack,Queue_교육과정설계_Queue)

 

7. 교육과정 설계

 

예시 입력 1 

CBA
CBDAGE

예시 출력 1

YES

 

 

내가 푼 풀이(Time: 164ms Memory: 27MB)

필수 과목들을 먼저 Q에 집어넣고, k문자열을 순회하면서 Q의 상단(앞단)에 있는거라아 일치하면 Q의 원소를 빼내줍니다.

이때 isEmpty()를 걸어주지 않으면 큐가 비어있는데 peek()을 하려고 해서 NullpointException이 나옵니다.

그리고 마지막 큐의 사이즈가 비어있지 않으면 NO를 리턴합니다.

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

public class Main {

    public String solution(String need, String k) {
        String answer = "YES";

        Queue<Character> Q = new LinkedList<>();
        for (int i = 0; i < need.length(); i++) {
            Q.offer(need.charAt(i));
        }

        for (int i = 0; i < k.length(); i++) {
            if (!Q.isEmpty() && k.charAt(i) == Q.peek()) Q.poll();
        }
        if (!Q.isEmpty()) return "NO";
        return answer;
    }


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

 

강의 풀이(Time: 162ms Memory: 27MB)

 

필수과목을 CBA라고 했는데, 순서대로 계획표를 짜야합니다. 이 순서대로 있지 않으면 잘못된것입니다.

모든 과목은 영문 대문자라고 되어있는데, 대문자 알파벳은 총 26개뿐인데, 30이하라는건 설계표에 중복된 과목이 있을 수도 있다는 것을 의미합니다. 그러더라도 필수과목 순서를 유지하고 있는지만 확인하면 됩니다. 필수과목은 중복되서 들어오지 않습니다.

 

먼저 필수과목을 큐에 집어넣고, 수업계획서인 문자열을 하나식 탐색하고 contains()를 사용해서 큐에 있으면 필수 과목입니다.

있다고 참이 나오면 맨 앞에 있어야 합니다. 맨 앞에 있다는 것은 해당 과목을 들어도 된다는 내용입니다.

 

해당 과목을 수강했다고 하면 poll으로 빼내줍니다. 그런데 맨 앞에 있는 과목이 poll안당하고 앞에 있다고 하면 아직 계획서상 필수과목을 안들었다는 것입니다.

 

만약 계획표가 CDKAE였을 경우, A가 필수과목인데 제일 앞에 있지 않으면 잘못된 계획표입니다. B를 먼저 들어야 합니다. 

만약 계획표가 CEDBK였을 경우, 전부 다 들었는데 큐에 원소가 남아 있다면 잘못된 계획표입니다.

 

peek()을 할 경우 앞단에 뭐가 있는지만 확인하고 빼낼 수 없으므로 pop()사용, 어차피 빼냈을때 x가 아니면 바로 리턴

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

public class Main {
    public String solution(String need, String plan) {
        String answer = "YES";
        Queue<Character> Q = new LinkedList<>();
        // queue에 필수과목을 먼저 다 집어넣기
        for (char x : need.toCharArray()) Q.offer(x);
        // 계획표를 하나씩 순회하면서 Q에 있는지 확인
        for (char x : plan.toCharArray()) {
            // 참이면 필수과목이다
            if(Q.contains(x)) {
                // queue에 있는 맨 앞에꺼가 x와 일치하지 않으면 뒤쪽에 있는걸 순서가 틀린것이다.
                // x를 기준으로 보는거라서 포함되어있는데 앞단이 아니라면 잘못된 계획표
                // peek()을 하면 해당 조건문에 부합하지 않을때 빼낼 수가 없으므로 poll()로 조건문을 걸어야한다
                if(x!=Q.poll()) return "NO";
            }
        }
        // 필수 과목을 이수 안 할경우
        if (!Q.isEmpty()) return "NO";

        return answer;
    }

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