0x05 - Stack

Jieun·2024년 4월 30일
0

코테

목록 보기
4/18

java의 Stack 클래스는 Vector를 상속받아 구현되었다

* P10828 - 스택

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P10828 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] stack = new int[10000];
        int c=0;
        int cnt=0;
        while(n-->0) {
            String inStr = br.readLine();
            if(inStr.charAt(1)=='u') {
                StringTokenizer st = new StringTokenizer(inStr," ");
                inStr = st.nextToken();
                c =  Integer.parseInt(st.nextToken());
            }
            if(inStr.equals("push")) {
                stack[cnt++]=c;
            } else if(inStr.equals("pop")) {
                if(cnt==0) {System.out.println(-1); continue;}
                System.out.println(stack[--cnt]);
            } else if(inStr.equals("size")) {
                System.out.println(cnt);
            } else if(inStr.equals("empty")) {
                if(cnt==0) {System.out.println(1);}
                else {{System.out.println(0);}}
            } else if(inStr.equals("top")) {
                if(cnt==0) {System.out.println(-1); continue;}
                System.out.println(stack[cnt-1]);
            }
        }
    }
}

* 10773 - 제로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Iterator;
import java.util.Stack;

public class P10773 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        int result=0;
        for(int i=0;i<n;i++) {
            int k = Integer.parseInt(br.readLine());
            if(k==0) {stack.pop(); continue;}
            stack.add(k);
        }
        Iterator<Integer> iter = stack.iterator();
        while(iter.hasNext()) {result+= iter.next();}
        System.out.print(result);
    }
}

입력받은 수 stack에 push
0 나오면 직전에 받았던 숫자 pop
: Last In을 빼야하는 문제이므로 stack 활용

* P1874 - 스택 수열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class P1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        int in =1; int result=0;
        Stack<Integer> stack = new Stack<>();
        for(int i=0;i<n;i++) {
            int k = Integer.parseInt(br.readLine());
            if(stack.empty()) {
                while(in<=k) {stack.add(in++); sb.append('+');}
                stack.pop(); sb.append('-');
                continue;
            }
            if(k>stack.peek()) {
                while(k>stack.peek()){stack.add(in++); sb.append('+');}
                stack.pop(); sb.append('-');
            } else if(k<stack.peek()) {
                result=1;
                break;
            } else {
                stack.pop(); sb.append('-');
            }
        }
        if(result==1) {
            System.out.println("NO");
        } else {
            for(int i=0;i<sb.length();i++) {
                System.out.println(sb.charAt(i));
            }
        }
    }
}

1. 반드시 오름차순으로 정수를 push하므로,
요구받은 수열이 스택의 최상단보다 작으면 불가능한 수열로 판단함

2. 요구받은 수열이 스택의 최상단보다 크면 해당 수열까지 push한 후 pop

* P9012 - 괄호

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class P9012 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<n;i++) {
            String result="YES";
            String str = br.readLine();
            for(int j=0;j<str.length();j++) {
                if(str.charAt(j)=='(') {stack.add('(');}
                else {
                    if(stack.empty()) {result="NO"; continue;}
                    stack.pop();
                }
            }
            if(!stack.empty()) {result="NO";}
            System.out.println(result);
            stack.clear();
        }
    }
}
  • ( 는 무조건 push
  • )는 pop
    -> )를 만났을때 스택이 비어있다면 or 전부 수행한 후에 스택이 비어있지 않으면 : not valid

* P17413 - 단어 뒤집기2

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class P17413 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        StringBuilder sb = new StringBuilder();
        int in =0;
        Stack<Character> stack = new Stack<>();
        for(int i=0;i<str.length();i++) {
            switch (str.charAt(i)) {
                case '<' :
                    while(!stack.empty()) {sb.append(stack.pop());}
                    in=1;
                    sb.append('<');
                    break;
                case '>' :
                    in=0;
                    sb.append('>');
                    break;
                case ' ' :
                    while(!stack.empty()) {sb.append(stack.pop());}
                    sb.append(' ');
                    break;
                default :
                    if(in==1) {sb.append(str.charAt(i));}
                    else {stack.add(str.charAt(i));}
            }
        }
        if(!stack.empty()) {while(!stack.empty()) {sb.append(stack.pop());}}
        System.out.println(sb);
    }
}
  • 단어뒤집기 : Last In First Out : 스택 사용
  • 괄호 안의 문자 / 괄호 밖의 문자(뒤집어야 함)의 구분 : in 변수 (flag)
  • 전체를 한 번에 뒤집는 것이 아닌, 괄호를 기점으로 뒤집어야 하므로 괄호를 만나면 스택 전부 비움

