[C/C++] 백준 14725번 - 개미굴

14725번: 개미굴

'로봇 개미가 지나온 경로 자체를 문자열로 처리를 한 뒤 중복을 제거하면 되지 않을까' 라는 생각을 했다.

만약 입력 값이 "KIWI-APPLE-BANANA" 라고 한다면, 이 경로를 다음과 같이 처리하는 것이다.

-KIWI

-KIWI-APPLE

-KIWI-APPLE-BANANA

이렇게 입력 받은 경로를 위 처럼 3개의 문자열로 저장하는 것이다.

중복을 제거하기 위해서 문자열을 저장할 때는 set을 사용했다. (정렬까지 해주니 더 좋다.)

 

이런 상황에서 다른 입력 값으로 "KIWI-APPLE-PEACH" 라는 경로가 입력되면

-KIWI

-KIWI-APPLE

-KIWI-APPLE-PEACH

위 3개의 문자열로 처리될 것이다. 

그러면 이미 set에 저장되어 있는 -KIWI, -KIWI-APPLE 2개의 문자열은 중복 제거가 될 것이다.

 

단어 앞에 있는 '-' 는 현재 경로를 오기 위해 지나온 개미굴의 개수를 나타낸다.

#include <iostream>
#include <string>
#include <algorithm>
#include <set>
using namespace std;
#define endl '\n'
#define SIZE 1001

int N;
set<string> s;

void initInput() {
    cin >> N;

    while (N--) {
        int M; cin >> M;
        string str = "";

        while (M--) {
            string input; cin >> input;
            str += "-" + input;
            s.insert(str);
        }
    }
}

void solve() {
    for (auto iter : s){
        int cnt = count(iter.begin(), iter.end(), '-');
        int pos = iter.find_last_of("-");
        string str = iter.substr(pos + 1);
        for (int i = 0; i < cnt - 1; i++) cout << "--";
        cout << str << endl;
    }
}

int main(void) {
    cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false);
    // freopen("input.txt", "r", stdin);
    initInput();
    solve();

    return 0;
}