문제 : https://www.acmicpc.net/problem/18258
18258번: 큐 2
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
풀이
문제 자체는 쉽다. Queue에 대한 기본 개념만 있으면 쉽게 구현할 수 있다.
다만 계속 '시간초과'가 떠서 이를 해결하는 데 초점을 맞춰야 한다.
시간초과를 해결하기 위해서는 아래 방법들이 있다.
1. 시간이 오래 걸리는 Scanner나 System.out.print() 대신 => BufferedReader, BufferedWriter를 사용한다
- 입력된 데이터를 바로 전달되지 않고 buffer에 모았다가 한번에 전달하므로 데이터 처리 효율성을 높인다. 다만 입력받은 데이터를 전부 String타입으로 고정하기 때문에 다른 타입으로 변환하는 가공 작업이 필요하다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
2. StringBuilder를 사용해서 output을 한번에 출력한다
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
class Queue{
StringBuilder sb = new StringBuilder();
LinkedList<Integer> list = new LinkedList<Integer>();
public void push(int x) {
list.add(x);
}
public void pop() throws IOException {
//가장 앞에 있는 정수를 빼고 그 수를 출력한다
//만일 큐에 들어있는 정수가 없으면 -1 출력
sb.append(list.isEmpty()? "-1": list.poll());
sb.append("\n");
}
public void size() throws IOException {
//큐에 들어있는 정수의 개수를 출력한다
sb.append(list.size() + "\n");
}
public void empty() throws IOException {
//큐가 비어있으면 1, 아니면 0 출력
sb.append(list.isEmpty()?"1":"0");
sb.append("\n");
}
public void front() throws IOException {
//가장 앞에 있는 정수를 출력
//만약 큐에 들어있는 정수가 없으면 -1 출력
sb.append(list.isEmpty() ? "-1" : list.getFirst());
sb.append("\n");
}
public void back() throws IOException {
//가장 뒤에 있는 정수를 출력
//만약 큐에 들어있는 정수가 없는 경우 -1 출력
sb.append(list.isEmpty()? "-1" : list.getLast());
sb.append("\n");
}
public void print() {
System.out.print(sb);
}
}
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Queue q = new Queue();
String command[] = new String[n];
for(int i = 0; i<n; i++) {
command[i] = br.readLine();
}
for(int i = 0; i<n; i++) {
String tmp = command[i];
switch(tmp) {
case "front":
q.front();
break;
case "pop":
q.pop();
break;
case "size":
q.size();
break;
case "empty":
q.empty();
break;
case "back":
q.back();
break;
default:
String sx = tmp.substring(5);
int x = Integer.parseInt(sx);
q.push(x);
}
}
q.print();
br.close();
}
}
참고자료
https://docs.oracle.com/javase/8/docs/api/java/io/BufferedReader.html
BufferedReader (Java Platform SE 8 )
Reads characters into a portion of an array. This method implements the general contract of the corresponding read method of the Reader class. As an additional convenience, it attempts to read as many characters as possible by repeatedly invoking the read
docs.oracle.com
https://jhnyang.tistory.com/92
[Java 자바 입출력] BufferedReader/BufferedWriter
[자바 입출력 함수] BufferedReader / BufferWriter BufferedReader/BufferedWriter은 이름처럼 버퍼를 이용해서 읽고 쓰는 함수입니다. 이 함수는 버퍼를 이용하기 때문에 이 함수를 이용하면 입출력의 효율이..
jhnyang.tistory.com
https://yeon-kr.tistory.com/152
(Java)ArrayList vs LinkedList 시간 복잡도
1) 서론 Selenium과 JSoup을 이용해서 크롤링을 하다 보면 데이터를 가지고 오고, 추가하는 작업을 많이 하게 됩니다. 그럴 때 반복적으로 사용하게 되는 것이 List 인터페이스와 For loop입니다. 하지만
yeon-kr.tistory.com
'알고리즘 > 백준' 카테고리의 다른 글
| [백준2606/java] 바이러스 (0) | 2023.05.12 |
|---|---|
| [백준/java] 1260번 - DFS와 BFS (1) | 2023.05.12 |
| [백준/java] 2164번 - 카드2 (0) | 2023.05.12 |
| [백준/java] 2630번 - 색종이 만들기 (0) | 2023.05.12 |
| [백준/java] 4949번 : 균형잡힌 세상 (0) | 2023.05.12 |
