[백준 3425] 고스택 -JAVA //le_effort//

고스택 성공

 

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	2938	429	306	14.599%

문제

고창영은 스택을 조금 변형해서 고스택을 만들었다.

고스택은 숫자만을 저장할 수 있고, 다음과 같은 10가지 연산을 수행할 수 있다.

편의상 스택의 가장 위에 저장된 수를 첫 번째 수라고 하고, 그 다음은 차례대로 두 번째 수, 세 번째 수라고 한다.

• NUM X: X를 스택의 가장 위에 저장한다. (0 ≤ X ≤ 109)
• POP: 스택 가장 위의 숫자를 제거한다.
• INV: 첫 번째 수의 부호를 바꾼다. (42 -> -42)
• DUP: 첫 번째 숫자를 하나 더 스택의 가장 위에 저장한다.
• SWP: 첫 번째 숫자와 두 번째 숫자의 위치를 서로 바꾼다.
• ADD: 첫 번째 숫자와 두 번째 숫자를 더한다.
• SUB: 첫 번째 숫자와 두 번째 숫자를 뺀다. (두 번째 - 첫 번째)
• MUL: 첫 번째 숫자와 두 번째 숫자를 곱한다.
• DIV: 첫 번째 숫자로 두 번째 숫자를 나눈 몫을 저장한다. 두 번째 숫자가 피제수, 첫 번째 숫자가 제수이다.
• MOD: 첫 번째 숫자로 두 번째 숫자를 나눈 나머지를 저장한다. 두 번째 숫자가 피제수, 첫 번째 숫자가 제수이다.

이항 연산자의 경우에 첫 번째 숫자가 오른쪽에 있는 수이고, 두 번째 숫자가 왼쪽에 있는 수이다. 또, 연산을 수행하기 전에 두 숫자를 모두 스택에서 제거한 뒤, 결과를 다시 스택에 저장하는 것이다.

숫자가 부족해서 연산을 수행할 수 없을 때, 0으로 나눴을 때 (DIV, MOD), 연산 결과의 절댓값이 109를 넘어갈 때는 모두 프로그램 에러이다.

음수 나눗셈에 대한 모호함을 피하기 위해 다음과 같이 계산한다. 나눗셈의 피연산자에 음수가 있을 때는, 그 수를 절댓값을 씌운 뒤 계산한다. 그리고 나서 몫과 나머지의 부호는 다음과 같이 결정한다. 피연산자중 음수가 한 개일때는 몫의 부호가 음수이다. 이 경우를 제외하면 몫의 부호는 항상 양수이다. 나머지의 부호는 피제수의 부호와 같다. 따라서, 13 div -4 = -3, -13 mod 4 = -1, -13 mod -4 = -1이다.

프로그램 에러가 발생했을 경우에는, 현재 프로그램의 수행을 멈추고, 그 다음 어떤 명령도 수행하지 않는다.

입력

입력은 기계 여러 대의 설명으로 이루어져 있다. 각 기계의 설명은 프로그램과 입력영역으로 나누어져 있다.

프로그램은 명령어로 이루어져 있고, 명령어는 한 줄에 하나씩 있다. 각 명령은 문제 설명에 나와있는 대문자 알파벳 3글자이고, 다른 글자는 주어지지 않는다. NUM의 경우에는 명령어 다음에 숫자가 주어지며, 이 숫자는 0보다 크거나 같고, 109보다 작거나 같은 정수이다. NUM과 숫자는 공백으로 구분되어져 있다. 각 프로그램은 END가 나오면 끝난다.

입력영역은 첫째 줄에 프로그램 수행 횟수 N이 있다. (0 ≤ N ≤ 10,000) 다음 N개의 줄에는 한 줄에 하나씩 입력값 Vi가 있다. (0 ≤ Vi ≤ 109) 각 입력값에 대해서 프로그램을 한 번씩 수행해야 하고, 이 수행은 모두 독립적이다. 매번 프로그램을 수행할 때, 스택에 들어있는 값은 입력값 Vi 하나이다.

각각의 기계 설명은 빈 줄로 구분되어져 있다. QUIT이 나오면 다음 기계 설명이 없다는 뜻이다. 명령어가 100,000개를 넘어가는 경우와 스택이 수행될 때, 1,000개 이상의 숫자를 저장하는 경우는 없다.

출력

