(C++) [백준 1874번] 스택 수열

www.acmicpc.net/problem/1874

1874번: 스택 수열

 

N과 1부터 N으로 이루어진 어떤 수열이 주어지면, 스택에 1부터 N까지 push와 pop을 이용해 그 수열을 구할 수 있는지

찾는 문제이다. 단 이때 반드시 1부터 오름차순으로만 push 할 수 있다.

 

구할 수 있으면 push를 할 때 '+', pop을 할 때 '-'를 각각 출력하면 되고, 구하지 못하면 "NO"를 출력하면 된다.

 

예제 1

예제 1에 대한 힌트

보통은 힌트가 잘 없는데 문제 이해하기가 어려워서 그런지 힌트를 제공해준다.

말 그대로 1부터 n까지의 수를 차례대로 늘어놓고 스택의 연산을 이용한다고 생각했을 때 위와 같은 과정을 거쳐서

원래 수열을 얻을 수 있다. 

 

예제 2

"NO"가 되는 경우의 예제이다.

1,2,5,3,4는 오름차순으로 push하는 스택에서 절대 결과를 얻을 수 없으므로 NO이다.

 

[문제 풀이 과정]

스택을 이용하는 문제이므로 STL의 스택을 썼다.

 

처음에는 어떤 특정한 조건에서 NO가 될것이라고 생각해서 조건을 열심히 찾아봤다.

찾다 보니 조건이 있긴 했는데, 임의의 연속된 숫자 3개에서 max(n),min(m)순으로 나오는 수열이 있다면 ex) 3,1,2 / 6,4,5이 수열은 나오지 않더라.

당연하게도 1,2,3 순서대로 PUSH하는데 1,2,3이 PUSH된 상태에서는 어떻게 하더라도 2를 놔두고 1을 꺼낼 수는 없기 때문이다.

이 조건을 써서 NO를 출력하려고 했는데 이렇게 풀라고 낸 문제는 아닌 것 같아서 계속 고민하다보니까, 한번에 모아서

출력하면 되겠다는 생각이 들었다.

되든 안되든 일단 돌려보고 나중에 원본과 다르면 NO를 출력하면 된다.

아래는 핵심 소스코드 설명 보기

while(s.size() < (n+1))
	{
		if (result[n - 1] != 0) break;
		if (s.empty())
		{
			s.push(cnt++);
			saveOperator[opcnt++] = '+';
			continue;
		}
		if (s.top() == saveArray[index])
		{
			result[index++] = s.top();
			s.pop();
			saveOperator[opcnt++] = '-';
			continue;
		}
		else
		{
				s.push(cnt++);
				saveOperator[opcnt++] = '+';
			
		}
		
	}

s는 스택, saveArray는 원본 수열, result는 비교할 수열, saveOperator는 +와 - 연산자를 넣은 배열이다.

먼저 스택이 비어있을 때를 고려해야 한다.

 

스택이 비어있는데 무작정 top()을 비교한다던가 pop을 한다던가 하면 당연히 없는 데이터를 사용하게 되므로

오류가 난다. empty를 먼저 처리해준다.

push와 pop을 같이 처리하려니까(처음에는 그렇게 했었다) 오류가 있어서 한 번에 하나만 처리하도록 했다.

push를 하거나 pop을 했을 때 continue를 사용해서 한 번에 하나의 연산만 처리하도록 구현했다.

두 번째 조건문 s.top() == saveArray[index]는 스택의 탑과 원본 수열을 비교하는 것이다.

탑과 현재 원본 수열이 같으면 이 데이터는 현재 pop해야 하는 데이터다. 그러므로 index를 1 증가시키면서

result에 데이터를 복사하고, pop을 통해 데이터를 없애준다.

마지막 else문은 empty()도 아니고, 데이터도 다른 경우이므로 push를 해주었다.

 

[고려해볼 사항]

1. pop을 할 때는 cnt를 증가시키면 안 된다.

2. 한번에 push와 pop을 처리하는것 보다(가능한지 모르겠지만) 하나씩 처리하는게 낫다.

 

3. 위에도 작성했지만 스택이 비었을때 연산을 할 수 없다.

*잘못된 정보,오타 수정 지적 환영합니다. 댓글로 남겨주시면 반영하겠습니다.