백준 자바 1874번 스택수열

스택수열 문제... 많은 시간이 걸렸다! 근데 arraylist 하나면 해결됐던 문제... arraylist쓸 생각 안하고 자꾸 stack으로만 해결하려고 해서 시간이 오래 걸렸다.

 

package boj_basic.cp_1;

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

public class Q1874 {

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

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

        int a = 0;
        int c = 0;

        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            if(a<num) {
                for(int b=a+1 ; b <=num; b++) {
                    stack.push(b);
                    bw.write("+\n");
                    a=stack.peek();
                }
            }
            else {
                if(!stack.isEmpty()) {
                    if(c!=num) {
                        // "NO"를 출력하지 않고 바로 종료하지 않음
                        break;
                    }
                    else {
                        for(int d = c; d>=num; d--) {
                            stack.pop();
                            if(!stack.isEmpty())
                                c=stack.peek();
                            bw.write("-\n");
                        }
                        continue;
                    }
                }
            }
            if(!stack.isEmpty()) {
                stack.pop();
                if(!stack.isEmpty())
                    c=stack.peek();
                bw.write("-\n");
            }
        }

        // 입력이 끝나고 스택이 비어있지 않은 경우에 "NO"를 출력
        if(!stack.isEmpty()) {
            bw.write("NO\n");
        }

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

맨 처음에 작성했던 코드. 예제출력 1은 잘 되지만 수열이 불가능한 경우 즉 예제출력 2번의 경우는 별다른 +,- 출력 없이 그냥 "NO"만 나와야 하는데 자꾸 + - + - + + + - NO 이런식으로 출력됐다. arraylist쓸 생각을 못하고 계속 stack으로만 해결하려고 했기 때문...^^

 

그래서 arraylist를 사용해서 +,-를 따로 넣어주고, 마지막에 스택이 비어있지 않으면 NO만 출력해주는 식으로 코드를 수정했다.

package boj_basic.cp_1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Stack;

public class Q1874_1 {

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

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

        int a = 0;
        int c = 0;

        Stack<Integer> stack = new Stack<>();
        ArrayList<String> array = new ArrayList<>();

        for(int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            
            if(a<num) {
                for(int b=a+1 ; b <=num; b++) {
                    stack.push(b); //1234 집어넣음
                    array.add("+\n"); //arraylist에 1234 ++++
                    a=stack.peek();  // a=4
                }
            }
            else { //(a>=num) 3이 들어왔을 때 a인 4가 3보다 크니까
                if(!stack.isEmpty()) {
                    if(c!=num)  //만약 들어온 num값과 제일 위에 있는 값이 동일하지 않다면 수열을 만들 수가 없음.
                        break; //  for(int i = 0; i < n; i++) 반복문 빠져나옴
                    else {
                    	stack.pop();
                    	if(!stack.isEmpty())
                    		c=stack.peek(); //c=2
                    	array.add("-\n");
                    	continue; //continue해서 밑에 if문 실행하지 않고 바로 위에 for문으로 올라가서 continue!
                    }
                }
            }
            
            
            if(!stack.isEmpty()) { //for문 한 번 돌릴때마다 마지막에 pop을 한번씩! (사실은 위에 if문 만족할 때만 행해지는 if문임)
                stack.pop();
                if(!stack.isEmpty())
                    c=stack.peek(); // c=3
                array.add("-\n");
            }
        }

        // 입력이 끝나고 스택이 비어있지 않은 경우에 "NO"를 출력
        if(!stack.isEmpty()) {
            bw.write("NO\n");
        }
        else {
        	for(String st : array) {
        		bw.write(st);
        	}
        }

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

}

성공적..ㅎ 근데 if,else문도 너무 많고, 잘 안 읽히고, 처음봤을 때 이해하기 좀 어려운 코드를 짠 것 같았다.

 

package boj_basic.cp_1;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Stack;

public class Q1874_2 {

	public static void main(String[] args) throws NumberFormatException, IOException {
		 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	     BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	        
	        int n = Integer.parseInt(br.readLine());
	        
	        Stack<Integer>stack = new Stack<>();
	        
	        int[] arr = new int[n];
	        
	        ArrayList<String> array = new ArrayList<>();
	        
	        int index = 0;
	        
	        for(int i = 0; i<n; i++) {
	        	int num = Integer.parseInt(br.readLine());
	        	arr[i]=num;
	        }
	        
	        for(int i = 1; i<=n; i++) {
	        	stack.push(i);
	        	array.add("+\n");
	        	while(!stack.isEmpty()) {
	        		if(stack.peek()==arr[index]) {
	        			stack.pop();
	        			array.add("-\n");
	        			index++;
	        		}
	        		else 
	        			break;
	        	}
	        }
	        
	        if(!stack.isEmpty()) {
	        	bw.write("NO");
	        }
	        else {
	        	for(String st : array)
	        		bw.write(st);
	        }
	        
	        bw.flush();
	        bw.close();
	        br.close();

	}

}

다른 분들 코드를 좀 참고해서 좀 더 깨끗한 코드 완성!!

 

시간과 메모리 모두 줄어든 것을 볼 수 있다!