백준
백준 닷컴 단계 별로 풀어보기 16단계
CD가참둥그렇다
2023. 10. 22. 19:25
1단계 스택 2
- 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
- 명령은 총 다섯 가지이다.
-
- 1 x: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
-
- 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
-
- 3: 스택에 들어있는 정수의 개수를 출력한다.
-
- 4: 스택이 비어있으면 1, 아니면 0을 출력한다.
-
- 5: 스택에 정수가 있다면 맨 위의 정수를 출력한다. 없다면 -1을 대신 출력한다.
-
- 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
- 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.
import java.io.*;
import java.util.*;
public class Step_1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
Stack<Integer> stInt = new Stack<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String temp = st.nextToken();
if (temp.equals("1")) {
stInt.push(Integer.parseInt(st.nextToken()));
}
if (temp.equals("2")) {
if (stInt.empty()) {
bw.write("-1\\n");
} else {
bw.write(stInt.peek() + "\\n");
stInt.pop();
}
}
if (temp.equals("3")) {
bw.write(stInt.size() + "\\n");
}
if (temp.equals("4")) {
if (stInt.empty()) {
bw.write("1\\n");
} else {
bw.write("0\\n");
}
}
if (temp.equals("5")) {
if (stInt.empty()) {
bw.write("-1\\n");
} else {
bw.write(stInt.peek() + "\\n");
}
}
}
bw.flush();
bw.close();
}
}
A.
- stack 클래스의 메소드를 사용하여 명령을 수행한다.
2단계 제로
- 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000)
- 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다.
- 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할 수 있다.
- 재민이가 최종적으로 적어 낸 수의 합을 출력한다. 최종적으로 적어낸 수의 합은 231-1보다 작거나 같은 정수이다.
import java.io.*;
import java.util.*;
public class Step_2 {
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 n = Integer.parseInt(br.readLine());
Stack<Integer> stInt = new Stack<>();
long sum = 0;
for(int i=0; i<n; i++) {
int temp = Integer.parseInt(br.readLine());
if(temp==0) {
stInt.pop();
} else {
stInt.push(temp);
}
}
while(!stInt.empty()) {
sum+=(long)stInt.peek();
stInt.pop();
}
bw.write(sum+"");
bw.flush();
bw.close();
}
}
A.
- stack 을 만들어 정수를 저장하여 계산한다.
- 입력된 수를 stack에 저장하고 0이 입력된 경우 stack.pop()을 하도록 한다.
- 입력 완료 후 stack.peek()의 값을 long sum에 더하고 stack.pop()하도록 하는 반복문을 만든다.
3단계 괄호
- 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(concatenation)시킨 새로운 문자열 xy도 VPS 가 된다. 예를 들어 “(())()”와 “((()))” 는 VPS 이지만 “(()(”, “(())()))” , 그리고 “(()” 는 모두 VPS 가 아닌 문자열이다.
- 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 주어진다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 괄호 문자열이 한 줄에 주어진다. 하나의 괄호 문자열의 길이는 2 이상 50 이하이다.
- 출력은 표준 출력을 사용한다. 만일 입력 괄호 문자열이 올바른 괄호 문자열(VPS)이면 “YES”, 아니면 “NO”를 한 줄에 하나씩 차례대로 출력해야 한다.
import java.io.*;
import java.util.*;
public class Step_3 {
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 n = Integer.parseInt(br.readLine());
Stack<Boolean> vps = new Stack<>();
for(int i=0; i<n; i++) {
String str = br.readLine();
vps.clear();
boolean temp=true;
for(int j=0; j<str.length(); j++) {
if(str.charAt(j)=='(') {
vps.push(true);
} else {
if(vps.empty()) {
temp=false;
break;
}
vps.pop();
}
}
if(temp&&vps.empty()) {
bw.write("YES\\n");
} else {
bw.write("NO\\n");
}
}
bw.flush();
bw.close();
}
}
A.
- stack이 아니더라도 연산할 수 있다.
- (가 등장 시 stack에 값을 채우고, )가 등장 시 stack의 값을 날리도록 한다.
- 연산 중간에 stack이 비어있는 상태에서 )가 등장하거나, 마지막 괄호 처리 후 stack이 비어있지 않다면 NO, 그 이외는 YES를 출력하도록 한다.
4단계 균형잡힌 세상
- 각 문자열은 마지막 글자를 제외하고 영문 알파벳, 공백, 소괄호("( )"), 대괄호("[ ]")로 이루어져 있으며, 온점(".")으로 끝나고, 길이는 100글자보다 작거나 같다.
- 각 줄마다 해당 문자열이 균형을 이루고 있으면 "yes"를, 아니면 "no"를 출력한다.
import java.io.*;
import java.util.*;
public class Step_4 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
Stack<Boolean> vps = new Stack<>();
while (true) {
String str = br.readLine();
if(str.equals(".")) {
break;
}
vps.clear();
boolean temp = true;
for (int j = 0; j < str.length(); j++) {
if (str.charAt(j) == '(') {
vps.push(true);
} else if (str.charAt(j) == '[') {
vps.push(false);
} else {
if (str.charAt(j) == ')') {
if (vps.empty()) {
temp = false;
break;
}
if (vps.peek() == false) {
temp = false;
break;
} else {
vps.pop();
}
}
if (str.charAt(j) == ']') {
if (vps.empty()) {
temp = false;
break;
}
if (vps.peek() == true) {
temp = false;
break;
} else {
vps.pop();
}
}
}
}
if (temp && vps.empty()) {
bw.write("yes\\n");
} else {
bw.write("no\\n");
}
}
bw.flush();
bw.close();
}
}
A.
- 소괄호와 대괄호가 입력될 때 스택에 true와 false를 저장하고, 각 값에 맞다면 pop하는 반복문을 만들어줄 수 있다.
- 소괄호를 true, 대괄호를 false로 저장하고, 소괄호가 닫힐 때 stack.peek()가 true일 경우 pop()처리 하고, false인 경우 그 문장을 no로 출력하게 할 수 있다.
- 각 문장이 균형잡힌 문장인 경우 yes를 출력하게 된다.
5단계 도키도키 간식드리미
- 입력의 첫째 줄에는 현재 승환이의 앞에 서 있는 학생들의 수 N(1 ≤ N ≤ 1,000,자연수)이 주어진다.
- 다음 줄에는 승환이 앞에 서있는 모든 학생들의 번호표(1,2,...,N) 순서가 앞에서부터 뒤 순서로 주어진다.
- 승환이가 무사히 간식을 받을 수 있으면 "Nice"(따옴표는 제외)를 출력하고 그렇지 않다면 "Sad"(따옴표는 제외)를 출력한다.
import java.io.*;
import java.util.*;
public class Step_5 {
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 n = Integer.parseInt(br.readLine());
Queue<Integer> qu = new LinkedList<>();
Stack<Integer> stack = new Stack<>();
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
qu.offer(Integer.parseInt(st.nextToken()));
}
int count = 1;
while (true) {
if (qu.contains(count)) {
while (true) {
if (qu.peek() == count) {
qu.remove();
count++;
break;
}
stack.push(qu.poll());
}
}
if (stack.contains(count)) {
if(stack.peek()==count) {
stack.pop();
count++;
} else {
bw.write("Sad");
break;
}
}
if (qu.isEmpty()) {
bw.write("Nice");
break;
}
}
bw.flush();
bw.close();
}
}
A.
- 입력 값을 queue에 받아준다.
- 옆길을 의미하는 stack을 만들어준다.
- 1부터 순서대로이므로 int count=1로 선언하고 반복문을 작성한다.
- count가 queue에 있다면 해당 숫자가 등장할 때 까지 queue.peek의 값을 stack에 담아준다.
- count를 찾은 경우 해당 숫자를 remove해주고 count++을 해준다.
- count가 stack에 있는 경우 stack의 peek값이 count라면 stack을 pop해주고 count++을 해준다.
- 그렇지 않다면 반복문을 종료하고 Sad를 출력한다.
- 반복문이 동작하여 queue.empty가 true인 경우 반복문을 종료하고 Nice를 출력한다.
6단계 큐 2
- 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
- 출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
package stage16;
import java.io.*;
import java.util.*;
public class Step_6 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
Deque<Integer> deq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
String str = st.nextToken();
if (str.equals("push")) {
deq.offer(Integer.parseInt(st.nextToken()));
} else if (str.equals("pop")) {
if (deq.isEmpty()) {
bw.write("-1\\n");
} else {
bw.write(deq.poll() + "\\n");
}
} else if (str.equals("size")) {
bw.write(deq.size()+"\\n");
} else if (str.equals("empty")) {
if (deq.isEmpty()) {
bw.write("1\\n");
} else {
bw.write("0\\n");
}
} else if (str.equals("front")) {
if (deq.isEmpty()) {
bw.write("-1\\n");
} else {
bw.write(deq.peek()+"\\n");
}
} else if (str.equals("back")) {
if (deq.isEmpty()) {
bw.write("-1\\n");
} else {
bw.write(deq.peekLast()+"\\n");
}
}
}
bw.flush();
bw.close();
}
}
A.
- 값을 deque에 받아준다.
- 각 명령에 맞춰 실행하고 출력한다.
7단계 카드 2
- 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
- N이 주어졌을 때, 제일 마지막에 남게 되는 카드를 구하는 프로그램을 작성하시오.
import java.io.*;
import java.util.*;
public class Step_7 {
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 n = Integer.parseInt(br.readLine());
Deque<Integer> card = new ArrayDeque<Integer>();
for (int i=0; i<n; i++) {
card.offer(i+1);
}
while(card.size()!=1) {
card.removeFirst();
card.offer(card.poll());
}
bw.write(card.getFirst()+"\\n");
bw.flush();
bw.close();
}
}
A.
- 값을 deque에 받아준다.
- 반복문을 덱의 크기가 1이 될 때까지로 설정하고 마지막 남은 덱의 요소를 출력한다.
8단계 요세푸스 문제 0
- 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다.
- 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
- <3, 6, 2, 7, 5, 1, 4> 예제와 같이 요세푸스 순열을 출력한다.
import java.io.*;
import java.util.*;
public class Step_8 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
Deque<Integer> man = new ArrayDeque<Integer>();
for (int i=0; i<n; i++) {
man.offer(i+1);
}
bw.write("<");
while(man.size()>1) {
for(int i=0;i<k-1;i++) {
man.offer(man.poll());
}
bw.write(man.poll()+", ");
}
bw.write(man.poll()+">");
bw.flush();
bw.close();
}
}
A.
- 값을 deque에 받아준다.(큐도 무관)
- 덱에 숫자를 입력한다.
- 반복문을 덱 크기가 1이 될 때 까지로 설정한다.
- 각 반복문에서 k-1번은 맨 앞의 값을 맨 뒤로 보내도록 한다.
- k번째 값을 출력하도록 한다.
- 반복문 종료 후 마지막 값을 출력하고 양식에 맞도록 수정한다.
9단계 덱 2
- 첫째 줄에 명령의 수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
- 둘째 줄부터 N개 줄에 명령이 하나씩 주어진다.
- 출력을 요구하는 명령은 하나 이상 주어진다.
- 출력을 요구하는 명령이 주어질 때마다 명령의 결과를 한 줄에 하나씩 출력한다.
import java.io.*;
import java.util.*;
public class Step_9 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
Deque<Integer> de = new ArrayDeque<Integer>();
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
int t = Integer.parseInt(st.nextToken());
switch (t) {
case 1:
de.offerFirst(Integer.parseInt(st.nextToken()));
break;
case 2:
de.offer(Integer.parseInt(st.nextToken()));
break;
case 3:
if (de.isEmpty()) {
bw.write("-1\\n");
} else {
bw.write(de.pollFirst() + "\\n");
}
break;
case 4:
if (de.isEmpty()) {
bw.write("-1\\n");
} else {
bw.write(de.pollLast() + "\\n");
}
break;
case 5:
bw.write(de.size() + "\\n");
break;
case 6:
if (de.isEmpty()) {
bw.write("1\\n");
} else {
bw.write("0\\n");
}
break;
case 7:
if (de.isEmpty()) {
bw.write("-1\\n");
} else {
bw.write(de.getFirst() + "\\n");
}
break;
case 8:
if (de.isEmpty()) {
bw.write("-1\\n");
} else {
bw.write(de.getLast() + "\\n");
}
break;
}
}
bw.flush();
bw.close();
}
}
A.
- 값을 deque에 받아준다.(큐도 무관)
- 반복문을 만들고 해당하는 명령을 수행하는 조건문을 만든다.
10단계 풍선 터뜨리기
- 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선이 있다. 각 풍선 안에는 종이가 하나 들어있고, 종이에는 -N보다 크거나 같고, N보다 작거나 같은 정수가 하나 적혀있다. 이 풍선들을 다음과 같은 규칙으로 터뜨린다.
- 우선, 제일 처음에는 1번 풍선을 터뜨린다. 다음에는 풍선 안에 있는 종이를 꺼내어 그 종이에 적혀있는 값만큼 이동하여 다음 풍선을 터뜨린다. 양수가 적혀 있을 경우에는 오른쪽으로, 음수가 적혀 있을 때는 왼쪽으로 이동한다. 이동할 때에는 이미 터진 풍선은 빼고 이동한다.
- 첫째 줄에 자연수 N(1 ≤ N ≤ 1,000)이 주어진다. 다음 줄에는 차례로 각 풍선 안의 종이에 적혀 있는 수가 주어진다. 종이에 0은 적혀있지 않다.
- 첫째 줄에 터진 풍선의 번호를 차례로 나열한다.
import java.io.*;
import java.util.*;
public class Step_10 {
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 n = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
Deque<Integer> deNum = new ArrayDeque<Integer>();
Deque<Integer> deMove = new ArrayDeque<Integer>();
for (int i = 0; i < n; i++) {
deNum.offer(i + 1);
deMove.offer(Integer.parseInt(st.nextToken()));
}
int move = deMove.poll();
int num = deNum.poll();
bw.write(num + " ");
for (int i = 0; i < n - 1; i++) {
if (move > 0) {
for (int j = 0; j < move - 1; j++) {
deMove.offer(deMove.poll());
deNum.offer(deNum.poll());
}
move = deMove.poll();
num = deNum.poll();
} else {
for (int j = 0; j < move * (-1) - 1; j++) {
deMove.offerFirst(deMove.pollLast());
deNum.offerFirst(deNum.pollLast());
}
move = deMove.pollLast();
num = deNum.pollLast();
}
if (i != n - 1) {
bw.write(num + " ");
} else {
bw.write(num);
}
}
bw.flush();
bw.close();
}
}
A.
- 풍선 번호를 지정할 덱과 이동 좌표를 지정할 덱을 만들고 값을 대입한다.
- 이동 좌표 절대값 -1만큼 덱의 값을 앞/뒤로 옮기고, 마지막 값을 출력한다.
11단계 queuestack
package temp;
import java.io.*;
import java.util.*;
public class Step_11 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
int n = Integer.parseInt(br.readLine());
Deque<Integer> de = new ArrayDeque<Integer>();
boolean[] check = new boolean[n];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
int temp = Integer.parseInt(st.nextToken());
if (temp == 0) {
check[i] = true;
}
}
st = new StringTokenizer(br.readLine());
for (int i = 0; i < n; i++) {
int temp = Integer.parseInt(st.nextToken());
if (check[i]) {
de.offerFirst(temp);
}
}
int test = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < test; i++) {
de.offer(Integer.parseInt(st.nextToken()));
if (i != test - 1) {
bw.write(de.poll() + " ");
} else {
bw.write(de.poll() + "");
}
}
bw.flush();
bw.close();
}
}
A.
- 내용의 결과물을 요약하면 stack의 경우는 무시하고, queue인 경우만 체크하여 deque에 값을 부여한다.
- 출력은 뒤에서부터 시행되고, 테스트 케이스는 앞에서부터 시행된다.
- 반복문을 통해 queue에 들어갈 값을 deque의 앞부터 채워 넣는다.
- 테스트 케이스는 deque의 뒤부터 채워넣고, 테스트케이스만큼 deque의 앞부터의 값을 출력한다.