[백준 1874번] 스택 수열 (메모리 초과 +StringBuilder) - java/자바

---

문제 이해

• 1부터 n까지 오름차순으로 스택에 push할수 있다.
• 입력된 숫자가 스택에 있는 숫자 보다 클 경우 push를 해준다.
• 스택을 pop했을때 입력된 숫자와 pop된 숫자가 동일해야 한다.
  • 동일하지 않거나 스택이 비어있는 경우, 실패이다.

 

풀이

import java.io.*;
import java.util.Stack;

public class Solution {
    void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        StringBuilder answer = new StringBuilder();
        int max=1;
        for(int i=0; i<num; i++){
            int n = Integer.parseInt(br.readLine());
            if(n>=max){
                while(max<=n) {
                    stack.push(max++);
                    answer.append("+\n");
                }
            }
            if(stack.empty() || stack.pop()!=n){
                System.out.println("NO");
                return;
            }else{
                answer.append("-\n");
            }
        }
        System.out.println(answer);
        br.close();
    }
}

 

메모리 초과 (+StringBuilder)

처음엔 답에 해당하는 String을 BufferWriter로 출력하게끔 해서 코드를 제출했더니 메모리 초과가 떴다.

그 이유는 Java에서 String 클래스는 immutable, 즉 상수다. 한번 생성한 이후에는 값이 변하지 않는다!

??그럼 이때까지 우리가 문자열을 변경하거나 concat같은 연산을 해줬을때는? 

→ 값이 변경된게 아니라 새로운 문자열을 heap에 생성한 다음 새로 참조했던것. (전에 참조했었던건 아마 garbage행..)

 

그렇기 때문에 문자열 변경이 많은 경우, String을 계속해 생성해 나가면서 메모리 초과가 뜨는게 아닐까 싶다.

이건 StringBuilder와 StringBuffer로 해결할수 있다.

 

String vs StringBuilder vs StringBuffer

String을 immutable한 반면 StringBuilder와 StringBuffer은 mutable한 문자 배열이다.

생성될때 default한 capacity(16)가 있고 이 크기를 넘어가면 자동으로 더 큰 문자열을 생성해준다!

StringBuilder와 StringBuffer의 차이는 synchronization 지원 여부이다.

StringBuilder에서는 synchronization을 지원하지 않아 멀티스레드에서 사용은 위험하지만, 알고리즘 문제는 모두 단일 스레드 환경이기 때문에 더 빠른 StringBuilder을 이용하면 된다.

 

결론! 문자열의 변경, 연산이 잦다면 String 대신 StringBuilder을 사용하자!

 

더 자세한 정보나 메소드를 알고 싶다면 아래 오라클 자바 문서를 확인하면 된다!

참고 : https://docs.oracle.com/javase/8/docs/api/java/lang/StringBuilder.html

StringBuilder (Java Platform SE 8 )

 

문제 : https://www.acmicpc.net/problem/1874

 

(개인 공부를 정리하기 위해 개설한 블로그입니다. 따라서 잘못된 정보가 있을 수 있고 댓글로 알려주신다면 정말 감사하겠습니다. )