PS
[백준] 스택, 큐 문제들 (10828, 1406, 1966, 1158)
by solanarey
2024. 9. 25.
스택(10828)
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));
int n = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
Stack<Integer> stack = new Stack<>();
while (n-- > 0) {
String[] command = br.readLine().split(" ");
switch (command[0]) {
case "push":
int val = Integer.parseInt(command[1]);
stack.push(val);
break;
case "pop":
sb.append(stack.isEmpty() ? -1 : stack.pop()).append("\n");
break;
case "size":
sb.append(stack.size()).append("\n");
break;
case "empty":
sb.append(stack.isEmpty() ? 1 : 0).append("\n");
break;
case "top":
sb.append(stack.isEmpty() ? -1 : stack.peek()).append("\n");
}
}
System.out.println(sb);
}
static class Stack<T> {
Node<T> top; // 스택 최상단
int size; // 스택 사이즈
static class Node<T> { // 스택의 각 요소
T data;
Node<T> next; // top의 바로 아래 요소를 가리킴
public Node(T data) {
this.data = data;
}
}
void push(T data) {
Node<T> node = new Node<>(data);
node.next = top; // 새 요소의 next를 현재 top(꼭대기)가 가리키는 노드로 설정
top = node; // 꼭대기를 새 노드로 갱신시킴
size++;
}
T pop() {
if (isEmpty()) throw new EmptyStackException();
T data = top.data; // top에 있는 요소를 변수에 담아 반환
top = top.next; // top 요소의 아래 요소를 top으로 갱신시킴
size--;
return data;
}
int size() {
return size;
}
T peek() {
if (isEmpty()) throw new EmptyStackException();
return top.data;
}
boolean isEmpty() {
return top == null;
}
}
}
에디터(1406)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
Stack<Character> left = new Stack<>();
Stack<Character> right = new Stack<>();
StringBuilder sb = new StringBuilder();
/*
* 커서 기준 왼쪽의 요소들은 left에 저장, 오른쪽 요소들은 right에 저장
* abc
* 9
* L ab / c
* L a / cb
* L / cba
* L / cba
* L / cba
* P x x / cba
* L / cbax
* B / cbax
* P y y / cbax
* */
for (int i = 0; i < input.length(); i++)
left.push(input.charAt(i)); // 제일처음 커서의 위치는 맨 뒤이므로 커서 기준 왼쪽 문자열들을 전부 left 스택에 저장
int n = Integer.parseInt(br.readLine());
while (n-- > 0) {
String[] command = br.readLine().split(" ");
switch (command[0]) {
case "P":
char ch = command[1].charAt(0);
left.push(ch); // 커서 기준 왼쪽에 입력하는 명령어이므로 left에 저장함
break;
case "L":
if (!left.isEmpty()) right.push(left.pop());
break;
case "D":
if (!right.isEmpty()) left.push(right.pop());
break;
case "B":
if (!left.isEmpty()) left.pop();
}
}
for (char ch : left) sb.append(ch);
while (!right.isEmpty()) sb.append(right.pop()); // 커서 오른쪽 요소들도 순서대로 출력하기위해 위에서부터 꺼냄
System.out.println(sb);
}
}
| 메모리 |
시간 |
| 150824 |
696 |
| - 특이사항으로는 처음엔 동적배열을 이용하여 단순하게 문제의 요구사항대로만 풀었다가 시간 초과가 발생했음. |
|
| |
|
| |
|
프린트 큐(1966)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
//A B C D 각 문서의 중요도가 2 1 4 3 이라면
//C D A B 순으로 출력
//0번째부터 시작 중요도가 같다면 그냥 순서대로
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int t = Integer.parseInt(br.readLine());
for (int i = 0; i < t; i++) {
st = new StringTokenizer(br.readLine(), " ");
int n = Integer.parseInt(st.nextToken()); // 문서의 개수
int m = Integer.parseInt(st.nextToken()); // 몇번째로 출력되었는지 궁금한 문서
st = new StringTokenizer(br.readLine(), " ");
Queue<int[]> importance = new LinkedList<>();
for (int j = 0; j < n; j++) {
importance.add(new int[]{j, Integer.parseInt(st.nextToken())}); // [문서의 위치, 문서의 중요도]
}
int cnt = 0;
boolean canPrint; // 현재 문서 출력 가능여부
while (!importance.isEmpty()) {
int[] current = importance.poll();
canPrint = true;
for (int[] q : importance) {
if (current[1] < q[1]) { // 큐의 처음요소와 그 다음요소의 중요도를 비교함
canPrint = false; // 중요도가 낮은 문서라면 출력할 수 없으니 false로 저장
break;
}
}
if (canPrint) { // 현재 문서가 뒤의 문서보다 중요도가 높은 문서라면 출력 가능하므로 카운트시킨다
cnt++;
if (current[0] == m) break; // 현재문서가 입력으로 받은 찾고자하는 문서라면 멈춘다
} else {
importance.add(current); // 중요도가 낮은 것을 맨뒤에 추가
}
}
System.out.println(cnt);
}
}
}
요세푸스 순열(1158)
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 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
Queue<Integer> q = new LinkedList<>();
for (int i = 1; i <= n; i++) q.add(i); // 1부터 n까지 큐에 추가
StringBuilder sb = new StringBuilder();
sb.append("<");
while (!q.isEmpty()) {
for (int i = 1; i < k; i++) { // k 이전까지의 숫자는 큐에서 빼내어 맨 뒤에 추가한다
q.add(q.poll());
}
if (q.size() == 1) { // 큐의 요소가 마지막 한 개 남았을 때는 반점을 붙이면 안됨
sb.append(q.poll());
} else {
sb.append(q.poll()).append(", "); // 현재 큐의 가장 앞에있는사람은 k번 사람임. k번째 사람을 큐에서 빼내고 출력하기위해 스트링빌더에 추가
}
}
sb.append(">");
System.out.println(sb);
}
}
