글 읽기 - 질문드립니다... 반례를 모르겠어요

kgient 4년 전 0

안녕하세요. 처음으로 질문글을 적습니다.

질문글의 반례와 제가 생각할 수 있는 예제와 엣지 케이스를 넣어도 잘 모르겠습니다.

구현은 stack 사용해서 처음에 입력 받으면서 stack에 넣는데 top 값보다 큰 경우는 미리 답을 선택하고,

아닌 경우 계속 stack에 쌓도록 구현하였습니다.

배열의 숫자를 다 입력 받았을 때는 stack에서 하나씩 뽑아서 스택의 위에 값이랑 비교를 했습니다.

반례 좀 찾아주시길 부탁드려요.. 질문 올리는 형식을 잘 모르지만 염치 불구하고 올려요ㅠ

#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;

int N;
pair<int, int> p;
pair<int, int> top;
stack<pair<int,int>> s;
int ans[1000001];
int main()
{

	scanf("%d", &N);

	int num;
	scanf("%d", &num);
	p.first = 0;
	p.second = num;
	s.push(p);
	top = s.top();
	
	for (int i = 1; i < N; i++) {
		scanf("%d", &num);
		p.first = i;
		p.second = num;
		if (top.second >= p.second) {
			s.push(p);
			top = p;
		}
		else {
			ans[top.first] = p.second;
			s.pop();
			s.push(p);
			top = p;
		}
	}
	p = s.top();
	ans[p.first] = -1;
	s.pop();
	while (!s.empty()) {
		top = s.top();
		s.pop();
		if (top.second >= p.second) {
			ans[top.first] = -1;
			p = top;
		}
		else {
			ans[top.first] = p.second;
		}
	}

	for (int i = 0; i < N-1; i++) {
		printf("%d ", ans[i]);
	}
	printf("%d\n", ans[N - 1]);
	return 0;
}

newdeal 4년 전 2

안녕하세요.

반례 첨부해 드립니다.

5
1 1 1 3 4
//your answer:4 4 3 4 -1
//correct answer:3 3 3 4 -1

kgient 4년 전 1

감사합니다~~ 알고리즘에 구멍이 있었네요..

로직 수정하고 맞았습니다.

조언 감사드립니다^^

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

문제

문제

출처

ICPC

질문드립니다... 반례를 모르겠어요

kgient 4년 전 0

newdeal 4년 전 2

kgient 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말