[백준_Queue]10845번_큐

Posted by 열정보이
2018. 11. 13. 22:37 Algorithms

기본적인 스택문제를 풀었으니, 이제 기본적인 큐 문제를 풀어보려고 한다.


스택의 특징이 Last In First Out 이었다면, 큐의 특징은 First In First Out 이다.


우리는 사실 일상생활에서 큐를 활용한 케이스를 쉽게 접할 수 있다.


우리가 은행에 갔다고 가정하자.

그리고 내가 먼저 왔는데 내 뒤에 온 사람이 나보다 먼저 상담원에게 갔다면, 스택의 원리인 LILO을 활용한 시스템이라고 할 수 있다. 하지만 현실에서 그런일이 일어날리는 없다...


은행 시스템은 먼저 온 사람이 먼저 업무를 볼 수 있게 도와준다.

"먼저 왔으니, 먼저 처리하자" 이것이 바로 FIFO, 큐이다.


그렇다면 큐를 활용한 문제를 풀어보도록 하자.



스택과 마찬가지로 기본적인 메서드를 활용하는 큐 문제이다.


Java에서는 Queue를 클래스가 아닌, 인터페이스로 제공을 하고 있다.


바로 소스코드를 보도록 하자.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Al10845 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine());
        Queue<Integer> queue = new LinkedList<>();
        StringTokenizer token;
        StringBuilder build = new StringBuilder();
        int lastVal = -1;
        
        for (int i = 0; i < testCase; i++) {
            token = new StringTokenizer(br.readLine());
            String method = token.nextToken();
            
            switch (method) {
            case "push":
                int temp = Integer.parseInt(token.nextToken());
                lastVal = temp;
                queue.add(temp);
                break;
            case "pop":
                if(queue.isEmpty()) build.append("-1\n");
                else build.append(queue.poll()+"\n");
                break;
            case "size":
                if(queue.isEmpty()) build.append("0\n");
                else build.append(queue.size()+"\n");
                break;
            case "empty":
                if(queue.isEmpty()) build.append("1\n");
                else build.append("0\n");
                break;
            case "front":
                if(queue.isEmpty()) build.append("-1\n");
                else build.append(queue.peek()+"\n");
                break;
            case "back":
                if(queue.isEmpty()) build.append("-1\n");
                else build.append(lastVal+"\n");
                break;
            default:
                break;
            }
        }
        System.out.println(build.toString());
    }
}
 
cs


Queue 인터페이스를 직접 구현하기보다, LinkedList 인스턴스를 참조하게 하였다.


Queue 인터페이스는 Collection 인터페이스를 상속받았고, List 인터페이스는 Collection을 상속받았고, LinkedList 클래스는 List 인터페이스를 implements 하여 구현한것이기 때문에, Queue 인터페이스를 참조하는 참조변수는 LinkedList 인스턴스를 참조할 수 있다.


왜냐하면 Java는 A라는 클래스를 상속받은 클래스를 B라고 할 때, A testA = new B(); 로도 선언을 할 수 있기 때문이다.

하지만 testA는 A클래스 타입의 참조변수이므로, 만약 B 클래스의 독자적인 메서드나 변수가 있다면 사용할 수 없다.


무튼 그리하여 Queue를 완성하였고,

Queue에 주어진 메서드를 사용하여 해당 문제를 쉽게 풀 수 있다.

단, Queue의 맨 마지막 값을 return하는 메서드는 제공되지 않아, push할 때, 해당 값을 저장하여 그 값을 출력하는 방식으로 진행하였다.


그러나 만약, Queue 인터페이스를 사용하지 않고, LinkedList 클래스 타입으로 문제를 푼다면 다음과 같이 풀 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
    static LinkedList<Integer> qu = new LinkedList<>();
    static StringBuilder build = new StringBuilder();
    static StringTokenizer token;
    
    public static void Al10845(String[] args) throws NumberFormatException, IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            token = new StringTokenizer(br.readLine());
            check(token);
        }
        
        System.out.println(build);
        
    }
    
    public static void check(StringTokenizer token) {
        
        String[] str = new String[token.countTokens()];
        for (int i = 0; i < str.length; i++) {
            str[i] = token.nextToken();
        }
        switch (str[0]) {
        case "push":
            qu.add(Integer.parseInt(str[1]));
            break;
        case "front":
            if(qu.isEmpty()) {
                build.append("-1").append("\n");
            }else {
                build.append(qu.peek()).append("\n");
            }
            break;
        case "pop" :
            if(qu.isEmpty()) {
                build.append("-1").append("\n");
            }else {
                build.append(qu.poll()).append("\n");
            }
            break;
        case "size":
            build.append(qu.size()).append("\n");
            break;
        case "empty":
            if(qu.isEmpty()) {
                build.append("1").append("\n");
            }else {
                build.append("0").append("\n");
            }
            break;
        case "back":
            if(qu.isEmpty()) {
                build.append("-1").append("\n");
            }else {
                build.append(qu.getLast()).append("\n");
            }
        }
    }
}
cs


굳이 메서드를 만들어 문제를 풀어보았다.

LinkedList를 이용한다면 LinkedList에서 제공하는 getLast()메서드를 사용하여 마지막 값을 쉽게 구할 수 있다.


즐거운 알고리즘~

'Algorithms' 카테고리의 다른 글

[백준_Queue]1158_조세퍼스 문제  (0) 2018.11.25
[백준_Queue]1966번_프린터 큐  (0) 2018.11.18
[백준_Stack]1874번_스택 수열  (0) 2018.11.11
[백준_Stack]2504번_괄호의 값  (0) 2018.11.06
[백준_Stack]9012번_괄호  (0) 2018.11.04
Trackback: Comment:

티스토리툴바