[java] 백준 알고리즘 1874번 스택 수열 풀이

사용하는 객체가 많아 메모리, 시간 둘 다 많이 잡아먹는다. ㅠㅠ

내가 짰지만 소스가 그다지 마음에 들지는 않지만, 일단 문제 해결.

* 풀이 소스

 
public class Baekjooon1874{
 
    static StringTokenizer st;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        st = new StringTokenizer(br.readLine());
        int rangeNum = Integer.parseInt(st.nextToken()); // 몇개의 수열이냐
        int[] matchingArray = new int[rangeNum+1]; // 입력된 수열(만들고 싶은 or 원하는 수열)
        int[] reOrderArray = new int[rangeNum+1]; // push와 pop의 반복으로 만들어진(재정렬된) 배열
        
        Stack<Integer> stackImpl = new Stack<>(); // 구현된 스택
        List<String> pushPopList = new ArrayList<>(); // +,-로 나타낼 리스트
        
        for(int i=1; i<matchingArray.length; i++) {
            st = new StringTokenizer(br.readLine());
            matchingArray[i] = Integer.parseInt(st.nextToken());
        }
        
        int order = 1; 
        for(int j=1; j<=rangeNum; j++) { // 문제의 n까지 수열 반복
            
            stackImpl.push(j);
            pushPopList.add("+"); // push가 이루어지면 + 입력
            if(matchingArray[order] == j) { // 만들고싶은 수가 나오는 순간 pop
                int popNum = j;
                
                while(matchingArray[order] == popNum) { // 한 번 pop되고 바로 다음 원하는 값이 있을 경우 계속 반복
                    
                    reOrderArray[order] = stackImpl.pop();
                    
                    order++; // 단순히 재정렬하는 배열을 만들기 위해 index 객체
                    pushPopList.add("-");
                    if(stackImpl.size()>0) {
                        popNum = stackImpl.get(stackImpl.size()-1);
                    }else {
                        break;
                    }
                    
                    if(order == matchingArray.length) { // 만들고자 하는 배열의 길이를 넘는 순간 더 이상 비교할 필요 없으므로 break
                        break;
                    }
                }
            }
        }
        
        while(!stackImpl.isEmpty()) { // 스택에 값이 남아있다면 나머지는 다 pop(-)을 해줘야하니까 계산
            reOrderArray[order] = stackImpl.pop();
            order++;
            pushPopList.add("-");
        }
        
        if(Arrays.equals(matchingArray, reOrderArray)) { // 새로 만든 배열과 만들고자하는 배열이 일치하면 프린트
            for(String output : pushPopList) {
                bw.write(output);
                bw.newLine();
                bw.flush();
            }
        }else { // 일치하지 않는다면 불가
            bw.write("NO");
            bw.flush();
        }
    }
 
}