[BaekJoon/백준] 1620번 C++

C++ 을 연습하는 중인데

이 문제 덕분에 pair와 vector에 대해 조금 더 공부하고 이해하는 시간을 가질 수 있었다.

 

다만 덕분에 시간을 좀 많이 투자했다 ㅜㅜ

 

이 문제는 아무런 조치 없이 선형검색으로 하다가는 시간초과가 나게 된다.

N , M의 범위가 100,000 이기 때문에 주어진 2초 안에서 얼핏보면 O(n)에서시간초과가 일어나지 않을 것 같지만

테스트케이스 단위가 아니라 한번에 받는 것이기 때문에 아마 주어진 시간은 모든 검색에 대한 사항인 것 같고, 게다가 문자열의 길이가 20이기 때문에 시간복잡도가 상당히 길어질 것이라는 것을 종합적으로 생각해줘야 한다.

 

이 문제는 검색에 있어서

문자열 검색 : O(log n)

숫자 검색 : O(1)

로 구현하면 된다.

 

문자열 검색을 위해서

vector<pair<string ,int>> book 을 선언했고

입력받은 값들을 string 기준으로 오름차순으로 정렬한 뒤에 이진검색을 수행해줬다.

 

숫자 검색을 위해서

 vecotr<string> Ibook 을 선언했고

입력받은 숫자를 인덱스 값으로 받아들여서 바로 접근해주면 된다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<pair<string, int>> book;
vector<string> Ibook;

int bin_search(int n, string key) {

    int pl = 0; // 검색 범위 맨 앞의 인덱스
    int pr = n - 1; // 검색 범위 맨 끝의 인덱스
    int pc; // 검색 범위 한가운데의 인덱스

    do {
        pc = (pl + pr) / 2;

        if(book[pc].first == key) {
            return pc;
        }
        else if(book[pc].first < key)
            pl = pc + 1;
        else if(book[pc].first > key)
            pr = pc - 1;

    } while(pl <= pr);

    return -1; // 검색 실패

}

// C언어에서도 못본 'int &a' 이런식으로 매개변수를 받기도 하던데.. 주소를 받는다는 뜻이다.
// C에서 'int *a' 이런식으로 받는 것 처럼 C++에선 이렇게 받는듯
// https://hashcode.co.kr/questions/7379/c-배열-형태의-vector-매개변수

// 참고로 여기서의 구현은 주소로 다뤄주지 않아도 잘 작동한다.
bool compare(pair<string, int> a, pair<string, int> b) {
    // 오름차순 정렬.
    return a.first < b.first;
}

int main() {
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, M;
    string s;
    cin >> N >> M;
    
    for(int i = 1; i <= N; i++) {
        cin >> s;
        //make_pair 함수를 써서
        //make_pair(s, i) 해도 되고, {s, i}로 넘겨줘도 된다.
        book.push_back({s, i});
        Ibook.push_back(s);
    }

    sort(book.begin(), book.end(), compare);
    
    
    for(int i = 0; i < M; i++) {
        
        cin >> s;
        if(atoi(s.c_str()) == 0 || s == "0") {
            cout <<  book[bin_search(book.size(), s)].second << '\n';
        } else
            cout << Ibook[atoi(s.c_str()) - 1] << '\n';
        
    }
}

 

 

참고 : jaimemin.tistory.com/990