글 읽기 - 어려운 문제네요; 오답 케이스좀 알려주세요

na982 7년 전 0

그리디 방식으로,

1. 한개의 단어라도 그룹단어 조건에 만족하지 않으면 그룹단어가 아니라고 판단.

2. 어떤 단어 1개를 추가 한다.

3. 현재까지 추가된 단어의 앞자리 또는 뒷자리 알파벳과 같은 단어로만 되어있으면 연결한다.

4. 현재 까지 까지 연결된 단어의 앞자리 알파벳으로 끝나는 단어는 앞에 붙이고, 뒷자리 알파벳으로 시작하는 단어는 뒤에 붙인다.

5. 4번에서 단어를 붙이면 다시 3번으로 간다.

6. 5번까지 추가된 단어가 없고, 남은 단어 중에서 시작과 끝이 현재까지 나오지 않아서 앞 또는 뒤 에 붙일수 있는 단어는 뒤에다 붙이고,

답이 여러개 나올수 있거나, 답이 될수 없는 경우라고 체크한다.

7. 6번이 만족했으면 3번으로, 6번이 만족하지 않았으면 종료 시킨다.

위와 같은 로직으로; 구현하였는데; 어디가 구멍인지 잘 모르겠습니다;;

#include <stdio.h>
#include <string.h>
#include <deque>
#include <algorithm>
using namespace std;

typedef struct DATA{
	char text[21];
	int flag;		//1 is all same text, 2 is different sp, ep;
	int sp, ep;
	DATA(){}
	DATA(char* pText, int _flag, int _sp, int _ep){
		strcpy(text, pText);
		flag = _flag, sp = _sp, ep = _ep;
	}
};

int n;
DATA data[101];

deque<DATA> q;

int init(){
	int ret = 1;
	for (int i = 0; i < n; ++i){
		data[i].flag = 1;
		char mark = data[i].text[0];
		int len = strlen(data[i].text);

		int alpha[26] = { 0, };
		for (int k = 0; k < len; ++k){
			if (k == 0){
				alpha[(int)(data[i].text[k]- 'a')] = 1;
			}
			else {
				if (data[i].text[k] != data[i].text[k - 1]){
					if (alpha[(int)(data[i].text[k] - 'a')] == 0){
						alpha[(int)(data[i].text[k] - 'a')] = 1;
					}
					else {
						return ret = 0;
					}
				}
			}
		}

		if (mark != data[i].text[len - 1]){
			data[i].flag = 2;
		}
		data[i].sp = (int)(data[i].text[0] - 'a');
		data[i].ep = (int)(data[i].text[len - 1] - 'a');
	}
	return ret;
}

int solve(){
	int ret = 1;
	while (!q.empty())	q.pop_back();

	int alpha[26] = { 0, };
	int picked[101] = { 0, };
	picked[0] = 1;
	alpha[data[0].sp] = 1, alpha[data[0].ep] = 1;
	q.push_back(data[0]);
	while (q.size() < n){
		int size = q.size();
		DATA front = q.front();
		DATA back = q.back();
		for (int next = 0; next < n; ++next){
			if (data[next].flag == 1){
				if (picked[next] == 0 && front.sp == data[next].ep){
					picked[next] = 1;
					q.push_front(data[next]);
				}
				if (picked[next] == 0 && back.ep == data[next].sp){
					picked[next] = 1;
					q.push_back(data[next]);
				}
			}
		}
		for (int next = 0; next < n; ++next){
			if (data[next].flag == 2){
				if (picked[next] == 0 && front.sp == data[next].ep && alpha[data[next].sp] == 0){
					picked[next] = 1;
					alpha[data[next].sp] = 1;
					q.push_front(data[next]);
					break;
				}
				if (picked[next] == 0 && back.ep == data[next].sp && alpha[data[next].ep] == 0){
					picked[next] = 1;
					alpha[data[next].ep] = 1;
					q.push_back(data[next]);
					break;
				}
			}
		}

		
		if (size == q.size()){
			ret = 0;
			int loop_flag = 0;
			for (int next = 0; next < n; ++next){
				if (data[next].flag == 2){
					if (picked[next] == 0){
						if (alpha[data[next].sp] == 0 && alpha[data[next].ep] == 0){
							picked[next] = 1;
							alpha[data[next].sp] = 1, alpha[data[next].ep] = 1;
							q.push_back(data[next]);
							loop_flag = 1;
						}
					}
				}
			}
			if (loop_flag == 0)	break;
		}
	}

	if (ret == 0){
		for (int i = 0; i < n; ++i){
			if (picked[i] == 0){
				if (alpha[data[i].sp] == 1 || alpha[data[i].ep] == 1){
					return ret = -1;
				}
			}
		}
	}
	

	return ret;
}

