글 읽기 - 메모리 초과 질문입니다.

silvanas 4년 전 0

33% 이후에 메모리 초과가 납니다.

웹상의 다른 풀이를 보니 Stack을 LinkedList로 구현해서 풀었더군요.

저처럼 정적으로 Stack을 구현하면 반드시 메모리초과가 날수밖에없는건가요?

128MB 제한인데
(int)4byte * 100000 = 약 0.381471 MB로 충분히 여유롭다고 생각하는데 아닌가용..?

package Backjoon;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class X고스택 {
	
	static int MAX_VALUE = (int)1e9;
	
	public static void main(String[] args) throws IOException {
		solve();
	}
	
	static void solve() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		while(true) {
			LinkedList cmds = new LinkedList();
			while(true) {
				String line = br.readLine();
				if(line.equals("QUIT")) return;
				if(line.equals("END")) break;
				if(line.equals("")) continue;
				cmds.add(new Node(line));
			}
			
			int N = Integer.parseInt(br.readLine());
			for(int iter = 0 ; iter < N ; iter++) {
				int init = Integer.parseInt(br.readLine());
				Stack st = new Stack();
				st.num(init);
				
				// cmd실행하는것.
				Node cur = cmds.head;
				int isok = MAX_VALUE+1;
				while(cur!= null) {
					String[] cmd = cur.cmd.split(" ");
					isok = MAX_VALUE+1;
					switch(cmd[0]) {
					case "NUM":
						int n = Integer.parseInt(cmd[1]);
						isok = st.num(n);
						break;
					case "POP":
						isok = st.pop();
						break;
					case "INV":
						isok = st.inv();
						break;
					case "DUP":
						isok = st.dup();
						break;
					case "SWP":
						isok = st.swp();
						break;
					case "ADD":
						isok = st.add();
						break;
					case "SUB":
						isok = st.sub();
						break;
					case "MUL":
						isok = st.mul();
						break;
					case "DIV":
						isok = st.div();
						break;
					case "MOD":
						isok = st.mod();
						break;
					default:
						break;
					}
					if(isok == MAX_VALUE+1) break;
					cur = cur.next;
				}
//				System.out.println("isok : " + isok);
//				System.out.println("st.top : " + st.top);
				if(MAX_VALUE+1 == isok || st.top != 1)
					System.out.println("ERROR");
				else System.out.println(st.stack[0]);				
			}
			System.out.println();
			
		}
	}
	
	static class Stack{
		int top;
		int[] stack;
		
		public Stack() {
			stack = new int[100001];
			top = 0;
		}
		
		void init() {
			top = 0;
		}
		
		int num(int n) {
			if(top == 2000) return MAX_VALUE+1;
			stack[top++] = n;
			return 1;
		}
		
		int inv() {
			if(top == 0) return MAX_VALUE+1;
			stack[top-1] *= -1;
			return 1;
		}
		
		int dup() {
			if(top == 0) return MAX_VALUE+1;
			int n = stack[top-1];
			stack[top++] = n;
			return 1;
		}
		
		int swp() {
			if(top < 2) return MAX_VALUE+1;
			int tmp = stack[top-2];
			stack[top-2] = stack[top-1];
			stack[top-1] = tmp;
			return 1;
		}
		
		int add() {
			if(top < 2) return MAX_VALUE+1;
			int n = stack[top-1] + stack[top-2];
			if(n >= MAX_VALUE) return MAX_VALUE+1;
			top -= 2;
			stack[top++] = n;
			return 1;
		}
		
		int sub() {
			if(top < 2) return MAX_VALUE+1;
			int n = stack[top-2] - stack[top-1];
			if(n >= MAX_VALUE) return MAX_VALUE+1;
			if(n <= MAX_VALUE * -1) return MAX_VALUE+1;
			top -= 2;
			stack[top++] = n;
			return 1;
		}
		
		int mul() {
			if(top < 2) return MAX_VALUE+1;
			long a = stack[top-2];
			long b = stack[top-1];
			long c = a * b;
			if(c >= MAX_VALUE) return MAX_VALUE+1;
			if(c <= MAX_VALUE * -1) return MAX_VALUE+1;
			top -= 2;
			stack[top++] = (int)c;
			return 1;
		}
		
		int div() {
			if(top < 2) return MAX_VALUE+1;
			if(stack[top-1] == 0) return MAX_VALUE+1;
			int n = stack[top-2] / stack[top-1];
			top -= 2;
			stack[top++] = n;
			return 1;
		}
		
		int mod() {
			if(top < 2) return MAX_VALUE+1;
			if(stack[top-1] == 0) return MAX_VALUE+1;
			int n = stack[top-2] % stack[top-1];
			top -= 2;
			stack[top++] = n;
			return 1;
		}
		
		int pop() {
			if(top == 0) return MAX_VALUE+1;
			return stack[--top];
		}
	}
	
	static class LinkedList{
		Node head, tail;
		public LinkedList() {
			head = null;
			tail = null;
		}
		void add(Node n) {
			if(head == null) {
				head = n;
				tail = n;
				return;
			}
			
			tail.next = n;
			tail = tail.next;
		}
	}
	
	static class Node{
		String cmd;
		Node next;
		Node(String cmd){
			this.cmd = cmd;
		}
	}
}

pineleaf1215 4년 전 0

그러게요... 저도 그렇게 생각하는데 궁금하네요 ㅠ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

메모리 초과 질문입니다.

silvanas 4년 전 0

pineleaf1215 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말