ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • [java] 백준 알고리즘 10845번 큐 풀이
    알고리즘/백준 알고리즘 2018. 7. 25. 14:37


    큐의 개념을 공부하기 위한 문제이다.


    큐는 스택과 반대되는 개념으로 FIFO(First In, First Out)이다.


    먼저 들어간 녀석이 먼저 나오는 것이다. 


    예를 들어 급식을 받는다고 일렬로 줄을 서있으면


    먼저 배식을 받는 사람이 먼저 배식 줄을 나오는 것과 같은 원리!


    아래는 이해를 돕기위한 발 그림...




    자바에서 라이브러리를 통해 큐를 사용할 수 있지만,


    배열을 통해 직접 한 번 만들어보고 싶었다.


    일반 배열을 큐처럼 만들기 위해 사이즈(dynamicSize)와 0번째 순서(bottom)를 동적으로 만들었다.


    큐에서 pop이 되면 0번째 순서의 다음 순서로 +1로 올라가게 만들고, 사이즈는 -1로 줄어들게 했다.


    반대로 push를 하면 사이즈는 +1로 만들었다.


    제약조건 중 정수가 들지 않았을 경우 -1 출력은


    동적으로 변하는 0번째 순서(bottom)가 동적으로 변하는 size보다 같거나 커지는 순간으로 처리했다.


    이는 큐 안에 정수가 들어있지 않다는 의미와 같다. 



    * 풀이 소스


    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
    71
    72
    73
    74
    75
     
    public class Baekjoon10845{
     
        static StringTokenizer st;
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
            st = new StringTokenizer(br.readLine());
            int orderCount = Integer.parseInt(st.nextToken());
            int[] queue = new int[10001];
            int dynamicSize = 0// 일반 배열을 큐처럼 만들기 위해 동적으로 사이즈를 만들기 위함
            int bottom = 0// 0번째 순서를 동적으로 만들기 위함
            List<Integer> outputArray = new ArrayList<>();
            
            for(int i=0; i<orderCount; i++) {
                st = new StringTokenizer(br.readLine());
                
                switch(st.nextToken()) {
                    case "push":
                        int inputNum = Integer.parseInt(st.nextToken());
                        
                        queue[dynamicSize] = inputNum;
                        dynamicSize++;
                        break;
                        
                    case "pop":
                        
                        if(bottom >= dynamicSize){
                            outputArray.add(-1);
                        }else {
                            outputArray.add(queue[bottom]);
                            bottom++;
                        }
                        break;
                        
                    case "size":
                        outputArray.add(dynamicSize-bottom);
                        break;
                        
                    case "empty":
                        if(bottom >= dynamicSize) {
                            outputArray.add(1);
                        }else {
                            outputArray.add(0);
                        }
                        break;
                    
                    case "front":
                        if(bottom >= dynamicSize) {
                            outputArray.add(-1);
                        }else {
                            outputArray.add(queue[bottom]);
                        }
                        break;
                        
                    case "back":
                        if(bottom >= dynamicSize) {
                            outputArray.add(-1);
                        }else {
                            outputArray.add(queue[dynamicSize-1]);
                        }
                        break;
                }
            }
            
            for(int output : outputArray) {
                bw.write(output+"\n");
                bw.flush();
            }
            
     
        }
     
    }
     
    cs



    댓글 0

Designed by Tistory.