백준 1874번 <스택 수열>

백준 알고리즘 1874번

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

1874번: 스택 수열

모각코 때부터 도전했는데 실패한 문제!

 

오늘은 꼭 풀겠다는 마음으로 풀었다.

 

거의 다 풀어놨는데 시간 초과랑 런타임 에러가 떠서 고생했다.

---

1874번

입력 첫 줄에 수열의 수(n))가 주어지고 둘째 줄부터 n개의 줄에 걸쳐 수열을 이루는 1 이상 n이하의 정수가 하나씩 순서대로 주어진다.

 

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push -> +  pop -> -

---

문제 해결

사용할 스택 stack을 Integer 형으로 만들어준다.

 

만들 수 없는 수열과 만들 수 있는 수열을 구분하기 위해 boolean형의 fact를 true로 초기화한다.

(만들 수 없는 조건을 만족했을 때 fact를 false로 바꾸는 것으로 한다.)

 

입력받은 수열을 input이라는 배열에 저장한다.

똑같은 수열을 sort에 저장하고 Arrays.sort()를 사용하여 정렬한다.

 

이 두 개의 수열을 이용하기 위해 이중 for문을 돌릴 것이다.

for(int i = 0; i < n; i++){
	for(int j = index; j < n; j++){
    
    }
}

이런 식으로!

 

안쪽 for문 안에서 if문으로 경우를 나눌 것이다.

1. input[i] == sort[j] 인 경우

stack에 넣었다고 뽑는다. 

(어차피 넣었다고 뽑을 것이기 때문에 굳이 stack에 넣지는 않고 결과를 저장하는 sb에 +\n-\n을 append해주었다.)

이제 input[]에서 i번째 것 말고 i+1번째 것을 비교해야 하기 때문에 break로 안쪽 for문을 빠져나간다.

 

*index는 sort[] 볼 지점을 알려준다. (굳이 0번째부터 다시 볼 필요는 없으니까!)

 

2. input[i] > sort[j] 인 경우

sort[j]의 값을 stack에 넣는다. sb에 +\n을 append해준다.

 

3. input[i] < sort[j] 인 경우

stack의 크기 0이면 fact를 false로 하고 break. (이미 만들 수 없는 수열이므로 더 이상 볼 필요가 없다.)

stack의 꼭대기에 있는 것을 int형으로 바꿔서 input[i]와 비교했을 때 같으면 sb에 -\n을 append해준다.

그리고 break. (입력받은 수열에 있는 숫자를 이미 찾았으므로 j++을 할 필요가 없다.)

만약 서로 다르면 fact를 false로 하고 break. (이미 만들 수 없는 수열이므로 더 이상 볼 필요가 없다.)

 

-----------------------------------------------------------------------------------------------

 

안쪽 for문을 빠져나오고 바깥쪽 for문에서

fact가 만약 false라면 break를 해주어서 안쪽 for문도 빠져나오도록 한다.

index가 n과 같다면 == sort 배열의 끝까지 이미 확인했다는 것

이제는 index에 i+1을 저장해 두고 바깥쪽  for문을 빠져나오도록 한다.

 

-----------------------------------------------------------------------------------------------

 

두 개의 for문을 모두 빠져나오고 나서

fact가 true면

for문을 돌려서  stack에 남아있는 숫자들을 순서대로 pop 하는데 그 숫자들이 input[i]와 같아야 한다. 

같으면 sb에 -\n을 append해준다.

같지 않으면 fact를 false로 바꿔주고 break로 for문을 빠져나온다.

 

fact가 true면 

sb.toString()을 출력해주고

그렇지 않으면 

NO를 출력해준다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;

public class Main2 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();

		int num = Integer.parseInt(br.readLine());
		int[] input = new int[num];
		int[] sort = new int[num];

		for (int i = 0; i < num; i++) {
			input[i] = Integer.parseInt(br.readLine());
			sort[i] = input[i];
		}

		Arrays.sort(sort);

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

		int index = 0;
		boolean fact = true;

		for (int i = 0; i < num; i++) {
			for (int j = index; j < num; j++) {
				if (input[i] == sort[j]) {
					sb.append("+\n");
					sb.append("-\n");
					index = j + 1;
					break;
				} else if (input[i] > sort[j]) {
					stack.add(sort[j]);
					sb.append("+\n");
				} else { // input[i] < sort[j]
					if (stack.size() != 0) {
						int stackN = stack.pop().intValue();
						if (stackN == input[i]) {
							sb.append("-\n");
							break;
						} else {
							fact = false;
							break;
						}
					} else {
						fact = false;
						break;
					}
				}
			}
			if (!fact) {
				break;
			}
			if (index == num) {
				index = i + 1;
				break;
			}
		}

		if (fact) {
			int size = stack.size();
			for (int i = index; i < index + size; i++) {
				int x = stack.pop().intValue();
				if (x == input[i]) {
					sb.append("-\n");
				} else {
					fact = false;
					break;
				}
			}
		}
		if (fact) {
			System.out.println(sb.toString());
		} else {
			System.out.println("NO");
		}

	}

}

---

결과

 

---

처음에 시간 초과가 떠서 Scanner를 BufferedReader로 바꿔주고 출력도 배열을 for문으로 출력하는 것이 아니라 StringBUffer로 출력해주었다.

이렇게 고치고 나니 시간초과 말고 런타임 에러가 뜨길래

stack에서 pop() 한 것과 input[]값을 비교할 때 Integer와 int형을 비교하는 것이니까

stack에서 pop()한 것을 intValue()로 int형으로 바꿔주었다.

그리고 stack에서 pop()할 때 stack의 크기가 0일 수도 있으니까 그것을 if문으로 고쳐주었다.

 

다행히 그러니까 맞았습니다!!! 떠서 너무 행복했다 ㅎㅎ