각각의 입력값에 대해서, 해당하는 프로그램을 수행한 뒤, 출력값을 출력하면 된다. 출력값이란 스택에 저장되어 있는 숫자이다.

만약, 프로그램 에러가 발생하거나, 모든 수행이 종료됐을 때 스택에 저장되어 있는 숫자가 1개가 아니라면, "ERROR"를 출력한다.

각 기계에 대한 출력값을 모두 출력한 뒤에는 빈 줄을 하나 출력해야 한다.

예제 입력 1 복사

​x
DUP
MUL
NUM 2
ADD
END
3
1
10
50
​
NUM 1
NUM 1
ADD
END
2
42
43
​
NUM 600000000
ADD
END
3
0
600000000
1
​
QUIT

 

풀이

구현인데 엄청 어렵게 풀었다.... 생각 해야 할 조건이 엄청 많다 ..

14%라는 정답률이 거품이 아니라는것을 보여줬던것 같다...

ArrayList 2개 Deque 1개를 이용해서 풀었다

 

ArrayList

2개를 받았는데

order와 order_num을 이용했다

order에는 SUB MUL 등과 같은 문자열 명령이 들어가고

order_num은 NUM 1 , NUM 2 이런 것을 처리하기 위해 만들었다.

 

Deque

이 문제는 스택인데 내가 문제 이해를 잘못해서 덱으로 풀었다.

(기존 스택에서 스택 인덱스의 first와 last를 빼는게 있는줄 알고 덱으로 접근했었다...)

근데 찾아보니 어차피 이 문제는 stack의 삽입,삭제가 많이 일어나서 LinkedList로 하는게 시간에서

더 빠르다고 한다.

이건 이 문제에서 stack으로 생각하면 될 거 같다.

 

연산중 공통적으로 생각 해줘야 할 것

입력을 다 받았으면 명령을 처리해줘야 하는데

POP, INV , DUP , SWP , ADD , SUB , MUL, DIV, MOD 등

수 많은 명령들이 있는데 일단 스택의 사이즈를 처리 해줘야 한다

POP, INV , DUP 의 경우는 스택의 사이즈가 적어도 1개는 있어야 한다

SWP ADD SUB MUL DIV MOD 는 2개의 수를 이용하니 스택의 사이즈가 적어도 2개는 있어야 한다.

 

int ?? long ??

맨처음엔 들어 올 수 있는 값이 10^9 이라서 int로만 해결 될 줄 알았었다

근데 104024 * 104024의 연산이 올 경우

int범위를 벗어나 오버플로우가 나게 된다.

그래서 이런 연산류는 다 long으로 처리 해줘야 한다

나도 한 실수가 있는데

int a= 104024;
int b= 104024;
long c = a*b;

이 코드는 얼핏 보기에 c는 long형이기 때문에 오버플로우가 안 날 것 같지만 실제로 해보면 오버 플로우가 난다.

 

그래서

long a = 104024;
long b = 104024;
long c=  a*b;

이런식으로 처리를 해줘야 했다. 이것때문에도 엄청 틀렸습니다를 받았다 ^^...

하지만 틀린걸 배웠으니 좋은 경험이지 !!

 

10^9의 범위

위의 int ?? long?? 주제와 연관된 문젠데 더하기,빼기,더하기,나누기를 한 값이 10^9 보다 크면 안되고

-10^9보단 작아선 안된다.

xxxxxxxxxx
if(sum>max_val || sum<max_val*-1) {
        break;
    }

이런식으로 잘 해줘야 한다.

 

나누기 예외

몫,나머지를 구하기 위한 나누기 연산에도 예외처리를 잘 해줘야 한다.

이것도 빠트려서 오랫동안 삽질 했다.

콘솔창에

0/15과 15/0 를 해보자

0/15의 경우 0이라는 값이 잘 나오는데

15/0의 경우 오류가 난다 0으로 나눌수 없기 때문이다.

Exception in thread "main" java.lang.ArithmeticException: / by zero at test.main() 이라는 에러를 볼 수 있을 것이다 ㅎㅎ..

 

 

전체코드

