10828 Stack

import com.sun.source.tree.NewArrayTree;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main{
    public static class Stack{
        //stack을 위해 배열을 선언한다. 배열의 크기는입력크기만큼을 선언한다.
        int arr[];
        //추가가될곳을 가리키는 idx변수를 생성한다
        int input;
        //생성자에서는 배열에 메모리공간을 할당해주고, input을 0으로 설정해준다 
        //input이 0이라는것은 무언가가 추가된다고가정할떄 0번째에 추가된다는 의미이다
        //생성자에서 기본적인 초기값세팅을 해줬다
        Stack(){
            arr = new int[100000 + 1];
            input = 0;
        }
        public int pop(){
            //isEmpty==1이라는것은 비어있다는 뜻이다. 문제요구사항에 맞게 비어있으면 -1을 return한다
            if(isEmpty()==1) return -1;
            //input이라는것은 추가될곳을 가리키는것이다. pop은 내가 가지고있는 가장 바깥쪽 배열을 return 해줘야한다. 그리고 추가될곳의 idx를 -1해주어야하고
            //arr[input]: 추가될값이 들어갈곳, arr[input-1]:stack의 가장 위쪽에 있는 부분
            //input의 값을 --해주는 이유는 삭제의 행위를 구현하기 위함이다
            else return arr[--input];
        }
        //값을 추가한다음에는 input을 추가시켜줘야한다.
        //그래야 다음값이 stack에 차곡차곡쌓이기때문이다.
        public void push(int x){
            arr[input++] = x;
        }
        //input을 곧 추가될곳 으로 설정했기때문에 size로도쓸수있다. 만약에 값이 하나 들어온다면 input=1이될것이고 두개가 들어온다면 input=2가될것이기때문에
        public int size(){
            return input;
        }
        //가장 stack위에있는 값을 return해주고 무언가를 삭제하지는 않는다
        public int top(){
            //stack이 비어있는 경우 값을 return할수가없으니 -1을리턴해준다
            if(isEmpty()==1) return -1;
            //arr[input-1]:stack최상단에 있는 값
            else return arr[input-1];
        }
        public int isEmpty(){
            //input = size를 의미하기때문에 아래와같이 코딩할 수 있다
            if(input == 0) return 1;
            else return 0;
        }

    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack stack = new Stack();
        //n개의 명령이 들어온다
        for(int i=0;i<n;i++){
            //push는 띄어쓰기로 명령어와 숫자가 구분된다. 나머지도 띄어쓰기로 구분할 수 있다.
            String input[] = br.readLine().split(" ");
            if(input[0].equals("push")){
                stack.push(Integer.parseInt(input[1]));
            }
            else if(input[0].equals("top")){
                System.out.println(stack.top());
            }
            else if(input[0].equals("size")){
                System.out.println(stack.size());
            }
            else if(input[0].equals("empty")){
                System.out.println(stack.isEmpty());
            }
            else if(input[0].equals("pop")){
                System.out.println(stack.pop());
            }
        }

    }
}

9012:괄호배치

import com.sun.source.tree.NewArrayTree;

import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main{
    public static class Stack{
        //stack을 구현할 배열
        int arr[];
        //입력이 들어올 idx에 대한 변수
        int idx;
        //문제 조건에서 입력제한으로 주어진 값 50, 이하라고 했으니 50까지 포함하여 51을 선언함
        final int MAX_IDX = 51;
        //생성자에서 초기값 세팅
        Stack(){
            arr = new int[MAX_IDX];
            idx = 0;
        }
        public boolean isEmpty(){
            //idx는 size를 의미하기도함
            //(1개의 값이 들어오면 idx는 +1돼서 1이됨. 2개의 값이 들어오면 idx는 +1+1돼서 2가 됨.)
            if(idx==0) return true;
            else return false;
        }
        public int size(){
            return idx;
        }
        public int push(int x){
            if(x >= MAX_IDX) return -1;
            else {
                //push할 경우엔 idx를 ++ 해주어야 다음 입력값을 계속 받을수 있다
                arr[idx++] = x;
                return 1;
            }
        }
        public int pop(){
            if(isEmpty()) return -1;
            //idx-1인값을 return해주어야한다. arr[idx-1]: stack가장 최상단에 위치한 값 을 의미하기때문
            else return arr[--idx];
        }

    }


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        for(int i=0;i<n;i++){
            //매번 stack을 선언한다. 그이유는 stack에 들어있는 배열의 초기화를 위해서임. 이렇게 안하고 그냥 idx를 매번 0으로 설정해둬도됨
            Stack stack = new Stack();
            //flag = true일경우 VPS가 아니라는 소리.
            boolean flag = false;
            //입력은 매번 받아서 char배열로 변환한뒤 하나씩 검사한다
            String str = br.readLine();
            char ch[] = str.toCharArray();
            for(int k=0;k<ch.length;k++){
                //시작괄호를 넣어주면 stack에 push하고
                if(ch[k]=='('){
                    stack.push(1);
                }
                //끝괄호를 넣어주면 stack를 pop한다.
                //시작과끝개수가 맞지 않으면 결국 stack에는 무언가가 남게된다. 그 size로 VPS의 유무를 판단한다
                else{
                    //위의 로직만 넣으면 ())과 같은것은 처리가 안된다. pop이 여러번 되는 경우도. 그러니까 비어있는데 pop을 시킨다는것은 결국
                    //시작괄호와 끝괄호가 match되지 않았다는 소리니까 flag를 true로 두고 이 경우에도 no를 출력하도록 한다.
                    //시작괄호 < 끝괄호 - flag를 통해 처리
                    //시작괄호 > 끝괄호 - stack 에 무언가가 남음
                    if(stack.pop()==-1){
                        flag = true;
                    }

                }
            }
            if(stack.isEmpty()&& !flag) System.out.println("YES");
            else System.out.println("NO");
        }


    }

}

