[Java,백준] 알고리즘 문제 메모리 초과되는 이유를 모르겠습니다.

Question

문제는 1874번 스택 수열이라는 문제입니다.https://www.acmicpc.net/problem/1874아래 소스 코드로 제출했는데 메모리 초과 즉, 128MB를 넘어갔다는 이야기인데..스택 수열 해당 문제 메모리 제한 128MB 이고 입력 n은 최대값이 100000 이고 두 int 배열 N 크기만큼 메모리 잡으면 100000*4*2 byte &#61; 800000 byte또한 String output 최대 길이는 최대로 push, pop을 하는 100000*2*2 byte &#61; 400000 byte총 합쳐도 최대 1200000 byte 기껏해야 2MB도 안넘어가는데 도대체 무슨 문제가 있어서 메모리 초과가 날까요?추측해보자면 while 문이 무한 루프 돌아서 string 길이가 무제한 늘어나서 메모리 초과되는 경우인데..arr[size] !&#61; nArray[getIndex] 이 아닐경우 getIndex가 증가하여 결국에는 nArray.length가 같아져서 while문이 빠져나올텐데 잘 모르겠습니다. 10만 데이터 1~100000 차례로 넣어보고 역순으로 넣어봐도 출력까지 잘 이어집니다. 무엇이 문제일까요?import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static void main(String[] args) throws IOException { BufferedReader br &#61; new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw &#61; new BufferedWriter(new OutputStreamWriter(System.out)); int n &#61; Integer.parseInt(br.readLine()); int nIndex &#61; 1; int[] arr &#61; new int[n&#43;1]; int size &#61; 0; int[] nArray &#61; new int[n]; int getIndex &#61; 0; String output &#61; &#34;&#34;; for (int i &#61; 0; i < nArray.length; i&#43;&#43;) { nArray[i] &#61; Integer.parseInt(br.readLine()); } size&#43;&#43;; arr[size] &#61; nIndex; output &#43;&#61; &#34;&#43;&#34;; while(getIndex<nArray.length) { if(arr[size] !&#61; nArray[getIndex]) { if(size &#61;&#61; n) { output &#61; &#34;NO&#34;; break; } output &#43;&#61; &#34;&#43;&#34;; size&#43;&#43;; nIndex&#43;&#43;; arr[size] &#61; nIndex; } else { output &#43;&#61; &#34;-&#34;; size--; getIndex&#43;&#43;; } } if(output.equals(&#34;NO&#34;)) { bw.write(&#34;NO
&#34;); } else { for (int i &#61; 0; i < output.length(); i&#43;&#43;) { bw.write(String.valueOf(output.charAt(i))&#43;&#34;
&#34;); } } bw.flush(); } }

즐기는 개발자 · Accepted Answer

문제점 알 것 같아요 StringBuilder 사용해서 함 해볼게요

[Java,백준] 알고리즘 문제 메모리 초과되는 이유를 모르겠습니다.

1개의 답변

Q&A 목록