[백준 1874] 스택 수열

입출력 속도 때문에 하루 종일 푼 문제

입출력 속도에 대한 내용은 여기에서 볼 수 있다.

2024.07.31 - [Programming/C++] - C++ 입출력 속도 높이기

C++ 입출력 속도 높이기

 

문제

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

코드

// 처음에 푼 풀이
// 코드가 난잡함

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<int> inputSeq; // 입력받은 배열
	int n;
	cin >> n;

	// 수열 값 입력
	for (int i = 0; i < n; i++)
	{
		int inputNum;
		cin >> inputNum;
		inputSeq.push_back(inputNum);
	}

	// 한 개의 수만 있는 경우 무조건 수열을 만들 수 있음
	if (n == 1)
	{
		cout << "+" << '\n' << "-";
		return 0;
	}

	auto progress = inputSeq.begin(); // 수열을 어디까지 확인했는지 나타내는 이터레이터

	vector<int> tempStack; // 임시 벡터
	vector<int> result; // 1 ~ n 사이의 수로 만든 수열을 저장할 벡터
	vector<char> operationLog; // 연산 기록

	// tempStack에 집어 넣을 1 ~ n 사이의 수
	int num = 1;

	// 입력 수열 전체 순회
	while (progress != inputSeq.end())
	{
		// 1부터 시작해 n까지 오름차순으로 tempStack에 저장
		if (!tempStack.empty())
		{
			if (tempStack.back() == *progress) // 만약 스택의 맨 위에 있는 값이 현재 progress가 가리키는 값과 같다면
			{
				result.push_back(tempStack.back()); // 스택 맨 위 값을 결과 벡터에 넣음
				tempStack.pop_back(); // tempStack의 옮긴 값 삭제
				operationLog.push_back('-');
				progress++; // 이터레이터 한 칸 전진
				continue; // 검사 한 번 더 하기 위해 continue
			}
			else if (tempStack.back() > *progress) // progress가 가리키는 값이 현재 tempStack에 있는 마지막 값보다 작다면 해당 수열을 만들 수 없음
			{
				cout << "NO" << '\n';
				return 0;
			}
		}

		tempStack.push_back(num);
		operationLog.push_back('+');

		if (num < n) // num == n이 되면 더 이상 증가하는 것을 멈추고 스택에 남아있는 숫자와 progress를 비교하는 작업만 함
		{
			num++;
		}
	}


	if (!tempStack.empty()) // 스택에 수가 남아있으면
	{
		cout << "NO" << '\n';
	}
	else if (inputSeq == result) // 입력 수열과 결과 수열이 같으면
	{
		for (const char& elem : operationLog)
		{
			cout << elem << '\n';
		}
	}
	else
	{
		cout << "NO" << '\n';
	}
}

// 정답 참고 풀이

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	vector<char> oper; // 연산 결과를 저장할 벡터
	stack<int> stack; // 수열을 만들 스택
	stack.push(0); // 빈 스택 참조할 때 오류 방지

	bool isValidSeq = true; // 유효한 수열인지 확인

	int n;
	cin >> n;

	int currentNum = 1; // 1 ~ n 숫자 중 현재 숫자

	for (int i = 0; i < n; i++)
	{
		int inputNum; // 수열에 있는 각각의 수
		cin >> inputNum;
		
		// 스택에 집어 넣었다가 빼면서 수열을 만듦
		// 그렇기 때문에 스택의 top을 계속 검사하면서 입력받은 수보다 작은 동안 계속 오름차순으로 집어넣음
		while (stack.top() < inputNum)
		{
			oper.push_back('+'); // 연산
			stack.push(currentNum); // 스택에 오름차순으로 push
			currentNum++;
		}
		
		// while 문의 조건이 더 이상 유효하지 않았을 때
		// top과 inputNum이 같으면 수열을 계속 만들 수 있고
		// 아니라면 유효하지 않은 수열임
		if (stack.top() == inputNum)
		{
			oper.push_back('-'); // 연산
			stack.pop(); // top 값을 뺌		
		}
		else
		{
			isValidSeq = false;
		}
	}

	if (isValidSeq)
	{
		for (const char& elem : oper)
		{
			cout << elem << '\n';
		}
	}
	else
	{
		cout << "NO";
	}
}

