백준 - 2866 문자열 잘라내기

 

해결과정 - 딕셔너리

핵심은 아래의 문자부터 확인하여 같은 같은 문자가 있을 경우 그 열에 해당하는 문자를 확인해 나가는 것을 반복하는 것이였다 아이디어는 간단하여 해결은 쉬웠다

 

대체로 다른 사람들의 코드를 확인해 보니 이진탐색 방식과 해쉬를 사용하여 풀었고 R과 C의 값이 작아 완탐으로도 충분히 풀리는 문제였지만 내 코드가 메모리 측면에서는 별로지만 시간 측면에서는 효율적이라고 생각들었다

#include<bits/stdc++.h>

#define Fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);

using namespace std;

vector<string> inputs;
int result = 0;

//아래부터 확인하며 같은 문자열의 최고위를 확인한다
void dfs(vector<int> cols, int depth) {
    map<char, vector<int>> temp;
    result = min(result, depth);

    if (depth == 0) return;

    for (auto col : cols) {
        temp[inputs[depth][col]].push_back(col);
    }

    for (auto t : temp) {
        if (t.second.size() > 1) dfs(t.second, depth - 1);
    }

    return;
}
int main() {
    Fast;
    int R, C; cin >> R >> C;

    inputs.resize(R);
    for (int i = 0; i < R; i++) {
        cin >> inputs[i];
    }

    vector<int> init(C);
    for (int i = 0; i < C;i++) {
        init[i] = i;
    }

    result = R - 1;
    dfs(init, R - 1);

    cout << result;
    return 0;
}

 

후기 

요즘 cpu가 좋아서 메모리 중심의 코드가 더 좋아보이기는 하다