[백준/BOJ] 2469번 사다리 타기 (C++)

www.acmicpc.net/problem/2469

2469번: 사다리 타기

 

https://www.acmicpc.net/problem/2469

시작 알파벳에서 '?' 전까지, 결과 알파벳에서 '?' 전까지 알파벳의 순서를 계속 수정합니다. 위의 예시에선 최종적으로 '?' 전의 시작 알파벳과 '?' 전의 결과 알파벳은 다음과 같이 만들어집니다.

 

시작 알파벳 : [C, A, D, B, E, G, F, H, I, J]

결과 알파벳 : [C, A, B, D, G, E, F, H, J, I]

 

두 결과를 비교하여 문자가 같다면 '*', 순서가 서로 교차되어 같다면 '-', 그 외의 경우라면 불가능한 경우로 k-1개 만큼 x를 출력하게 구현하여 해결할 수 있습니다.

 

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

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

    int k, n, stop; // 사람의 수, 사다리의 행 길이, '?' 가 나오는 행 인덱스 
    cin>>k>>n;
    string start, end, answer; // 시작 알파벳, 결과 알파벳, 출력할 정답 
    vector<string> v; // 사다리 정보 저장 

    // 시작 알파벳 초기화, 결과 알파벳 입력 받기 
    for(int i = 0; i < k; i++) {
        start.push_back('A' + i);
    }
    cin>>end;

    // 사다리 정보 입력받고, '?' 나오는 행 인덱스 찾기 
    for(int i = 0; i < n; i++) {
        string str;
        cin>>str;
        v.push_back(str);
        if(str[0] == '?') stop = i;
    }

    // 시작 알파벳에서 '?' 전까지 알파벳 순서 수정  
    for(int i = 0; i < stop; i++) {
        for(int j = 0; j < v[i].size(); j++) {
            if(v[i][j] == '-') {
                swap(start[j], start[j + 1]);
            }
        }
    }

    // 결과 알파벳에서 '?' 전까지 알파벳 순서 수정 
    for(int i = n - 1; i > stop; i--) {
        for(int j = 0; j < v[i].size(); j++) {
            if(v[i][j] == '-') {
                swap(end[j], end[j + 1]);
            }
        }
    }

    // 알파벳 비교 
    bool flag = true;
    for(int i = 0; i < k - 1; i++) {
        if(start[i] == end[i]) {
            answer.push_back('*');
        } else if( (start[i] == end[i + 1]) && (start[i + 1] == end[i]) ) {
            answer.push_back('-');
            swap(start[i], start[i + 1]);
        } else {
            flag = false;
            break;
        }   
    }

    if(!flag) {
        for(int i = 0; i < k - 1; i++) {
            cout<<"x";
        }
    } else {
        cout<<answer;   
    }
}