글 읽기 - 테스트 케이스 중간에 자꾸 틀립니다..

marco2520332 6년 전 0

사전 순으로 노드들을 연결해서 그래프를 만든다음에,

위상 정렬 방법을 통해 결과를 출력하도록 했습니다.

큐가 중간에 비게되면 !

2개 이상이 되면 ? 를 출력하도록 구현했습니다.

아래 코드에서 어디가 잘못 된 것인지 모르겠습니다..

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int N;
int indegree[26], alphaCheck[26];
vector<vector<char>> list, adj;
vector<char> ans;

int main ( void )
{
	char input[11], cnt = 0, alphaNum = 0, questionMark = 0;
	scanf ( "%d", &N );
	list.resize ( N );
	for ( int i = 0; i < N; i++ ) {
		list[i].resize ( 10 );
	}
	adj.resize ( 26 );
	for ( int n = 0; n < N; n++ ) {
		scanf ( "%s", input );
		for ( int i = 0; input[i] != '\0'; i++ ) {
			list[n][i] = input[i];
			if ( alphaCheck[input[i] - 'a'] == 0 ) {
				alphaCheck[input[i] - 'a'] = 1;
				alphaNum++;
			}
		}
	}
	for ( int n = 0; n < N - 1; n++ ) {
		for ( int m = n+1; m < N; m++ ) {
			for ( int c = 0; c < 10; c++ ) {
				if ( list[n][c] == list[m][c] ) continue;
				else if(!(list[n][c] == 0 || list[m][c] == 0)){
					adj[list[n][c] - 'a'].push_back ( list[m][c] );
					indegree[list[m][c] - 'a']++;
					break;
				}
				else if ( list[n][c] == 0 || list[m][c] == 0 ) {
					printf ( "!\n" );
					exit ( 0 );
				}
			}
			if ( list[n][0] != list[m][0] ) {
				n = m - 1;
				break;
			}
		}
	}
	queue<char> q;
	for ( int i = 0; i < 26; i++ ) {
		if ( alphaCheck[i] && indegree[i] == 0) {
			q.push ( i + 'a' );
		}
	}
	while ( cnt < alphaNum ) {
		if ( q.size ( ) == 0 ) {
			printf ( "!\n" );
			exit ( 0 );
		}
		char node = q.front ( ); q.pop ( );
		ans.push_back ( node );
		for ( int n = 0; n < adj[node - 'a'].size ( ); n++ ) {
			char nextNode = adj[node - 'a'][n];
			indegree[nextNode - 'a']--;
			if ( !indegree[nextNode - 'a'] ) q.push ( nextNode );
		}
		cnt++;
		if ( q.size ( ) > 1 ) {
			questionMark = 1;
		}
	}
	if ( questionMark ) {
		printf ( "?\n" );
		exit ( 0 );
	}
	for ( int i = 0; i < ans.size ( ); i++ ) {
		printf ( "%c", ans[i] );
	}printf ( "\n" );

	return 0;
}

marco2520332 6년 전 1

if ( list[n][0] != list[m][0] ) {
n = m - 1;
break;
}

중간에 이 부분이 필요없는 연산을 제거할 수 있다고 넣었는데, 이것 때문에 틀렸네요..!

donghy9508님 감사합니다!

#include<iostream>
#include<queue>
#include<vector>
using namespace std;

int N;
int indegree[26], alphaCheck[26], check[26][26];
vector<vector<char>> list, adj;
vector<char> ans;

int main ( void )
{
	char input[11], alphaNum = 0;
	scanf ( "%d", &N );
	list.resize ( N );
	for ( int i = 0; i < N; i++ ) {
		list[i].resize ( 10 );
	}
	adj.resize ( 26 );
	for ( int n = 0; n < N; n++ ) {
		scanf ( "%s", input );
		for ( int i = 0; input[i] != '\0'; i++ ) {
			list[n][i] = input[i];
			if ( alphaCheck[input[i] - 'a'] == 0 ) {
				alphaCheck[input[i] - 'a'] = 1;
				alphaNum++;
			}
		}
	}
	for ( int n = 0; n < N - 1; n++ ) {
		for ( int m = n+1; m < N; m++ ) {
			for ( int c = 0; c < 10; c++ ) {
				if ( list[n][c] == list[m][c] ) continue;
				else if(!(list[n][c] == 0 || list[m][c] == 0)){
					if ( check[list[n][c] - 'a'][list[m][c] - 'a'] ) break;
					check[list[n][c] - 'a'][list[m][c] - 'a'] = 1;
					adj[list[n][c] - 'a'].push_back ( list[m][c] );
					indegree[list[m][c] - 'a']++;
					break;
				}
			}
		}
	}
	queue<char> q;
	for ( int i = 0; i < 26; i++ ) {
		if ( alphaCheck[i] && indegree[i] == 0) {
			q.push ( i + 'a' );
		}
	}
	for(int i=0; i<alphaNum; i++){
		if ( q.empty() ) {
			printf ( "!\n" );
			exit ( 0 );
		}
		if ( q.size ( ) > 1 ) {
			printf ( "?\n" );
			exit ( 0 );
		}
		char node = q.front ( ); q.pop ( );
		ans.push_back ( node );
		for ( int n = 0; n < adj[node - 'a'].size ( ); n++ ) {
			char nextNode = adj[node - 'a'][n];
			indegree[nextNode - 'a']--;
			if ( !indegree[nextNode - 'a'] ) q.push ( nextNode );
		}
	}
	for ( int i = 0; i < ans.size ( ); i++ ) {
		printf ( "%c", ans[i] );
	}printf ( "\n" );

	return 0;
}

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

문제

문제

출처

ICPC

테스트 케이스 중간에 자꾸 틀립니다..

marco2520332 6년 전 0

marco2520332 6년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말