백준 2866번 문자열 잘라내기[C++]

1. 개요

 안녕하세요. 오늘 문제의 유형은 해쉬 + 이분 탐색입니다. 처음엔 해쉬만 사용해 풀이했습니다. 그런데 유형을 까보니 이분 탐색도 있었습니다. 그래서 이분 탐색으로도 풀이해 봤는데요. 로직은 똑같으나 naive하게 구현하느냐 parametric search를 사용하느냐 정도의 차이입니다. 시간 소요는 이분 탐색이 400ms 정도 빠릅니다.

 

2. 문제 풀이

 parametric search를 결정하기 위한 조건을 세워봅시다. 이분 탐색을 사용하여 count에 값을 미리 결정합니다. 그리고 해당 count를 만족하기 위한 문자열를 뽑아줍니다. 문자열 중 중복인 값이 있다면 false를 반환하고 없다면 true를 반환하게 합니다.

 

 중복을 확인하는 것은 unordered_set<string>을 사용합니다. count 값을 기준으로 보드판에서 지워진 행의 개수를 알 수 있으므로 loop 순회로 문자열을 뽑아올 수 있으니 구현이 가능합니다.

 

 naive 한 풀이도 문제없이 AC를 받을 수 있습니다. 각 열에 해당하는 문자열을 뽑은 다음 count를 증가하면서 문자열 앞단의 값을 제거하면서 진행하면 됩니다.

 

3. 코드

< naive >

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, m;
vs board;

int main() {
    fastio(nullptr, false);

    cin >> n >> m;

    vs(m).swap(board);

    for(int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for(int j = 0; j < m; j++) {
            board[j].pb(str[j]);
        }
    }

    for(auto &str : board) {
        reverse(all(str));
    }

    int count{};
    for( ; count < n; count++) {
        unordered_set<string> chk;
        for(auto &str : board) {
            if(chk.find(str) != chk.end()) {
                cout << count - 1; 
                exit(0);
            }
            chk.insert(str);
            str.pop_back();
        }
    }

    cout << count - 1;
}

 

< parametric search >

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

int n, m;
vs board;

bool solve(int count) {
    set<string> chk;
    for(int j = 0; j < m; j++) {
        string str{};
        for(int i = count; i < n; i++) {
            str.pb(board[i][j]);
        }
        chk.insert(str);
    }

    return sz(chk) == m;
}

int main() {
    fastio(nullptr, false);

    cin >> n >> m;
    vs(n).swap(board);
    for(auto &str : board) {
        cin >> str;
    }

    int st{0}, en{n};
    while(st + 1 < en) {
        int mid = (st + en) >> 1;
        (solve(mid) ? st : en) = mid;
    }

    cout << st;
}

 

4. 제출 결과