글 읽기 - 반례를 모르겠습니다. 도와주십시오..

bluecube 3년 전 0

이것저것 해보다가 도저히 반례를 찾지 못하여 질문글 올립니다.

무엇이 문제일까요... ㅜㅜ

판정은 '틀렸습니다'로 나옵니다.

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

using namespace std;

bool comp(pair<string, int> i, pair<string, int> j) { return i.second < j.second; }

int main() {

	int n, b;
	string a;

	cin >> n;

	vector<pair<string, int>> word;

	for (int i = 0; i < n; i++) {
		cin >> a;
		b = a.size();
		word.push_back(pair<string, int>(a, b));
	}

	sort(word.begin(), word.end(), comp);		//글자개수별 정렬

	word.erase(unique(word.begin(), word.end()), word.end());	//중복제거

	int start = 0;
	int end = 0;
	int length;

	for (int i = 0; i < int(word.size()); i++) {
		if (i == 0) {
			length = word[i].second;
		}
		else if (i == int(word.size()) - 1) {
			if (word[i].second == length) {
				sort(word.begin() + start, word.end());
			}
			else {
				sort(word.begin() + start, word.begin() + i);
			}
		}
		else {
			if (word[i].second != length) {
				end = i;
				sort(word.begin() + start, word.begin() + end);
				start = i;
				length = word[i].second;
			}
		}


	}
	for (int i = 0; i < int(word.size()); i++) {
		cout << word[i].first << endl;
	}
}

nahwasa 3년 전 2

중복 제거가 제대로 안되고 있습니다. 아래와 같이 중간에 다른 단어가 나온 경우용.

3
aa
ab
aa

bluecube 3년 전 1

댓글 확인하고 반례를 찾았습니다. 감사합니다.

중복제거 부분을 정렬부분 맨 마지막으로 해서 visual studio상에서 제대로 중복제거가 되는것을 확인했습니다.

하지만 백준에 입력했을때 시간초과판정이 나와서 다시 한번 더 수정을 해봐야 할 것 같습니다.

다시한번 감사드립니다.

nahwasa 3년 전 0

네넹! 시간초과는 확실하실꺼여요.

33라인부터 시작되는 정렬 로직이 매우 비효율적입니다.

사실 bool comp에 정렬 기준을 다 넣어두시면 sort 한방에 가능합니다.

33이하 라인 로직은 필요없구용

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

문제

문제

출처

ICPC

반례를 모르겠습니다. 도와주십시오..

bluecube 3년 전 0

nahwasa 3년 전 2

bluecube 3년 전 1

nahwasa 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말