* P4949 - 균형잡힌 세상

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class P4949 {
   public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       boolean pEnd = true;
       boolean result = true;
       Stack<Character> stack = new Stack<>();
       do {
           String str = br.readLine();
           if (str.equals(".")) { pEnd = false; break; }
           for (int i = 0; i < str.length(); i++) {
               if(str.charAt(i)=='.') { break; }
               switch (str.charAt(i)) {
                   case '(' :
                       stack.push('(');
                       break;
                   case ')' :
                       if (!stack.isEmpty()) {
                           if (stack.peek() == '(') { stack.pop(); break; }
                           else { result = false; break; }
                       } else {
                           result = false;
                           break;
                       }
                   case '[' :
                       stack.push('[');
                       break;
                   case ']' :
                       if (!stack.isEmpty()) {
                           if (stack.peek() == '[') { stack.pop(); break;}
                           else { result = false; break; }
                       } else {
                           result = false;
                           break;
                       }
               }
           }
           if (result && stack.isEmpty()) {
               System.out.println("yes");
           } else {
               System.out.println("no");
           }
           result = true; stack.clear();
       }
       while (pEnd); {}
   }
}

* 틀린풀이

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));
        boolean pEnd = true;
        boolean result = true;
        Stack<Character> stack = new Stack<>();
        do {
            String str = br.readLine();
            if (str.equals(".")) { pEnd = false; }
            for (int i = 0; i < str.length(); i++) {
                switch (str.charAt(i)) {
                    case '.' :
                        break;
                    case '(' :
                        stack.push('(');
                        break;
                    case ')' :
                        if (!stack.isEmpty()) {
                            if (stack.peek() == '(') { stack.pop(); break; }
                            else { result = false; break; }
                        } else {
                            result = false;
                            break;
                        }
                    case '[' :
                        stack.push('[');
                        break;
                    case ']' :
                        if (!stack.isEmpty()) {
                            if (stack.peek() == '[') { stack.pop(); break;}
                            else { result = false; break; }
                        } else {
                            result = false;
                            break;
                        }
                }
            }
            if (result == true && pEnd==true) {
                System.out.println("yes");
            } else if(result==false && pEnd==true) {
                System.out.println("no");
            }
            result = true;
        }
        while (pEnd); {}
    }
}

배운점 : 스택, 큐를 사용할 땐 반드시 루프마다 clear() 해주는 것을 잊지말자 ^-^

* P3986 - 좋은 단어

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));
        int n = Integer.parseInt(br.readLine());
        Stack<Character> stack = new Stack<>();
        int result =0;
        for(int i=0;i<n;i++) {
            String str = br.readLine();
            stack.push(str.charAt(0));
            for(int j=1;j<str.length();j++) {
                if(stack.isEmpty()) {
                    stack.push(str.charAt(j));
                } else {
                    if(stack.peek()==str.charAt(j)) {
                        stack.pop();
                    } else {
                        stack.push(str.charAt(j));
                    }
                }
            }
            if(stack.isEmpty()) {result++;}
            stack.clear();
        }
        System.out.println(result);
    }
}

직전에 나온 단어와 짝을 이루는지 확인하는 문제
: Last In First Out -> 스택을 활용

* P28278 - 스택2

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));
        int n = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        Stack<String> stack = new Stack<>();
        for(int i=0;i<n;i++) {
            String str = br.readLine();
            switch (str.charAt(0)) {
                case '1' :
                    stack.push(str.substring(2));
                    break;
                case '2' :
                    if(!stack.isEmpty()) {sb.append(stack.pop()+"\n");}
                    else {sb.append("-1"+'\n');}
                    break;
                case '3' :
                    sb.append(stack.size()+"\n");
                    break;
                case '4' :
                    if(stack.isEmpty()) {sb.append("1"+'\n');}
                    else {sb.append("0"+'\n');}
                    break;
                case '5' :
                    if(!stack.isEmpty()) {sb.append(stack.peek()+'\n');}
                    else {sb.append("-1"+'\n');}
                    break;
            }
        }
        System.out.println(sb);
    }
}

* P28278 - 시간초과풀이