int main()
{
	//freopen("input.txt", "r+", stdin);
	
	scanf("%d", &n);
	memset(data, 0, sizeof(data));
	for (int i = 0; i < n; ++i){
		scanf("%s", data[i].text);
	}
	if (init()){
		int ret = solve();
		if (ret == 1){
			for (int i = 0; i < q.size(); ++i){
				printf("%s", q[i].text);
			}
			printf("\n");
		}
		else if (ret == 0){
			printf("-_-\n");
		}
		else if (ret == -1){
			printf("gg\n");
		}
	}
	else {
		printf("gg\n");
	}
	return 0;
}

nsy0042 7년 전 0

안녕하세요~

만약 원래 단어로 가능한 것이 여러 개일 경우에는 -_-를 출력한다. 만약 만들 수 없다면 gg를 출력한다.

여러개일 경우는 -_- 출력하는 것인데, gg가 나오는군요

per

pyy인 경우

apper과 appyy 2가지 경우가 있는데, gg인 경우가 나오게 되네요.

na982 7년 전 0

ap, per, pyy의경우

3가지를 모두 사용해서 그룹단어를 만들수 있느냐가 문제 입니다.

3개중에 2개만 연결해서 그룹단어가 된다고, 그룹단어라고 하지 않습니다.;

nsy0042 7년 전 0

위에꺼는 죄송합니다.

제가 잘 몰라서 그랬는데 이번 반례는 맞나 잘 모르겠지만 올리겠습니다.

per

rqqe인 경우면

결과는 apperrqqe로 나오지만, per에서의 e 하고 rqqe에서 e가 따로따로 나오기 때문에 그룹단어가 아니지 않나 싶습니다.

na982 7년 전 0

맞습니다;

계속 저도 케이스 만들어가면서 수정하고 있는데; 코드가 점점 길어지네요;;

지금까지 수정한 코드입니다.

위의 케이스는 수정하였는데, 아직도 오답이네요

#include <stdio.h>
#include <string.h>
#include <deque>
#include <algorithm>
using namespace std;

typedef struct DATA {
	char text[21];
	int flag;       //1 is all same text, 2 is different sp, ep;
	int alpha[26];
	int sp, ep;
	DATA() {}
	DATA(char* pText, int _flag, int _sp, int _ep) {
		strcpy(text, pText);
		flag = _flag, sp = _sp, ep = _ep;
	}
};

int n;
DATA iData[101];

deque<DATA> q;

int init() {
	int ret = 1;
	for (int i = 0; i < n; ++i) {
		iData[i].flag = 1;
		char mark = iData[i].text[0];
		int len = strlen(iData[i].text);

		int alpha[26] = { 0, };
		for (int k = 0; k < len; ++k) {
			if (k == 0) {
				alpha[(int)(iData[i].text[k] - 'a')] = 1;
			}
			else {
				if (iData[i].text[k] != iData[i].text[k - 1]) {
					if (alpha[(int)(iData[i].text[k] - 'a')] == 0) {
						alpha[(int)(iData[i].text[k] - 'a')] = 1;
					}
					else {
						return ret = 0;
					}
				}
			}
		}

		if (mark != iData[i].text[len - 1]) {
			iData[i].flag = 2;
		}
		iData[i].sp = (int)(iData[i].text[0] - 'a');
		iData[i].ep = (int)(iData[i].text[len - 1] - 'a');

		for (int k = 0; k < len; ++k) {
			iData[i].alpha[iData[i].text[k] - 'a'] = 1;
		}
	}
	return ret;
}

