[백준] 1874번 : 스택 수열

글 작성자: ST_

www.acmicpc.net/problem/1874

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

문제

스택의 원리만 이해한다면 쉽게 풀 수 있는 문제다.

알고리즘 [접근 방법]

아마 이 문제를 처음 접한다면 무슨 말인가 할 수도 있겠지만, 이해만 한다면 정말 쉬운 문제다.

스택 자료구조는 본문에서도 나와있듯이 LIFO(후입선출) 특성을 갖고있다. 스택에 대한 기본적인 이해는 다음 포스팅을 참고하시길 바란다.

자바 [JAVA] - Stack (스택) 구현하기

•자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly LinkedLi..

st-lab.tistory.com

그럼 문제를 살펴보도록 하자.

스택에 1 부터 n까지 수를 스택에 넣고(push) 빼는(pop) 과정을 통해 임의의 수열이 주어졌을 때 해당 수열을 만들 수 있는지를 판단하는 문제다.

이 때 스택에 수를 넣을 때(push)는 반드시 오름차순을 지켜야 한다.

무슨 말인가 이해하기 어렵다면 예제로 한 번 보면 이렇다.

이런 식의 과정을 거치게 된다.

그럼 어떻게 풀어야 할까?

예제에서의 처음 수열 입력값은 '4'다. (8은 입력의 개수이므로 제외)

그럼 1부터 4까지의 정수를 스택에 push한다.

int start = 0;


/* ------N번 반복----- */
int value = input();

if(value > start) {
	for(int i = start + 1; i <= value; i++) {
		stack.push(i);
	}
	start = value;
}

그리고 숫자를 push 할 때는 반드시 오름차순이어야 하기 때문에 이전에 어디까지 입력 받았는지를 알기 위한 변수 start를 value 값으로 초기화 해주어야 한다. (4까지 push했기 때문에 다음에 push 할 경우 5 부터 push하기 위함이다.)

그런 다음 스택의 맨 위 원소가 입력받은 4와 같다면 pop을 해주고, 만약 같지 않다면 주어진 수열을 만족하지 못하는 것이므로 "NO" 가 된다.

int start = 0;


/* ------N번 반복----- */
int value = input();

if(value > start) {
	for(int i = start + 1; i <= value; i++) {
		stack.push(i);
	}
	start = value;
}

// top에 있는 원소가 입력받은 값과 같이 않은 경우  
else if(stack.peek() != value) {
	print("NO");
	return;	// 더이상 탐색 할 필요가 없으므로 프로그램을 종료시켜 버린다.
}

// value 값까지 push가 되어있다면 pop을 해준다.
stack.pop();

위 구조를 조금 가다듬어서 전체적으로 반복을 하면 된다.

전체적으로 보면 입력받은 value 값 까지 push 한 이력이 없을경우 stack에 value까지 push 한 후 마지막 원소를 pop해주면 되는 문제다. 참고로 결과적으로 출력해야 할 것은 + 또는 - 이므로 StringBuilder 을 사용하여 push할 땐 '+'를, pop할 때는 '-' 를 저장해준 뒤 만약 반복문이 정상적으로 끝날 경우 저장해둔 문자열을 한 번에 출력해주고, 그 외의 경우 이미 "NO"가 출력되어 프로그램이 종료된 상태이므로 출력될 일이 없다.

자세한 건 아래 풀이에서 알 수 있을 것이다.

4가지 방법을 사용하여 풀이한다.

이전 포스팅과 여타 다를 바 없이 스택 라이브러리를 사용하는 방법과 배열을 선언하여 스택처럼 사용하는 방법을 보여주고자 한다.

그리고 각각의 방법에 입력 방법을 달리하여 성능을 비교해보려 한다.

1 . Scanner + Stack

2. BufferedReader + Stack

1 . Scanner + array

2. BufferedReader + array

풀이

- 방법 1 : [Scanner + Stack]

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

public class Main {
	public static void main(String[] args) {
		
		Scanner in = new Scanner(System.in);
		StringBuilder sb = new StringBuilder();	// 출력할 결과물 저장
		
		Stack<Integer> stack = new Stack<>();
		
		int N = in.nextInt();
		
		int start = 0;
		
		// N 번 반복
		while(N -- > 0) {
			
			int value = in.nextInt();
			
			if(value > start) {
				// start + 1부터 입력받은 value 까지 push를 한다.
				for(int i = start + 1; i <= value; i++) {
					stack.push(i);
					sb.append('+').append('\n');	// + 를 저장한다. 
				}
				start = value; 	// 다음 push 할 때의 오름차순을 유지하기 위한 변수 초기화 
			}
			
			// top에 있는 원소가 입력받은 값과 같이 않은 경우  
			else if(stack.peek() != value) {
				System.out.println("NO");
				return;		// 또는 System.exit(0); 으로 대체해도 됨. 
			}
			
			stack.pop();
			sb.append('-').append('\n');
			
		}
		
		System.out.println(sb);
	}
}

보면 필자가 위 알고리즘 설명과 크게 다를 것이 없다. 추가 된 것이 있다면 StringBuilder을 이용하여 문자열을 연결해주는 작업만 추가되었을 뿐이다.

- 방법 2 : [BufferedReader + StringBuilder]

입력 방법을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다.

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

