[BOJ_10845/JAVA] 큐

[BOJ_10845/JAVA] 큐

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

문제

풀이

오늘 풀었던 문제는 자료구조의 기본 중의 기본 큐에 대해 공부를 했다.

처음에 Scanner를 써서 값을 입력받았으나... 시간초과가 났다. 저번에 메모리 초과에 이어서 시간초과라니 당황당황;;

보통 자바를 쓰는 사람들이 BufferedReader를 쓰는 사람이 많은데 그 이유가 입출력이 빠르기 때문에 사용한다.

그래서 나도 과감히 BufferedReader로 갈아탔다.

그리고 BufferedReader는 정수 값을 입력받을 때 `readLine()`을 써서 한줄 전체를 입력받은 다음에 int형변환을 해주어야한다.

int num = Integer.parseInt(br.readLine());

위와 같이 해야한다. 만약, 1을 입력했을 때 '1' 아스키값을 인식해 int형으로 변환해서 49를 입력받게된다.

`readLine()`은 공백을 포함해서 한줄 전체를 입력받는 메소드이다.

그리고 출력을 할 때 StringBuilder를 이용하면 속도와 메모리 측면에서 좋다고 해서 사용했다.

(그 이유는 String은 새로운 메모리를 계속해서 생성하고 StringBuilder는 이미 생성한 메모리에 이어서 작성하기 때문..)

더 자세한 설명은 여기 참고

따라서 결과값을 저장하고 싶을 때는 append()를 이용해서 문자열을 계속해서 추가한다.

그리고 마지막으로 StringTokenizer!

이것은 String클래스와 split()과 유사한 역할을 한다. BufferedReader 클래스를 이용해 입력값을 받을 때는 한줄 전체를 입력받을 수 밖에 없다. 우리는 이 클래스를 가지고 공백을 기준으로 문자열을 나눠줄 예정!

나눠진 문자열을 token이라 부른다고 한다.

출처 https://jhnyang.tistory.com/398

StringTokenizer st=new StringTokenizer(br.readLine());

위와 같이 쓰면 공백을 기준으로 문자열을 나눌 수 있다.

그리고 nextToken()은 나눈 문자열을 확인할 수 있다.

휴 클래스가 너무 많아서 정리하자면,

1. BufferedReader (readLine 사용)

2. StringTokenizer (nextToken 사용)

3. StringBuilder (append 함수사용)

지금부터 큐를 어떻게 구현했는지 설명하겠다..!

큐는 삽입과 삭제의 입구가 다르므로 front, back 변수가 따로 있다.

front는 값을 삭제하기위해, back은 값을 삽입하는 변수이다.

1. 값을 삽입/삭제할때마다 ++을 해주어 위치를 이동시켜주었다.

2. 그리고 계속 데이터를 삽입할 수 있는 원형 큐를 만들기위해 front,back이 배열의 크기를 넘어갈때 0으로 초기화해주었다.

3. front와 back이 같으면 큐에 아무것도 없는 상태

4. back은 다음 데이터가 들어갈 위치를 가리키고 있기때문에 back의 원소를 알고 싶을 때는 -1 해주어야한다.

코드

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ10845 { static int front=0; static int back=0; static int size=0; static int [] queue; public static void main(String[] args) throws IOException { // TODO Auto-generated method stub BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; StringBuilder sb = new StringBuilder(); int num = Integer.parseInt(br.readLine()); queue = new int[num]; int top=-1; for(int i=0;i

'); break; case "size" : sb.append(size()).append('

'); break; case "empty" : sb.append(empty()).append('

'); break; case "front": sb.append(front()).append('

'); break; case "back": sb.append(back()).append('

'); break; } } System.out.println(sb); } public static void push(int num) { queue[back++]=num; if(back>=queue.length) { // 추가했을 때 만약 배열의 길이보다 같거나 크면 0으로 초기화 back=0; } size++; } public static int pop() { if(back==front) { // 같으면 배열에 아무것도 없는 상태 return -1; }else { int data = queue[front]; front++; if(front>=queue.length) { // 배열에서 꺼냈을 때 배열의 길이보다 같거나 크면 0으로 초기화 front=0; } size--; return data; } } public static int size() { return size; } public static int empty() { if(size==0) { return 1; }else { return 0; } } public static int front() { if(size==0) { //비어있는 상태 return -1; }else { return queue[front]; } } public static int back() { if(size==0) { //비어있는 상태 return -1; }else if(back==0) { // back은 다음 삽입할 위치를 가리키기에 0일 경우 배열 끝을 반환해야한다. return queue[queue.length-1]; }else { return queue[back-1]; // 다음 삽입할 위치를 가리키기에 -1해줘야한다. } } }

확실히 스택보다 구현이 조금 더 어렵다.

2학년 때 자료구조 수업을 들은 이후 큐를 직접 구현해보는 것은 오랜만이라 낯설다... 그래도 화이팅

from http://silvergal.tistory.com/76 by ccl(A) rewrite - 2021-12-11 21:27:32