int is_front_valid(int* alpha, int pos) {
	int ret = 1;
	int x = q.front().sp;
	for (int i = 0; i < 26; ++i) {
		if (iData[pos].alpha[i] == 1) {
			if (alpha[i] == 1) {
				if(!(i == x && i == iData[pos].ep)){
					return ret = 0;
				}
			}
		}
	}
	return ret;
}

int is_back_valid(int* alpha, int pos) {
	int ret = 1;
	int x = q.back().ep;
	for (int i = 0; i < 26; ++i) {
		if (iData[pos].alpha[i] == 1) {
			if (alpha[i] == 1) {
				if (!(i == x && i == iData[pos].sp)) {
					return ret = 0;
				}
			}
		}
	}
	return ret;
}

int is_all_valid(int* alpha, int pos) {
	int ret = 1;
	for (int i = 0; i < 26; ++i) {
		if (iData[pos].alpha[i] == 1) {
			if (alpha[i] == 1) {
				return ret = 0;
			}
		}
	}
	return ret;
}

void set_picked(int* alpha, int pos) {
	int ret = 1;
	for (int i = 0; i < 26; ++i) {
		if (iData[pos].alpha[i] == 1) {
			alpha[i] = 1;
		}
	}
}

int solve() {
	int ret = 1;
	while (!q.empty())  q.pop_back();

	int alpha[26] = { 0, };
	int picked[101] = { 0, };
	picked[0] = 1;
	set_picked(alpha, 0);
	q.push_back(iData[0]);
	int temp = n;
	while (q.size() < temp) {
		int size = q.size();
		DATA front = q.front();
		DATA back = q.back();
		for (int next = 0; next < n; ++next) {
			if (iData[next].flag == 1) {
				if (is_front_valid(alpha, next)) {
					set_picked(alpha, next);
					q.push_front(iData[next]);
				}
				if (is_back_valid(alpha, next)) {
					set_picked(alpha, next);
					q.push_back(iData[next]);
				}
			}
		}
		for (int next = 0; next < n; ++next) {
			if (iData[next].flag == 2) {
				if (is_front_valid(alpha, next)) {
					set_picked(alpha, next);
					q.push_front(iData[next]);
					break;
				}
				if (is_back_valid(alpha, next)) {
					set_picked(alpha, next);
					q.push_back(iData[next]);
					break;
				}
			}
		}

		if (size == q.size()) {
			ret = 0;
			int loop_flag = 0;
			for (int next = 0; next < n; ++next) {
				if (iData[next].flag == 2) {
					if (picked[next] == 0) {
						if (is_all_valid(alpha, next)) {
							set_picked(alpha, next);
							q.push_back(iData[next]);
							q.push_front(iData[next]);
							loop_flag = 1;
							++temp;
							break;
						}
					}
				}
			}
			if (loop_flag == 0) break;
		}
	}

	if (ret == 0) {
		for (int i = 0; i < n; ++i) {
			if (picked[i] == 0) {
				return ret = -1;
			}
		}
	}

	return ret;
}

int main()
{
	freopen("input.txt", "r+", stdin);

	scanf("%d", &n);
	memset(iData, 0, sizeof(iData));
	for (int i = 0; i < n; ++i) {
		scanf("%s", iData[i].text);
	}
	if (init()) {
		int ret = solve();
		if (ret == 1) {
			for (int i = 0; i < q.size(); ++i) {
				printf("%s", q[i].text);
			}
			printf("\n");
		}
		else if (ret == 0) {
			printf("-_-\n");
		}
		else if (ret == -1) {
			printf("gg\n");
		}
	}
	else {
		printf("gg\n");
	}
	return 0;
}

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

문제

문제

출처

ICPC

어려운 문제네요; 오답 케이스좀 알려주세요

na982 7년 전 0

nsy0042 7년 전 0

na982 7년 전 0

nsy0042 7년 전 0

na982 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말