글 읽기 - 어느 케이스가 빠졌는지 잘 모르겠습니다..

dhsg0717 2년 전 0

다른 분들 블로그도 참고하고, 질문 글들도 보면서 열심히 고쳐봤는데 잘 모르겠네요..

abc, ab인 경우 = !

abc, abc = ?

ab, abc = ?

그리고 답이 여러개인 경우지만 계속 계산을 하다가 모순이 있는 경우에는 !를 출력해주는 것 까지도 했습니다.

혹시 어떤 케이스에서 문제가 될 수 있으지 의견 남겨주시면 감사하겠습니다

#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<cmath>
#include<sstream>
#include<limits>
#include<algorithm>
#include<queue>

using namespace std;

int c, n;
int used_num = 0;
vector<string> words;
vector< vector<int> > adj;
vector<int> ret;

bool visited[26];
int indgree[26];

bool isMulti = false;
bool isPossible = true;

void makeGraph() {
    adj = vector< vector<int> >(26, vector<int>(26, 0));

    for(int i = 0; i < words.size() - 1; i++) {
        int cnt = 0;
        for(int j = 0; j < words[i].length(); j++) {
            if(words[i][j] != words[i + 1][j]) {
                adj[words[i][j] - 'a'][words[i + 1][j] - 'a'] = 1;
                indgree[words[i + 1][j] - 'a']++;
                break;
            }
            else {
                cnt++;
                if(cnt == words[i + 1].length() && cnt < words[i].length()) {
                    isPossible = false; 
                    return;
                }
            }
        }
    }
}

void topologySort() {
    queue<int> q;

    for(int i = 0; i < 26; i++) {
        if(visited[i] && indgree[i] == 0) {
            q.push(i);
        }
    }
    
    for(int k = 0; k < used_num; k++) {
        if(q.empty()) {
            isPossible = false;
            return;
        }

        int x = q.front();
        q.pop();
        if(q.size() >= 1) 
            isMulti = true;
        
        ret.push_back(x);

        for(int i = 0; i < 26; i++) {
            if(adj[x][i] == 1) {
                if(--indgree[i] == 0) {
                    q.push(i);
                }
            }
        }
    }
}

int main(void)
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> n;
    for(int i = 0; i < n; i++) {
        string temp;
        cin >> temp;
        words.push_back(temp);
        for(int j = 0; j < temp.length(); j++) {
            if(!visited[temp[j] - 'a']) {
                visited[temp[j] - 'a'] = true;
                used_num++;
            }
        }
    }

    makeGraph();
    topologySort();

    if(!isPossible) 
        cout << '!' << '\n';
    else if(isMulti)
        cout << '?' << '\n';
    else {
        for(int i = 0; i < ret.size(); i++)
            cout << (char)(ret[i] + 'a');
        cout << '\n';
    }
    
    return 0;
}

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

문제

문제

출처

ICPC

어느 케이스가 빠졌는지 잘 모르겠습니다..

dhsg0717 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말