[백준] 단계별로 풀어보기(단계:18,스택,JAVA)1874번, 스택 수열

문제 링크

1874번: 스택 수열

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

기본적으로 스택이란 LIFO(후입 선출)의 자료구조입니다.

LIFO는 먼저 들어간 데이터들이 출력할 때 나중에 나온다는 이야기입니다.

예를 들어 3, 2, 1을 순서대로 스택에 저장한 뒤 하나씩 꺼내보겠습니다.

1. 스택에 3을 넣었을 때

3

2. 스택에 2을 넣었을 때

2

3

3. 스택에 1을 넣었을 때

1

2

3

4. 스택에 하나의 자료를 출력하라는 명령이 떨어졌을 때

1

2

3

5. 다시 자료를 출력하라는 명령이 떨어졌을 때

2

3

위에 표를 보면 간단히 돌탑을 생각하시고 돌을 뺄 때 나중에 올린 돌부터 빼는 것처럼 스택은 LIFO의 형태를 가진 자료구조입니다.

 

이 문제에서는 스택에는 오름차순 번호가 저장되는 것을 이용하여 입력된 수열이 되는지 확인하는 문제입니다.

그래서 두 가지의 경우로 나누었습니다. (다음 스택에 저장하는 값 = cur)

1. 스택이 비어있을 때

스택에 값이 존재하지 않는다면 현재 수열에 해당하는 값만큼 push를 한 뒤 그 값을 pop해야 합니다.

하지만 cur이 수열에 해당하는 값보다 크다면 cur을 오름차순으로 push를 해도 그에 해당하는 수열의 값을 얻을 수 없으므로 Fail() 함수를 실행하고 반복을 중단하도록 하였습니다.

2. 스택에 값이 존재할 때

스택에 값이 존재하면 스택에 가장 최근에 저장된 값을 받아옵니다.

수열에 해당하는 값이 최근값보다 작을 경우에는 cur을 오름차순으로 저장해도 그에 해당하는 값을 얻을 수 없으므로 Fail() 함수를 실행하고 반복을 중단하도록 하였습니다.

수열에 해당하는 값이 최근값과 같으면 최근값이 그에 해당하는 수이므로 pop만 진행하였습니다.

수열에 해당하는 값이 최근값보다 크면 cur을 오름차순으로 push하여 해당하는 수가 되면 pop이 되도록 하였습니다.

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 스택에 push/pop을 하는 함수 push()/pop()을 만들었습니다.
• 입력된 수열에 값을 표현할 수 없으면 값을 설정하는 Fail()함수를 만들었습니다.
• StringBuilder에 저장된 결과값을 System.out.println을 사용하여 출력하였습니다.

• push()는 수열에 해당하는 숫자만큼 push를 진행하고 '+'을 StringBuilder에 저장하도록 하였습니다.
• pop()은 스택에 pop을 수행하고 '-'을 StringBuilder에 저장하도록 하였습니다.
• Fail()은 StringBuilder를 초기화하고 불가능하다는 "NO"을 저장하도록 하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static Stack<Integer> stack = new Stack<Integer>();	//수열 관련 스택
	static StringBuilder sb = new StringBuilder();	//결과값
	static int index,cur=0;
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //---------입력 값 저장 및 함수 실행-------
    	index = Integer.parseInt(br.readLine());
    	for(int i=0;i<index;i++) {
    		int num = Integer.parseInt(br.readLine());
    		if(stack.empty()) {	//스택이 비어있을 때
    			if(cur > num) {
    				Fail();
    				break;
    			}
    			else {
    				push(cur,num);
    				pop();
    				continue;
    			}
    		}
    		int top = stack.peek();
    		if(top > num) {		//스택이 비어있지 않을 때
    			Fail();
    			break;
    		}else if(top == num) {
    			pop();
    		}else{
    			push(cur,num);
    			pop();
    		}
    	}
    	System.out.println(sb.toString());	//결과 출력
    	br.close();
	}
    //---------스택 push 함수---------
	public static void push(int n, int num) {
		for(int i=n+1;i<=index;i++) {
			if(i>num) {
				cur = i-1;
				break;
			}
			stack.push(i);
			sb.append("+\n");
		}
	}
    //-------스택 pop 함수------------
	public static void pop() {
		stack.pop();
		sb.append("-\n");
	}
    //----------수열 조성 불가능 확인 함수--------
	public static void Fail() {
		sb = new StringBuilder("NO");
	}
}