그냥 주어진 연산을 수행하기만 하면 되는 정말 간단한 문제지만,
시간초과 문제를 마주쳤다.

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));
        int n = Integer.parseInt(br.readLine());
        Stack<String> stack = new Stack<>();
        for(int i=0;i<n;i++) {
            String str = br.readLine();
            switch (str.charAt(0)) {
                case '1' :
                    stack.push(str.substring(2));
                    break;
                case '2' :
                    if(!stack.isEmpty()) {System.out.println(stack.pop());}
                    else {System.out.println(-1);}
                    break;
                case '3' :
                    System.out.println(stack.size());
                    break;
                case '4' :
                    if(stack.isEmpty()) {System.out.println(1);}
                    else {System.out.println(0);}
                    break;
                case '5' :
                    if(!stack.isEmpty()) {System.out.println(stack.peek());}
                    else {System.out.println(-1);}
                    break;
            }
        }
    }
}
  • 알게된점
  • System.out.println()으로 매 루프마다 데이터 출력을 진행하면 속도 현저히 느려진다
  • StringBuilder : 내부 내용을 변경시킬 수 없는 String (불변)과 다르게
    값을 변경해도 같은 주소공간을 참조하여, 값이 변경할 수 있는 가변성을 갖는다.
    → 매 번 출력하는 것보다 StringBuilder로 출력할 값들을 append하여 저장해두고, 마지막에 한 번에 출력하는 것이 시간을 줄일 수 있는 방법이다.
    출력이 많은 문제에서는 매 번 System.out으로 출력하는 것을 지양할 것!!

* P25497 - 기술 연계마스터 임스

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));
        int n = Integer.parseInt(br.readLine());
        Stack<Character> stack = new Stack<>();
        int cnt =0; int in=0;
        String str = br.readLine();
        for(int i=0;i<n;i++) {
            if(str.charAt(i)-'0'>=1 && str.charAt(i)-'0'<=9) {
                cnt++;
            } else if(str.charAt(i)=='L') {
                stack.push('L');
            } else if(str.charAt(i)=='R') {
                in = stack.search('L');
                if(in!=-1) {
                    stack.remove(stack.size()-in);
                    cnt++;
                } else {
                    break;
                }
            } else if(str.charAt(i)=='S') {
                stack.push('S');
            } else if(str.charAt(i)=='K') {
                in = stack.search('S');
                if(in!=-1) {
                    stack.remove(stack.size()-in);
                    cnt++;
                } else {
                    break;
                }
            }
        }
        System.out.println(cnt);
    }
}

  • stack - search() : 스택 내부에 해당 객체가 존재한다면, 위치를 반환한다 : 인덱스가 아닌 빠져나오는 순서, 즉 Last In이 0

  • stakc - remove() : 인덱스로 접근하여 삭제한다.
    → stack.remove(stack.size()-stack.search())를 사용하여 연계기술 사용시 선행기술이 존재하는지 찾고, 존재하면 해당 인덱스로 remove()를 수행했다

  • LIFO도 필요했고 + 인덱스로 접근하는 부분도 필요해서 저 메소드를 사용하긴 했지만, 스택을 사용하면서 LIFO를 어기는 메소드를 쓰는게 맞는지는 모르겠다. 무엇보다 인덱스로 접근하므로 O(n)인 점을 생각하면 시간복잡도 상으로도 바람직하지 못 한 것 같다.

  • 관련하여 생각해볼만한 글 링크
    https://velog.io/@jhl221123/%EC%9E%90%EB%B0%94%EC%9D%98-Stack%EC%9D%80-%EC%99%9C-%EC%82%AC%EC%9A%A9%ED%95%98%EC%A7%80-%EC%95%8A%EB%8A%94-%EA%B1%B8%EA%B9%8C

* P5957 - Cleaning the Dishes

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

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());

        Stack<Integer> stack = new Stack<>();
        for(int i=n;i>=1;i--) {stack.push(i);}

        Stack<Integer> dStack = new Stack<>();
        Stack<Integer> cStack = new Stack<>();
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            if(Integer.parseInt(st.nextToken())==1) {
                int d = Integer.parseInt(st.nextToken());
                for(int j=0;j<d;j++) {
                    if(!stack.isEmpty()) {
                        dStack.push(stack.pop());
                    }
                }
            } else {
                int d = Integer.parseInt(st.nextToken());
                for(int j=0;j<d;j++) {
                    if(!dStack.isEmpty()) {
                        cStack.push(dStack.pop());
                    }
                }
            }
            if(cStack.size()==n) {break;}
        }
        while(!cStack.isEmpty()) {
            System.out.println(cStack.pop());
        }
    }
}
profile
Jieun
이전 포스트

0x04

다음 포스트

0x06 Queue

0개의 댓글