풀이

두 개의 풀이가 있다. (두 번째 풀이는 https://velog.io/@suyeon-jung/%EB%B0%B1%EC%A4%80-1874-%EC%8A%A4%ED%83%9D-%EC%88%98%EC%97%B4-cpp 를 참고했다.)

 

기본적인 아이디어는 오름차순으로 스택에 1~n의 수를 넣다가 수열에 맞는 수가 나오면 그 수를 빼는 방식이다.

여기서 두 풀이의 차이점은 수를 하나씩 받아서 비교를 하냐, 아니면 수열의 수를 모두 받아서 벡터에 놓은 다음에 이터레이터로 하나씩 비교하냐의 차이이다.

첫 번째 코드 풀이

입력받은 수열을 저장할 inputSeq, 수열을 만들기 위한 임시 스택 tempStack, 그리고 결과를 저장할 result, 연산 결과를 저장할 operationLog까지 4개의 벡터가 있다.

// 수열 값 입력
for (int i = 0; i < n; i++)
{
    int inputNum;
    cin >> inputNum;
    inputSeq.push_back(inputNum);
}

// 한 개의 수만 있는 경우 무조건 수열을 만들 수 있음
if (n == 1)
{
    cout << "+" << '\n' << "-";
    return 0;
}

먼저 수열을 모두 입력받아 inputSeq 벡터에 저장한다. 이때, 입력 값과 상관 없이 하나의 숫자만 있다면 무조건 수열을 이룰 수 있으므로 +와 -를 출력한 후 프로그램을 종료한다.

auto progress = inputSeq.begin(); // 수열을 어디까지 확인했는지 나타내는 이터레이터

vector<int> tempStack; // 임시 벡터
vector<int> result; // 1 ~ n 사이의 수로 만든 수열을 저장할 벡터
vector<char> operationLog; // 연산 기록

// tempStack에 집어 넣을 1 ~ n 사이의 수
int num = 1;

// 입력 수열 전체 순회
while (progress != inputSeq.end())
{
    // 1부터 시작해 n까지 오름차순으로 tempStack에 저장
    if (!tempStack.empty())
    {
        if (tempStack.back() == *progress) // 만약 스택의 맨 위에 있는 값이 현재 progress가 가리키는 값과 같다면
        {
            result.push_back(tempStack.back()); // 스택 맨 위 값을 결과 벡터에 넣음
            tempStack.pop_back(); // tempStack의 옮긴 값 삭제
            operationLog.push_back('-');
            progress++; // 이터레이터 한 칸 전진
            continue; // 검사 한 번 더 하기 위해 continue
        }
        else if (tempStack.back() > *progress) // progress가 가리키는 값이 현재 tempStack에 있는 마지막 값보다 작다면 해당 수열을 만들 수 없음
        {
            cout << "NO" << '\n';
            return 0;
        }
    }

    tempStack.push_back(num);
    operationLog.push_back('+');

    if (num < n) // num == n이 되면 더 이상 증가하는 것을 멈추고 스택에 남아있는 숫자와 progress를 비교하는 작업만 함
    {
        num++;
    }
}

수가 두 개 이상 있다면 수열을 만들 수 있는지 확인해야 한다. 앞서 입력 받은 수열에서 각각의 수를 가리킬 이터레이터 progress가 있다. 이 progress가 inputSeq의 마지막까지 갈 때까지 다음과 같은 처리를 반복한다.

 

1. 만약 tempStack이 비어있지 않다면

• tempStack의 맨 마지막 값이 progress가 가리키는 inputSeq의 값과 같다면 그 값을 result로 옮기고 연산 기록을 남긴 후, 이터레이터를 한 칸 전진시키고 continue를 통해 다음 단계로 넘어간다
• tempStack의 맨 마지막 값이 progress가 가리키는 inputSeq의 값보다 크다면 inputSeq는 오름차순으로 저장된 스택으로 만들 수 없는 수열이므로 NO를 출력하고 프로그램을 종료한다.

2. tempStack에 num을 추가하고 연산 기록을 남긴다.

3. num이 n보다 작은 경우에만 num을 증가시킨다 (num의 범위는 1 ~ n이기 때문)

if (!tempStack.empty()) // 스택에 수가 남아있으면
{
    cout << "NO" << '\n';
}
else if (inputSeq == result) // 입력 수열과 결과 수열이 같으면
{
    for (const char& elem : operationLog)
    {
        cout << elem << '\n';
    }
}
else
{
    cout << "NO" << '\n';
}

위의 과정이 끝났을 때, inputSeq와 result가 같다면 수열을 만들 수 있는 것이므로 연산 결과를 출력한다. 그렇지 않은 경우에는 모두 NO를 출력한다.

 

두 번째 코드 풀이

첫 번째 코드는 난잡하고 직관적이지도 않다. 그래서 다른 코드를 참고한 후 다시 작성해봤다.

이 코드는 첫 번째 풀이와 다르게 연산 결과를 저장할 벡터와, 수열을 만들 때 사용할 스택만 있다.

vector<char> oper; // 연산 결과를 저장할 벡터
stack<int> stack; // 수열을 만들 스택
stack.push(0); // 빈 스택 참조할 때 오류 방지

bool isValidSeq = true; // 유효한 수열인지 확인

int n;
cin >> n;

이때 주의해야 할 점이 있다. 입력받은 수와 스택의 최상위에 있는 수를 계속해서 비교하는 코드가 있는데, 스택이 비어있을 때 top 함수를 호출할 경우 런타임 에러가 발생한다. 그러므로 사용되지 않는 수 (여기에서는 0)를 미리 스택에 삽입해 오류 발생을 방지한다.

int currentNum = 1; // 1 ~ n 숫자 중 현재 숫자

for (int i = 0; i < n; i++)
{
    int inputNum; // 수열에 있는 각각의 수
    cin >> inputNum;

    // 스택에 삽입했다가 빼면서 수열을 만듦
    // 그렇기 때문에 스택의 top을 계속 검사하면서 입력받은 수보다 작은 동안 계속 오름차순으로 집어넣음
    while (stack.top() < inputNum)
    {
        oper.push_back('+'); // 연산
        stack.push(currentNum); // 스택에 오름차순으로 push
        currentNum++;
    }

    // while 문의 조건이 더 이상 유효하지 않았을 때
    // top과 inputNum이 같으면 수열을 계속 만들 수 있고
    // 아니라면 유효하지 않은 수열임
    if (stack.top() == inputNum)
    {
        oper.push_back('-'); // 연산
        stack.pop(); // top 값을 뺌		
    }
    else
    {
        isValidSeq = false;
    }
}

수열에 있는 각각의 수를 입력받는다. 스택의 top이 현재 입력받은 수보다 작다면 계속해서 currentNum(1~n)을 1씩 증가시키면서 스택에 넣어준다.

 

위의 과정을 계속 반복하다가 top이 현재 입력받은 수보다 작지 않게 된다면 while문을 탈출하게 된다. 그러면 top이 입력받은 수와 같거나 크거나 둘 중에 하나인데, 같은 경우에는 수열을 만들 수 있는 상태이므로 연산 결과를 저장한 다음 stack에서 제거한다. top이 입력받은 수보다 큰 경우에는 오름차순으로 저장된 스택으로는 만들 수 없는 배열이므로 플래그 변수를 false로 설정한다.

if (isValidSeq)
{
    for (const char& elem : oper)
    {
        cout << elem << '\n';
    }
}
else
{
    cout << "NO";
}

모두 확인했다면 플래그 변수 값에 따라 결과를 출력한다.