백준 1874번 자바

문제

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

1874번: 스택 수열

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Main1874 {

	static int n;
	static int[] arr;
	static List<String> res;
	static Stack<Integer> stack;
	static int max = 1;
	static boolean isCheckSequence = true;

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		arr = new int[n];
		res = new ArrayList<String>();
		stack = new Stack<Integer>();
		
		for (int i=0; i<n; i++) {
			int sequence = sc.nextInt();
			if (sequence >= max) {
				for (int j=max; j<=sequence; j++) {
					stack.push(j);
					res.add("+");
					max++;
				}
				
				stack.pop();
				res.add("-");
				
			} else if (sequence < max) {
				if (stack.peek() != sequence) {
					isCheckSequence = false;
				} 
				
				stack.pop();
				res.add("-");
			}
		}
		
		if (!isCheckSequence) {
			System.out.println("NO");
			return;
		}
		
		for (int i=0; i<res.size(); i++) {
			System.out.println(res.get(i));
		}
	}
}

1. 스택 == DFS라는 고정관념 때문에 자꾸 dfs로 접근하려 해서 많이 헤맨 문제다. 결국 적당한 방법을 찾아 시도했지만 시간초과로 실패. 이유는 아래 코드와 함께 작성한다.

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class Main {

	static int n;
	static int[] arr;
	static List<String> res;
	static Stack<Integer> stack;
	static int max = 1;
	static boolean isCheckSequence = true;
	
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		arr = new int[n];
		res = new ArrayList<String>();
		stack = new Stack<Integer>();
		
		for (int i=0; i<n; i++) {
			int sequence = sc.nextInt();
			if (!stack.contains(sequence)) {  //contains 자체도 for문을 작동
				for (int j=max; j<=sequence; j++) {
					stack.push(j);
					res.add("+");
					max++;
				}
			} 
			
			if (stack.contains(sequence)) {
				int temp = 0;
				temp = stack.pop();
				res.add("-");
				
				if (temp != sequence) {
					isCheckSequence = false;
				}
			}
		}
		
		if (!isCheckSequence) {
			System.out.println("NO");
			return;
		}
		
		for (int i=0; i<res.size(); i++) {
			System.out.println(res.get(i));
		}
	}
}

2. 다른 부분들도 시간초과를 발생시키는데 많은 기여를 했겠지만 이 중에서 contains를 통해 sequence값을 찾는 과정이 아마 그 중 제일인듯하다.

Vector 클래스의 contains메소드는 indexOf 메소드를 반환하고 해당 메소드는 위와 같이 구성되어 있다. 사실 당연한 부분인데 문제를 푸는것에만 급급하여 전혀 생각을 못했다. 엉뚱하게도 ArrayList, LinkedList, Stack 중에 어떤 자료구조를 써서 "+" 또는 "-" 를 저장해야하나 고민했다. 

 

두번째로 크게 시간을 잡아먹은 부분은 "+" , "-" 저장할 객체의 타입이다.

맨위에 정답인 코드에서 ArrayList에 저장한 값들을 StringBuffer를 이용해 저장하기만 해도 시간이 반 이상 줄어든다.

import java.util.Scanner;
import java.util.Stack;

public class Main1874_1 {

	static int n;
	static int[] arr;
	static StringBuffer res;
	static Stack<Integer> stack;
	static int max = 1;
	static boolean isCheckSequence = true;

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		arr = new int[n];
		res = new StringBuffer();
		stack = new Stack<Integer>();
		
		for (int i=0; i<n; i++) {
			int sequence = sc.nextInt();
			if (sequence >= max) {
				for (int j=max; j<=sequence; j++) {
					stack.push(j);
					res.append("+\n");
					max++;
				}
				
				stack.pop();
				res.append("-\n");
				
			} else if (sequence < max) {
				if (stack.peek() != sequence) {
					isCheckSequence = false;
				} 
				
				stack.pop();
				res.append("-\n");
			}
		}
		
		if (!isCheckSequence) {
			System.out.println("NO");
			return;
		}
		
		System.out.println(res.toString());
	}
}

 

정리 : 여차저차 풀긴 풀었으나 좋은 방법으로는 풀었다고 못한다. 단순히 문제를 푸는 것보단 내가 이 자료구조를 선택하는 이유, 이 함수를 써야하는 이유 등에 대해 항상 고민하자.