글 읽기 - 1874번 문제 도와주세요!

persona_k 5년 전 0

제가 생각한 문제의 알고리즘은 다음과 같습니다.

처음 입력 받을 때는 입력 값 만큼 push해주고 원하는 값을 얻기 위해 pop합니다.

그런 다음부터는 스택이 비어있거나 내가 얻고자 하는 now가 현재 스택에 쌓여있는 가장 위에 있는 데이터와 비교해서 now가 더 크다면

스택에 계속해서 숫자를 넣어주고, 똑같아 지면 pop을 해서 원하는 값을 얻습니다.

하지만, 내가 원하는 숫자보다 스택의 가장 위에 있는 데이터가 now보다 더 크다면, 그것은 불가능으로 end를 true로 활성화 시킵니다.

출력은 end의 기준에 따라 불가능이라면 no를

아니면, 그동안 넣었던 기호 '+', '-'를 출력합니다.

두 예시 모두 답은 나오지만, 문제는 틀렸다고 하는데

제가 놓친 부분이 있을까요??

읽어주셔서 감사합니다.

소스는 아래와 같이 첨부하였습니다.

#include <iostream>
#include <stack>
#define MAX 100005
using namespace std;

int main()
{
	int n, now, idx = 0, diff = 0, cnt = 1;
	bool first = true, end = false;
    //입력
	cin >> n;

	stack<int> s;                     // 숫자를 담을 공간
	char sign[MAX * 2] = { '\0', };   // +,-를 담을 공간

	for (int i = 0; i < n; i++) {
		cin >> now;  //현재 들어온 값

		//처음 작업
		if (first) {
			//push
			for (int j = 1; j <= now; j++) {
				s.push(cnt++);
				sign[idx++] = '+';
			}
			//pop
			s.pop();
			sign[idx++] = '-';
			first = false;
			continue;
		}

		//내가 얻고자 하는 수가 스택의 맨 위의 수보다 클 때는 push하기
		//혹은 스택이 비어있거나
		while (s.empty() || s.top() < now) {
			s.push(cnt++);
			sign[idx++] = '+';
		}

		//내가 얻고자 하는 수가 맨 위에있다면 pop하기
		if (s.top() == now) {
			s.pop();
			sign[idx++] = '-';
			if (now == 1) sign[idx++] = '-';
			continue;
		}
		//내가 얻고자 하는 수가 stack에 가장 위에 있는 수보다 작으면 불가능하다.
		else if (s.top() > now) {
			end = true;
			continue;
		}
	}

	if (end) {
		cout << "NO" << '\n'; //불가능
	}
	else {
		int size = idx - 1;
		for (int i = 0; i < size; i++) {
			cout << sign[i] << '\n';  //아니라면 기호 출력하기
		}
	}
	return 0;
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1874번 문제 도와주세요!

persona_k 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말