1935: 후위표기식

import com.sun.source.tree.NewArrayTree;

import java.io.*;
import java.math.BigInteger;

public class Main{
    public static class Stack{
        double arr[];
        int idx;
        final int MAX_IDX = 1000000+1;
        Stack(){
            arr = new double[MAX_IDX];
            idx = 0;
        }
        public void push(double x){
            arr[idx++] = x;
        }
        public boolean isEmpty(){
            if(idx==0) return true;
            else return false;
        }
        public double pop(){
            if(isEmpty()) return -1;
            return arr[--idx];
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Stack stack = new Stack();
        char str[] = br.readLine().toCharArray();
        int num[] = new int[n];
        //n개의 입력을 받아서 수로 저장한다. 이수를 str이 어떤 문자이냐에 따라
        //idx를 다르게 하여 접근할 것이다.
        for(int i=0;i<n;i++){
            num[i] = Integer.parseInt(br.readLine());
        }
        for(int i=0;i<str.length;i++){
            if(str[i]!='*'&&str[i]!='-'&&str[i]!='+'&&str[i]!='/'){
                //'A' - 'A'를 하면 0이나오고, 'B'-'A'를 하면 1이나온다
                //즉,idx로 활용할 수 있다는얘기다
                int idx = str[i] - 'A';
                stack.push(num[idx]);
            }
            else{
                //후위수식은 123+이 있다면 +기준 가장근처에있는 수 두개를 계산하는것이다
                //근처에 있는두수 = stack의 개념과 유사하다
                //숫자는 모두 stack에 넣고 연산자를 만나면 가장 근처 두수를 꺼내서 계산하고
                //그 수를 다시 넣는다. 123+-을 계싼하면 15-이 남게되고 -4가 된다.
                double s1 = stack.pop();
                double s2 = stack.pop();
                if(str[i]=='*') stack.push(s1*s2);
                else if(str[i]=='+') stack.push(s1+s2);
                //AB가 순서대로 들어갔다면 A/B를 진행해야한다
                //그런데 STACK에 넣고 꺼내면 B,A이렇게 나올테니
                //s1/s2가 아닌 s2/s1을 해주어야한다
                else if(str[i]=='/') stack.push(s2/s1);
                else if(str[i]=='-') stack.push(s2-s1);
            }
        }
        System.out.printf("%.2f",stack.pop());

    }

}

1874: 스택수열

import com.sun.source.tree.NewArrayTree;

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;

//내가 push를 무조건 1,2,3,4,...순서대로 즉 오름차순으로 해야한다.
//그러니까 push를 하는 수는 무조건 temp=1로부터 시작해서 push할때마다 +1만큼 증가한다는얘기
public class Main{
    public static class Stack{
        int arr[];
        int idx;
        final int MAX_IDX = 1000000+1;
        Stack(){
            arr = new int[MAX_IDX];
            idx = 0;
        }
        public void push(int x){
            arr[idx++] = x;
        }
        public boolean isEmpty(){
            if(idx==0) return true;
            else return false;
        }
        public int top(){
            if(isEmpty()) return -1;
            return arr[idx-1];
        }
        public int size(){
            return idx;
        }
        public int pop(){
            if(isEmpty()) return -1;
            return arr[--idx];
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        //주어진 문제에서 stack을 활용하라고했으니 stack활용
        Stack stack = new Stack();
        //push,와 pop을 표시할 +,-를 담을 list를 선언해주었다
        ArrayList list = new ArrayList();
        //temp는 1부터시작한다 왜냐하면 stack.push(temp)를 할것이기때문.
        int temp =1;
        //n번의 반복
        for(int i=1;i<=n;i++){
            //입력을 받아서 x에 저장한다
            int x = Integer.parseInt(br.readLine());
            //stack최상단이 x랑 일치하지 않으면 계속해서 push한다
            //pop으로 수열을 만드는것이기때문에 stack의 top에 그 숫자가 없으면 pop으로 출력을 할수가없다
            while(stack.top()!=x){
                //내가 push를 했다면 push에 대한 + char를 추가시켜주어야한다
                list.add('+');
                stack.push(temp++);
                //계속 stack에 push하고있다는것은 아무리 push를 해도 stack.top이랑 일치하는
                //값이 없다는얘기다
                //stack.size가 n보다 커지는 경우는 없다. n보다 커진다는것은 n보다 큰 숫자를 넣고있다는의미이기때문이다
                //그 경우에는 함수를 끝내준다
                if(stack.size() > n) {
                    System.out.println("NO");
                    return;
                }
            }
            //스택의 최상단의 값이 x랑 일치하다면 pop을 해주고
            //pop을했다는 표시로 출력연산자list에 - 을 추가시켜줘야한다
            if(stack.top()==x){
                stack.pop();
                list.add('-');
            }
        }
        list.forEach(System.out::println);
    }

}

10799

풀이

자세히보면 () 에서만 레이저가 나가고 있다.
)앞에 (가 있다면 레이저가 나가는것이고, 레이저가 나가면 여러 나무조각을 자르게 된다. 그 나무조각은 앞에 (의 개수만큼이다
또한 ))이 연속으로 나오게 된다면 그것은 나무조각이 하나 더생김을 의미한다. 나무조각이 하나더생기는것만으로는 여러조각을 자를 수 없고, 한조각이 더 늘어남을 의미한다