[백준(BOJ)] 14713번 앵무새 C++

문제 : https://www.acmicpc.net/problem/14713

14713번: 앵무새

 

어떤 문제인가?

n가지의 문장과 기준이 되는 문장을 입력받는다. n가지 문장의 단어들은 뒤죽박죽 섞여있다.

이때, n가지 문장들의 단어들의 순서를 잘 조합해서 기준 문장을 만들 수 있는지의 여부를 묻는 문제이다.

 

 

접근 방법

기준 문장의 첫 단어와 n가지 문장들의 첫 단어가 일치하는지를 확인해가며

만약 일치한다면 pop 시켜주는 방법을 떠올렸다.

vector와 queue를 사용해야겠다고 생각했다.

 

int n;
cin >> n;
vector<queue<string>> word(n);
queue<string> standard;

 

string s;
getline(cin, s);

for (int i = 0; i < n; i++) {
    getline(cin, s);
    istringstream ss(s);
    string w;

    while (getline(ss, w, ' ')) {
        word[i].push(w);
    }
}

이 부분은 입력받은 n가지 문장을 공백 기준으로 분리해서 queue에 추가하는 부분이다.

 

string l;
getline(cin, l);
istringstream ss(l);
string l2;

while (getline(ss, l2, ' ')) {
    standard.push(l2);
}

이 부분은 기준 문장을 공백 기준으로 분리해서 queue에 추가하는 부분이다.

 

 

bool possible = true;

while (!standard.empty()) {
    bool nowPossible = false;

    for (int i = 0; i < n; i++) {
        if (word[i].front() == standard.front() && !word[i].empty()) {
            word[i].pop();
            standard.pop();
            nowPossible = true;
            break;
        }
    }
    if (!nowPossible) {
        possible = false;
        break;
    }
}

기준 문장이 빌 때까지 반목 문을 통해 연산을 할 것이다.

왜 기준 문장이 빌 때까지냐면 아까 말했듯이 첫 단어를 비교해서 pop 하는 방식이므로 기준 문장이 비었다는 말은 즉, n가지 문장으로 기준 문장을 완성할 수 있다는 말이기 때문이다.

 

가능 여부를 판단하는 변수를 선언해줬다.

 

이제 for문을 보자.

vector안에 있는 queue들의 front(첫 단어)를 기준 queue의 front(첫 단어)와 비교한다.

만약 이 둘이 같다면 각 queue를 pop 시켜준다.

그리고 nowPossible을 true로 바꿔준다.

 

if문에서 nowPossible이 false라는 소리는 n가지 문장의 첫 단어와 기준 문장의 첫 단어가 일치하지 않는다는 뜻이다.

따라서 기준 문장을 만들 수 없으므로 반복문을 탈출한다.

 

for (int i = 0; i < n; i++) {
    if (!word[i].empty()) {
        cout << "Impossible";
        return 0;
    }
}

혹시나 n가지 문장 중에 안 쓰인 단어가 있어도 문제의 조건상 불가능하기 때문에 Impossible을 출력하고 main함수를 종료한다.

 

if (possible) {
    cout << "Possible";
} else {
    cout << "Impossible";
}

위의 for문에서 main함수가 종료되지 않았다면 possible의 값에 따라 출력해주면 끝!

 

 

무엇이 어려웠는가?

문자열을 공백 단위로 분리해서 저장하는 것이 어려웠다.

어려웠다기 보단 아예 방법을 몰라서 구글링을 했다.

자바의 split함수가 정말 빛처럼 보였다.

 

"앵무새는 자신이 기억하고 있는 문장을 끝까지 말한 다음 pps789에게 돌아가며, cseteram은 모든 앵무새가 돌아갈 때까지 단어를 받아 적는다."

문제의 이 부분을 놓쳐서 또 시간이 많이 걸렸다.

처음엔 그냥 기준 문장이 완성만 되면 끝인 줄 알았는데, 알고 보니 앵무새가 모든 단어를 다 말해야 되는 것이었다.

 

배운 점

문제가 길어도 꼼꼼하게 읽어보자.

분명히 놓치는 부분이 있을 것이고 그 부분이 문제에서 숨겨둔 함정일 수도 있다!