[백준] 10845번 큐 JAVA (자바) 풀이

문제 10828번

 : 아래와 같은 [명령] 큐로 구현해보기 

 

 [명령]

  

push X	정수 X를 큐 넣는 연산
pop	큐에서 가장 앞에 있는 정수를 빼고 그 수를 출력, 큐에 정수가 없는 경우에 -1을 출력
size	큐에 들어있는 정수의 개수 출력
empty	큐가 비어있으면 1, 아니면 0 출력
front	큐의 가장 에 있는 정수를 출력. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력
back	큐의 가장 뒤에 있는 정수를 출력. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력

 

 [입력]

 : 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)

 : 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다

 

 

 [출력]

 : 명령 출력할 때마다 한 줄에 하나씩 출력

 [큐]

 : 큐는 들어가는 문 하나 나가는 문 하나

 : 선입선출 (후입선출인 스택과는 조금 다르다 얘는 들어왔던 순서대로 나갈 수 있다)  

   예) 1 - 3 - 5 순서대로 push 하고 pop 하면 맨 처음에 들어온 1 나간다

 

 

 [큐 연산]

 

init()	큐 초기화
create()	큐 생성
isEmpty()	큐 비어있는지 검사
isFull()	큐 가득 찼는지 검사
enqueue(e)	큐 맨 뒤에 e 추가
dequeue()	큐 맨 앞의 값 삭제
peek()	큐 맨 앞의 값 출력 (큐가 비어있는 경우 null 반환)
element()	큐 맨 앞의 값 출력 (큐가 비어 있는 경우 에러 발생)
offer(e)	큐의 맨 뒤에 e 추가 (큐가 비어있는 경우 null 반환)
add(e)	큐의 맨 뒤에 e 추가(큐가 비어 있는 경우 에러 발생)
poll()	큐의 맨 앞의 값 제거하고 출력 (큐가 비어있는 경우 null 반환)
remove()	큐의 맨 앞의 값 제거하고 출력 (큐가 비어 있는 경우 에러 발생)

 *            :  코드 구현에 사용된 것

 

 

 [코드 수정 전]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        int T = Integer.parseInt(br.readLine());
        Quque<Integer> que = new LinkedList<>();
        
        while(T-->0){
           String s = br.readLine();
           String spt[] = s.split(" ");
            switch(spt[0]){
                case "push":
                  que.offer(Integer.parseInt(spt[1]));
                break;
                    
                case "pop":
                  if(que.isEmpty())
                      bw.write(-1+"\n");
                  else
                      bw.write(que.poll()+"\n");
                break;
                
                case "size":
                      bw.write(que.size()+"\n");
                break;
                
                case "empty":
                  if(que.isEmpty())
                      bw.write(1+"\n");
                  else 
                      bw.write(0+"\n");
                break;
                
                case "front":
                  if(que.isEmpty())
                      bw.write(-1+"\n");
                  else 
                      bw.write(que.peek()+"\n");
                break;
            }
        }
        bw.flush();
    }
}

 

 [해설 1]

 :  int T = Integer.parseInt(br.readLine()); 첫줄에 명령수        

 :  Quque<Integer> que = new LinkedList<>(); 큐선언
        
 :  String s = br.readLine(); 둘째줄부터 입력받는 명령어
 
 :  String spt[] = s.split(" "); 공백으로 문자 구분하기 
           

 :  switch(spt[0]){ 는 if(s.contains())문으로 대신해도 좋다
               

 -  명령 대부분의 것들은 큐(Queue) 연산으로 바로 구현이 가능하다

    단, back 명령어를 바로 수행할 수 있는 연산이 없어서 직접 만들어줘야된다

    그렇게 되면 복잡하기 때문에 덱(Deque)으로 바꿔 구현하면 훨씬 더 편하다

    (덱의 peekLast라는 명령어를 쓰면 된다)

 

 

 [코드 수정 후]

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
        int T = Integer.parseInt(br.readLine());
        Deque<Integer> que = new LinkedList<>(); //수정부분
        
        while(T-->0){
           String s = br.readLine();
           String spt[] = s.split(" ");
            switch(spt[0]){
                case "push":
                  que.offer(Integer.parseInt(spt[1]));
                break;
                    
                case "pop":
                  if(que.isEmpty())
                      bw.write(-1+"\n");
                  else
                      bw.write(que.poll()+"\n");
                break;
                
                case "size":
                      bw.write(que.size()+"\n");
                break;
                
                case "empty":
                  if(que.isEmpty())
                      bw.write(1+"\n");
                  else 
                      bw.write(0+"\n");
                break;
                
                case "front":
                  if(que.isEmpty())
                      bw.write(-1+"\n");
                  else 
                      bw.write(que.peek()+"\n");
                break;
                
                case "back":                //수정부분
                  if(que.isEmpty())
                      bw.write(-1+"\n");
                  else
                      bw.write(que.peekLast()+"\n");
                break;
            }
        }
        bw.flush();
    }
}

                                                         

 [해설 2]

 

 :  Quque<Integer> que = new LinkedList<>(); 를 Deque<Integer> que = new LinkedList<>(); 로 바꾼다

 

 :  bw.write(que.peekLast()+"\n"); 덱의 마지막 값을 출력하는 연산이 peekLast이다

 

 

 

이제 풀어보러 갈께요 :)

 

 

https://www.acmicpc.net/problem/10845

10845번: 큐

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *