1. 스택 문제 풀이
백준 10828번
https://www.acmicpc.net/problem/10828
package Baekjoonjava;
import java.util.Scanner;
import java.util.Stack;
public class B10828 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in); //scanner이용
Stack<Integer> stack = new Stack<>(); //스택
int num = sc.nextInt(); //반복횟수
for(int i = 0; i < num; i++) {
String order = sc.next();//sc.next는 공백 기준으로 문자열 분리시 사용
switch (order) { //switch 이용
case "push":
stack.push(sc.nextInt());
break;
case "pop":
if(stack.empty()) {
System.out.println(-1);
}
else {
System.out.println(stack.pop());
}
break;
case "size":
System.out.println(stack.size());
break;
case "empty":
if(stack.empty()) {
System.out.println(1);
}
else {
System.out.println(0);
}
break;
case "top":
if(stack.empty()) {
System.out.println(-1);
}
else {
System.out.println(stack.peek());
}
break;
}
}
}
}처음에 풀 때는 scanner를 이용해서 풀었으나 시간초과가 떠서 BufferedReader와 BufferedWriter를 이용해 다시 풀었다.
BufferedReader는 readLine()으로 받아서
BufferedWriter에 write()를 하여
flush() 하면 한 번에 출력이 된다.
또한, System.out.println() 처럼 한 줄 띄어쓰기 출력을 위해서는 "\n"을 꼭 해야한다.
package Baekjoonjava;
import java.io.*;
import java.util.*;
public class B10828_2 {
public static void main(String[] args) throws NumberFormatException, IOException {
Stack<Integer> st = new Stack<Integer>();
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
for(int i=0;i<n;i++) {
String[] s = br.readLine().split(" ");
if(s[0].equals("push")) {
st.push(Integer.parseInt(s[1]));
}
else if(s[0].equals("pop")) {
if(st.empty()) {
bw.write(-1+"\n");
}
else {
bw.write(st.pop()+"\n");
}
}
else if(s[0].equals("size")) {
bw.write(st.size()+"\n");
}
else if(s[0].equals("empty")) {
if(st.empty()) {
bw.write(1+"\n");
}
else {
bw.write(0+"\n");
}
}
else if(s[0].equals("top")) {
if(st.empty()) {
bw.write(-1+"\n");
}
else {
bw.write(st.peek()+"\n");
}
}
}
bw.flush();
}
}주요 구성 요소 및 동작은 다음과 같다.
- 입력 및 출력 스트림 설정:
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- 표준 입력(System.in)을 통해 데이터를 빠르게 읽기 위해 BufferedReader 객체를 생성한다.
- BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
- 표준 출력(System.out)을 통해 데이터를 빠르게 쓰기 위해 BufferedWriter 객체를 생성한다.
- BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
- 스택 선언:
- Stack<Integer> st = new Stack<>();
- 정수를 저장할 스택을 생성한다.
- Stack<Integer> st = new Stack<>();
- 명령어 수 입력 받기:
- int n = Integer.parseInt(br.readLine());
- 명령어의 수를 읽어와 정수로 변환한다.
- int n = Integer.parseInt(br.readLine());
- 명령어 처리:
- for (int i = 0; i < n; i++) {
- 주어진 명령의 수만큼 반복문을 실행한다.
- String[] s = br.readLine().split(" ");
- 각 줄의 명령어를 읽어와 공백을 기준으로 분리한다.
- switch 문을 사용하여 명령어에 따라 실행한다.
- for (int i = 0; i < n; i++) {
- 명령어에 따른 동작:
- if (s[0].equals("push")) {
- push 명령어의 경우:
- 스택에 값을 추가한다. st.push(Integer.parseInt(s[1]));
- push 명령어의 경우:
- else if (s[0].equals("pop")) {
- pop 명령어의 경우:
- 스택이 비어 있는지 확인하고, 비어 있으면 -1을 출력한다.
- 그렇지 않으면 스택의 최상단 값을 제거하고 출력한다.
- pop 명령어의 경우:
- else if (s[0].equals("size")) {
- size 명령어의 경우:
- 스택의 크기를 출력한다.
- size 명령어의 경우:
- else if (s[0].equals("empty")) {
- empty 명령어의 경우:
- 스택이 비어 있으면 1을, 비어 있지 않으면 0을 출력한다.
- empty 명령어의 경우:
- else if (s[0].equals("top")) {
- top 명령어의 경우:
- 스택이 비어 있으면 -1을, 비어 있지 않으면 최상단 값을 출력한다.
- top 명령어의 경우:
- if (s[0].equals("push")) {
- 최종 출력:
- bw.flush();
- 버퍼에 남아 있는 데이터를 모두 출력한다.
- bw.flush();
백준 9012번
https://www.acmicpc.net/problem/9012
알고리즘 [접근 방법]
여는 괄호가 있으면 닫는 괄호가 있어야 하는데, 여는 괄호가 있을 때는 스택에 쌓고(push), 닫는 괄호가 들어오면(push) 여는 괄호를 하나 지우면(pop) 된다.
총 3가지의 경우가 나올 수 있다.
다음은 다른 블로그를 참고한 그림이다.
1. 여는괄호와 닫는 괄호가 올바른 경우
예시 : ( ( ) ( ) ) ( ( ( ) ) )
완전한 수식인 경우 최종적으로 스택에 아무 것도 없어야 한다.
2. 괄호가 남는 경우 (= 여는 괄호가 많은 경우)
예시 : ( ( ( ( ) ( ) ) ( )
모든 괄호를 검사한 후 스택에 괄호가 남는 경우는 여는 괄호가 많은 경우라는 의미다. 즉, 이는 온전한 수식이 아니라는 것이다.
3. 괄호가 부족한 경우 (= 닫는 괄호가 많은 경우)
예시 : ( ( ) ) ( ) )
보면 알겠지만, 이미 6번째 단계에서 pop 을 하면 스택은 비어버리게 된다. 스택이 비었다는 것은 현재 단계까지는 완전한 수식이라는 것이다. 근데 그 다음 단계에서도 닫는 괄호가 나온다면 이미 비어있는 상태에서 더이상 pop 할 요소가 없기 때문에 이는 잘못 된 참조가 되어버리게 된다.
즉, 다른 말로 하자면 이는 닫는 괄호가 더 많다는 것이다.
String s = input(); // 한 줄 입력
for(int i = 0; i < length; i++) { // legnth는 문자열의 길이
char c = s.charAt(i); // i 번째 문자
// 여는 괄호일 경우 스택에 넣는다.
if(c == '(') {
stack.push(c);
}
// 아래는 모두 닫는 괄호 일 경우들이다.
// 스택이 비어있는 경우. 즉, 닫는 괄호를 입력받았으나 pop할 원소가 없을 경우
else if(stack.empty()){
return "NO";
}
// 그 외의 경우 stack 원소를 pop 한다.
else {
stack.pop();
}
}
/*
모든 검사 마치고 스택에 잔여 요소가 있으면 여는 괄호가 많은 경우는 "NO"
스택이 비어있으면 온전한 수식이므로 "YES" 이다.
*/
if(stack.empty()) {
return "YES";
}
else {
return "NO";
}
찾아보니까 3가지 방법을 사용하여 풀이할 수 있는데, 순서대로
첫 번째는, Scanner와 Stack을 이용하는 방법,
두 번째는, BufferedReader와 Stack을 이용하는 방법
세 번째는, BufferedReader와 index를 이용하는 방법이 있다.
첫번째 방법: Scanner와 Stack을 이용하는 방법
package Baekjoonjava;
import java.util.Scanner;
import java.util.Stack;
public class B9012 {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int x = sc.nextInt(); //반복횟수
for(int i=0;i<x;i++) {
System.out.println(function(sc.next()));
}
}
public static String function(String s) {
Stack<Character> stack = new Stack<>();
for(int i=0;i<s.length();i++) {//문자열의 길이만큼 반복
char c=s.charAt(i);//괄호 하나하나
if(c=='(') {//여는 괄호일 경우 스택에 push한다.
stack.push(c);
}
//스택이 비어있는데, 닫는 괄호가 들어올 경우 pop을 못 한다.
else if(stack.empty()){
return "NO";
}
//스택이 비어있지 않으면서(여는 괄호가 있을 경우)인데,
//닫는 괄호가 들어올 경우,
//stack 원소를 pop한다.
else {
stack.pop();
}
}
//검사가 끝나고 스택에 뭐가 남아있으면 "NO"
//스택이 비어있으면 "YES"
if(stack.empty()) {
return "YES";
}else {
return "NO";
}
}
}두 번째는, BufferedReader와 Stack을 이용하는 방법
package Baekjoonjava;
import java.io.*;
import java.util.Stack;
public class B9012_2 {
public static void main(String args[]) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int x = Integer.parseInt(br.readLine());
for(int i=0;i<x;i++) {
sb.append(function(br.readLine())).append('\n');
}
System.out.println(sb);
}
public static String function(String s) {
Stack<Character> stack = new Stack<>();
for(int i=0;i<s.length();i++) {//문자열의 길이만큼 반복
char c=s.charAt(i);//괄호 하나하나
if(c=='(') {//여는 괄호일 경우 스택에 push한다.
stack.push(c);
}
//스택이 비어있는데, 닫는 괄호가 들어올 경우 pop을 못 한다.
else if(stack.empty()){
return "NO";
}
//스택이 비어있지 않으면서(여는 괄호가 있을 경우)인데,
//닫는 괄호가 들어올 경우,
//stack 원소를 pop한다.
else {
stack.pop();
}
}
//검사가 끝나고 스택에 뭐가 남아있으면 "NO"
//스택이 비어있으면 "YES"
if(stack.empty()) {
return "YES";
}else {
return "NO";
}
}
}세 번째는, BufferedReader와 index를 이용하는 방법
괄호 개수를 카운트 하는 방법이다.
스택을 이용할 필요가 없기 때문에 스택을 사용하지 않는다.
package Baekjoonjava;
import java.io.*;
public class B9012_3 {
public static void main(String args[]) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int x = Integer.parseInt(br.readLine());
while(x-- > 0) {
sb.append(function(br.readLine())).append('\n');
}
System.out.println(sb);
}
public static String function(String s) {
int count=0;
for(char c: s.toCharArray()) {
if(c=='(') {//여는 괄호일 경우 카운트 증가
count++;
}
//count가 0인데, 닫는 괄호만 들어올 경우 pop을 못 한다.
else if(count==0){
return "NO";
}
//스택이 비어있지 않으면서(여는 괄호가 있을 경우)인데,
//닫는 괄호가 들어올 경우,
//count를 감소시킨
else {
count--;
}
}
//검사가 끝나고 스택에 뭐가 남아있으면 "NO"
//스택이 비어있으면 "YES"
if(count==0) {
return "YES";
}else {
return "NO";
}
}
}
맨 밑에서부터 첫번째 방법, 두번째 방법은 그 위, 맨 위의 것은 세번째 방법으로 푼 것이다.
백준 10799번
풀려고 도전해봤는데 어떻게 풀어야할지 고민하다가 시간이 다 되어 다음에 풀도록 하겠다.
'스터디 > 2024하계모각코' 카테고리의 다른 글
| [2024 하계모각코] 5주차 목표 (0) | 2024.08.07 |
|---|---|
| [2024 하계모각코] 4주차 목표 (0) | 2024.07.24 |
| [2024 하계모각코] 3주차 결과 (0) | 2024.07.15 |
| [2024 하계모각코] 3주차 목표 (0) | 2024.07.15 |
| [2024 하계모각코] 2주차 결과 (1) | 2024.07.08 |