xxxxxxxxxx
import java.io.*;
import java.util.*;
public class Main {
    static int max_val;
    static boolean end;
    static int n;
    static boolean error_flag = false;
    static ArrayList<String>order_list= new ArrayList<>();
    static ArrayList<Integer>order_num = new ArrayList<>();
    static Deque<Integer>deque = new LinkedList<>();
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        max_val = (int)Math.pow(10, 9);
        while(true) {
            order_list.clear();
            order_num.clear();
            while(true) {
                String[] t = br.readLine().split(" ");
                if(t[0].equals("QUIT")) {
                    System.out.println(sb);
                    return;
                }   //EXIT명령이면 종료
                if(t[0].equals("END")) {
                    break;
                }
                if(t.length==1) {
                    order_list.add(t[0]);
                }
                else {
                    order_list.add(t[0]);
                    order_num.add(Integer.parseInt(t[1]));
                }
            }
            n = Integer.parseInt(br.readLine());
            for(int i=0; i<n; i++) {
                error_flag = false;
                deque.clear();
                int tmp = Integer.parseInt(br.readLine());
                deque.addFirst(tmp);
        
                solve();
                if(error_flag || deque.size()!=1) {
                    sb.append("ERROR\n");
                }
                else {
                    sb.append(deque.removeFirst()+"\n");
                }
            }
            sb.append("\n");
            String[] str = br.readLine().split("");
        }
    }
    public static void solve() {
        int order_num_cnt = 0;
        for(int i=0; i<order_list.size(); i++) {
            String order = order_list.get(i);
            if(order.equals("NUM")) {
                deque.addLast(order_num.get(order_num_cnt));
                order_num_cnt++;
            }
            if(order.equals("POP")) {
                if(deque.size()==0) {
                    error_flag=true;
                    break;
                }
                deque.removeLast();
            }
            if(order.equals("INV")) {
                if(deque.size()==0) {
                    error_flag=true;
                    break;
                }
                int tmp = deque.removeLast();
                tmp*=-1;
                deque.addLast(tmp);
            }
            if(order.equals("DUP")) {
                if(deque.size()==0) {
                    error_flag=true;
                    break;
                }
                int tmp = deque.getLast();
                deque.addLast(tmp);
            }
            if(order.equals("SWP")) {
                if(deque.size()<2) {
                    error_flag=true;
                    break;
                }
                int first = deque.removeLast();
                int second = deque.removeLast();
                
                deque.addLast(first);
                deque.addLast(second);
            }
            if(order.equals("ADD")) {
                if(deque.size()<2) {
                    error_flag=true;
                    break;
                }
                long first = deque.removeLast();
                long second = deque.removeLast();
                long sum = first+second;
                if(sum>max_val || sum<max_val*-1) {
                    error_flag=true;
                    break;
                }
                deque.addLast((int)sum);
            }
            if(order.equals("SUB")) {
                if(deque.size()<2) {
                    error_flag=true;
                    break;
                }
                long first = deque.removeLast();
                long second = deque.removeLast();
                long sub = second-first;
                if(sub>max_val ||sub<max_val*-1) {
                    error_flag= true;
                    break;
                }
                deque.addLast((int)sub);
            }
            if(order.equals("MUL")) {
                if(deque.size()<2) {
                    error_flag=true;
                    break;
                }
                long first = deque.removeLast();
                long second = deque.removeLast();
                long mul = second*first;
                if(mul>max_val || mul<max_val*-1) { //mul > max_cal도 고려
                    error_flag=true;
                    break;
                }
                deque.addLast((int)mul);
            }
            if(order.equals("DIV")) {
                if(deque.size()<2) {
                    error_flag=true;
                    break;
                }
                int minus_cnt=0;    // 음수 가리는 여부
                long first = deque.removeLast();
                long second = deque.removeLast();
                if(first<0) {
                    minus_cnt++;
                }
                if(second<0) {
                    minus_cnt++;
                }
                if(first==0) {
                    error_flag=true;
                    break;
                }
                long div = Math.abs(second)/Math.abs(first);
                
                if(minus_cnt==1) {
                    deque.addLast((int)div*-1);
                }
                else {
                    deque.addLast((int)div);
                }
            }
            if(order.equals("MOD")) {
                if(deque.size()<2) {
                    error_flag=true;
                    break;
                }
                long first = deque.removeLast();
                long second = deque.removeLast();
                if(first==0) {
                    error_flag=true;
                    break;
                }
                long mod = Math.abs(second) %Math.abs(first);
                if(second<0) {
                    mod*=-1;
                }
                deque.addLast((int)mod);
            }
        }
    }
}