public class Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();	// 출력할 결과물 저장
		
		Stack<Integer> stack = new Stack<>();
		
		int N = Integer.parseInt(br.readLine());
		
		int start = 0;
		
		// N 번 반복
		while(N -- > 0) {
			
			int value = Integer.parseInt(br.readLine());
			
			if(value > start) {
				// start + 1부터 입력받은 value 까지 push를 한다.
				for(int i = start + 1; i <= value; i++) {
					stack.push(i);
					sb.append('+').append('\n');	// + 를 저장한다. 
				}
				start = value; 	// 다음 push 할 때의 오름차순을 유지하기 위한 변수 초기화 
			}
			
			// top에 있는 원소가 입력받은 값과 같이 않은 경우  
			else if(stack.peek() != value) {
				System.out.println("NO");
				return;		// 또는 System.exit(0); 으로 대체해도 됨. 
			}
			
			stack.pop();
			sb.append('-').append('\n');
			
		}
		
		System.out.println(sb);
	}
}

크게 어려울 것은 없을 것이다. 이번 문제는 중복을 고려하지 않아도 되니 오히려 쉬웠을 수도 있다.

- 방법 3 : [Scanner + array]

Stack 클래스 대신 stack 자료구조를 배열로 직접 구현하여 풀이하는 방법이다.

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		StringBuilder sb = new StringBuilder();	// 출력할 결과물 저장 
        
		int N = in.nextInt();
		
		int[] stack = new int[N];
		
		int idx = 0;
		int start = 0;
		
		// N 번 반복
		while(N -- > 0) {
			int value = in.nextInt();
			
			if(value > start) {
				// start + 1부터 입력받은 value 까지 push를 한다.
				for(int i = start + 1; i <= value; i++) {
					stack[idx] = i;
					idx++;
					sb.append('+').append('\n');
				}
				start = value; 	// 다음 push 할 때의 오름차순을 유지하기 위한 변수 초기화 
			}
			
			// top에 있는 원소가 입력받은 값과 같이 않은 경우  
			else if(stack[idx - 1] != value) {
					System.out.println("NO");
					System.exit(0);	//	return 으로 대체해도 됨 
			}
			
			idx--;
			sb.append('-').append('\n');
		}
		System.out.println(sb);
	}

}

배열로 구성하는 방법이다. 배열로 작성하더라도 스택 자료구조의 기본 개념과 같기 때문에 그대로 구현 원리만 따라주면 된다.

- 방법 4 : [BufferedReader + array]

방법 3에서 입력 방법만 바꾼 방법이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		
		int[] stack = new int[N];
		
		int idx = 0;
		int start = 0;
		
		// N 번 반복
		while(N -- > 0) {
			int value = Integer.parseInt(br.readLine());
			
			if(value > start) {
				// start + 1부터 입력받은 value 까지 push를 한다.
				for(int i = start + 1; i <= value; i++) {
					stack[idx] = i;
					idx++;
					sb.append('+').append('\n');
				}
				start = value; 	// 다음 push 할 때의 오름차순을 유지하기 위한 변수 초기화 
			}
			
			// top에 있는 원소가 입력받은 값과 같이 않은 경우  
			else if(stack[idx - 1] != value) {
					System.out.println("NO");
					System.exit(0);	//	return 으로 대체해도 됨 
			}
			
			idx--;
			sb.append('-').append('\n');
		}
		System.out.println(sb);
	}

}

성능

채점 번호 : 24193328 - 방법 4 : BufferedReader + array

채점 번호 : 24193320 - 방법 3 : Scanner + array

채점 번호 : 24193313 - 방법 2 : BufferedReader + Stack

채점 번호 : 24192998 - 방법 1 : Scanner + Stack

정리

이 번 문제 또한 어려운 점은 없었을 것이다. 만약 어려웠던 점이 있다면 이러한 문제를 처음 접하는 분들은 어떤 말인지 지문을 이해하는 것이 아니었을까 생각이 든다.

여튼 이 문제로 스택 자료구조 카테고리의 문제는 끝났다.

하지만 안타깝게도 다음 문제 또한 자료구조와 관련 된 카테고리다. 큐(Queue)와 덱(Deque)인데 쉽게 생각하자면, 큐는 단방향 대기열이고, 덱은 양방향 대기열이라고 보면 된다.

큐 자료구조는 여러모로 쓰일 일이 많기 때문에 문제를 풀기 전에 어떤 원리로 짜여져 있는지부터 이해하는 것이 중요하다.

필자도 Queue 자료구조를 먼저 구현 한 뒤 백준 큐, 덱 카테고리를 진행하고자 한다.

만약 어렵거나 이해가 안되는 부분이 있다면 언제든 댓글 남겨주시면 된다.

저작자표시 비영리 변경금지

'JAVA - 백준 [BAEK JOON] > 스택' 카테고리의 다른 글

[백준] 4949번 : 균형잡힌 세상 - JAVA [자바] (10)	2020.12.01
[백준] 9012번 : 괄호 - JAVA [자바] (18)	2020.11.30
[백준] 10773번 : 제로 - JAVA [자바] (5)	2020.11.27
[백준] 10828번 : 스택 - JAVA [자바] (32)	2020.11.20

[백준] 1874번 : 스택 수열 - JAVA [자바]

'JAVA - 백준 [BAEK JOON] > 스택' 카테고리의 다른 글

댓글

이 글 공유하기

티스토리툴바

'JAVA - 백준 [BAEK JOON] > 스택' 카테고리의 다른 글

댓글

이 글 공유하기

다른 글

[백준] 4949번 : 균형잡힌 세상 - JAVA [자바]

[백준] 9012번 : 괄호 - JAVA [자바]

[백준] 10773번 : 제로 - JAVA [자바]

[백준] 10828번 : 스택 - JAVA [자바]

티스토리툴바