글 읽기 - 1317 그룹 단어 71% 오답

goodseog 6년 전 0

1. 만약 input 이 그룹단어가 아니라면, 무조건 gg이다.

2. greedy 하게 붙일 수 있는 경우 효율적으로 붙인다.

2-1 char c 로 시작하는 단어의 집합 Cfirst, 오로지 c로 이루어진 Call, c로 끝나는 단어의 집합 Clast 수집.

기존의 word 집합에서 원소를 제거함. ( 어떤 단어가 시작과 끝 alphabet이 같으면서, group word

라면 그 단어는 하나의 alphabet으로만 이루어져있다.)

2-2 만약 모두 다 비어있을 경우, 다음 c에 대해서 조사를 한다.

2-3 만약 Cfirst 혹은 Clast가 여러개 존재할 경우, group word 를 만드는 것이 불가능하다. gg

2-4 newWord = [ Clast, Call ........ , Cfirst ] 로 새롭게 생성하여, 만약 이것이 group word 라면

리스트에 추가를 한다. group word가 아니라면 gg

3. 모든 alphabet에 대해서 2의 과정을 거친 후 words 가 여러개 존재한다면 -_-을 출력,

1개만 존재한다면 words[0] 를 출력한다.

다음과 같은 알고리즘으로 문제를 해결해보았는데, 71%에서 오답 처리가 됩니다.

혹시 잘못된 과정이나, 좋은 예시 소개해주시면 감사드리겠습니다!!

isGroupWord(str) 함수는 1316 그룹 단어 체커 문제에서 정답 처리를 받았습니다.

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

using namespace std;

struct WORD {
	string word;
	char first, last;
	WORD() {}
	WORD(string& w) {
		word = w;
		first = w[0];
		last = w[w.length() - 1];
	}
};

vector<WORD> words;

bool isGroupWord(string input) {
	int check[26] = { 0, };
	for (int i = 0; i < input.length();) {
		char c = input[i];
		if ( check[c - 'a'] == 1) return false;
		check[c - 'a'] = 1;
		while (input[i] == c) i++;
	}
	return true;
}

int main() {
	int N;
	string str;
	cin >> N;

	// 단어 input
	for (int i = 0; i < N; i++) {
		cin >> str;
		words.push_back(WORD(str));		
	}

	// 입력이 group word가 아니면 불가능
	for( WORD& w : words ){
		if (!isGroupWord(w.word)) {
			cout << "gg" << endl;
			return 0;
		}
	}

	for (char c = 'a'; c <= 'z'; c++) {
		// group word 이면서, 시작과 끝이 같다면 전부 같은 character로 이루어진 단어이다.
		vector<WORD> Cfirst, Call, Clast;

		// c 로 시작, 끝나는 단어들과 c로만 이루어진 단어를 따로 모음
		for (vector<WORD>::iterator iter = words.begin(); iter != words.end(); ) {
			if ((*iter).first == (*iter).last && (*iter).last == c) {
				Call.push_back(*iter);
				iter = words.erase(iter);
			}
			else if ((*iter).first == c) {
				Cfirst.push_back(*iter);
				iter = words.erase(iter);
			}
			else if ((*iter).last == c) {
				Clast.push_back(*iter);
				iter = words.erase(iter);
			}
			else iter++;
		}

		if (Cfirst.empty() && Call.empty() && Clast.empty()) continue;

		// 만약 c로 시작, 끝나는 단어가 여러개이면 gg
		if (Cfirst.size() > 1 || Clast.size() > 1) {
			cout << "gg" << endl;
			return 0;
		}

		// c 로 이루어진 word들을 합침
		string newWord = "";
		if (!Clast.empty()) newWord = Clast[0].word;
		for (WORD& w : Call) newWord += w.word;
		if (!Cfirst.empty()) newWord += Cfirst[0].word;

		// 만약 합친 단어들이 group word 가 아니라면 gg
		if (!isGroupWord(newWord)) {
			cout << "gg" << endl;
			return 0;
		}

		// 합쳐서 만든 새로운 단어를 투입.
		words.push_back(WORD(newWord));
	}
	

	// 합칠 수 있는거 다합쳐도 단어가 여러개면 후보가 여러개
	if (words.size() == 1) cout << words[0].word << endl;
	else                   cout << "-_-" << endl;
	
	return 0;
}

goodseog 6년 전 0

자문자답!

3 과정 전에 마지막으로 모든 단어를 합쳤을 때 group word인지 확인하여야 합니다.

그룹 단어가 불가능한 경우(gg)인데 -_- 를 출력하는 케이스가 존재합니다.

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