글 읽기 - '틀렸습니다.'인데 반례를 못찾겠습니다.

hungryjay 3년 전 0

벡터 <인덱스(수), 해당 숫자 개수> 로 구현했습니다.

질문 리스트에 있는 반례 전부 통과했지만 틀렸습니다. 또 반례가 어떤게 있을까요?

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> answer;

void mysort(vector <pair<int, int> > list) {
	while (list.size() > 2) {
		while (list[0].second != 0) {
			answer.push_back(list[0].first);
			list[0].second--;
		}

		list.erase(list.begin());
		
		if (answer[answer.size() - 1] + 1 == list[0].first) {
			answer.push_back(list[1].first);
			list[1].second--;
		}
	}
	if (list[0].first + 1 == list[1].first) {
		for (int i = 0; i < list[1].second; i++)
			answer.push_back(list[1].first);
		for (int i = 0; i < list[0].second; i++)
			answer.push_back(list[0].first);
	}
	else {
		for (int i = 0; i < list[0].second; i++)
			answer.push_back(list[0].first);
		for (int i = 0; i < list[1].second; i++)
			answer.push_back(list[1].first);
	}
}

int main(void) {
	int n;
	cin >> n;
	vector<pair<int, int>> list;
	int arr[1005] = { 0, };

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		arr[tmp]++;
	}
	for (int i = 0; i <= 1004; i++)
		if (arr[i] != 0)
			list.push_back(make_pair(i, arr[i]));

	mysort(list);
	for (int i = 0; i < answer.size(); i++)
		cout << answer[i] << " ";
	cout << endl;
	return 0;
}

golazcc83 3년 전 1

mysort 함수의 list의 size가 1일 때의 경우를 추가해주셔야 할 것 같네요

3
1 1 1
    
// Answer
1 1 1
    
// Output
1 1 1 ??????????

hungryjay 3년 전 0

와 이걸 생각 못하고 있었네요.. 감사합니다 !

덧붙여, size 1인 경우까지 고려해서 수정했지만 다시 '틀렸습니다'를 받았고, 이 과정에서 또다른 test case를 찾았습니다.

input

6
1 5 3 4 8 9

정답 : 1 3 5 4 9 8

output : 1 3 5 4 8 9

erase하는 과정에서 만약 해당 숫자의 개수가 0개이면 while문을 통해 계속 지우는 방법으로 수정해 문제 해결했습니다.

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

문제

문제

출처

ICPC

'틀렸습니다.'인데 반례를 못찾겠습니다.

hungryjay 3년 전 0

golazcc83 3년 전 1

hungryjay 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말