39 삐약 : 백준 1874|스택 수열[바킹독 문제 풀이|스택|JAVA]

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

1874번: 스택 수열

 

 

1트 : 메모리 초과

package BKD_0x5_Stack;

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class BOJ_1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

        int[] inputlist = new int[N+1];
        Stack<Integer> handlestack = new Stack<>();
        int current_target_index=1;

        String result="";
        for (int i=1;i<=N;i++) inputlist[i]=Integer.parseInt(br.readLine());

        for(int i=1;i<=N;i++){
            handlestack.push(i);
            result += "+\n";
            while (!handlestack.isEmpty() && handlestack.peek()==inputlist[current_target_index]){
                handlestack.pop();
                result += "-\n";
                current_target_index++;
            }
        }

        if(handlestack.isEmpty()) bw.write(result);
        else bw.write("NO");

        bw.flush();
        bw.close();
        br.close();


    }
}

 

---

문제점

String1 += String2 연산 수행

- String은 불변한 객체이므로 각 문자열 연산마다 새로운 문자열을 생성하고 기존 문자열을 가비지 컬렉션의 대상이 된다. 
- 즉 연산이 많을 수록 메모리 사용량이 늘어나기에 메모리 소비를 증가시키고 성능을 저하시킬 수 있다. 
- 반복적인 문자열 조작이 많은 경우 해당 객체를 사용하는것을 추천하지 않는다. 

+)
- 문자열 사이의 연산을 진행 할 때 마다 String1 +String 2의 값을 가지는 새로운 문자열이 생성되고,
  기존의 값을 저장하였던 String1 변수는 새로운 값이 저장된 문자열을 참조하게 된다.
- 즉, 기존의 변경 이전의 String 1값을 가지는 문자열은 garbage collection의 대상이 된다. 

 

 

해결

StringBuilder사용

StringBuilder는 가변한 문자열을 나타내며 문자열을 효율적으로 누적할 수 있다. 
문자열 수정 시에 기존 데이터를 복사하지 않고 직접 수정하기에 메모리 사용량이 효율적이며, 연산 수행에 따른 메모리 증가가 거의 없다.

 

위와같은 이유로 반복적인 문자열 조작 작업을 진행하는 문제의 경우 StringBuilder가 권장됨을 확인할 수 있었다. 

 

 

---

 

2트 : StringBuilder

 

package BKD_0x5_Stack;

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class BOJ_1874 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder result = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        int[] inputlist = new int[N+1];
        Stack<Integer> handlestack = new Stack<>();
        int current_target_index=1;

        for (int i=1;i<=N;i++) inputlist[i]=Integer.parseInt(br.readLine());

        for(int i=1;i<=N;i++){
            handlestack.push(i);
            result.append("+\n");
            while (!handlestack.isEmpty() && handlestack.peek()==inputlist[current_target_index]){
                handlestack.pop();
                result.append("-\n");
                current_target_index++;
            }
        }

        if(handlestack.isEmpty()) bw.write(result.toString());
        else bw.write("NO");

        bw.flush();
        bw.close();
        br.close();


    }
}