BOJ 1764 - 듣보잡

https://www.acmicpc.net/problem/1764

1764번: 듣보잡

 

이 문제를 풀면서 배웠던 두가지가 있는데

 

첫째는, c++ STL vector 를 사용할때, 초기에 size 를 설정하지 않고 push_back 을 하면

2^n 만큼의 메모리 크기를 잡는다는것.

그래서 resize 를 통해서 미리 크기를 잡아주면 연산 속도도 줄이고, 메모리 크기도 줄일수 있다는 점을 알게 되었다.

 

둘째는, 코드 작성의 편리성 측면에 근거하여, algorithm header 에 있는 binary_search 함수를 써서 문제를 풀자.

문제 풀기 전엔 algorithm 헤더 파일에 binary_search 함수가 있는지 몰라서 아래와 같이 직접 구현하려 했다.

 

- c++

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int N, M;
vector<string> unknown;
vector<string> answer;
 
void binary_search(string in_str) {
    int low = 0;
    int high = unknown.size();
    int mid;
    while (low <= high) {
        mid = (low + high) / 2;
        if (unknown[mid] == in_str) {
            answer.push_back(in_str);
            return;
        } else if (unknown[mid] > in_str) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
}
 
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin >> N >> M;
 
    unknown.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> unknown[i];
    }
 
    sort(unknown.begin(), unknown.end());
 
    for (int i = 0; i < M; i++) {
        string in_str;
        cin >> in_str;
        binary_search(in_str);
    }
 
    int answer_size = answer.size();
 
    sort(answer.begin(), answer.end());
 
    cout << answer_size << '\n';
 
    for (int i = 0; i < answer_size; i++) {
        cout << answer[i] << '\n';
    }
 
    return 0;
}
 

 

 

 그러나 이렇게 답을 제출하면 런타임 에러가 떴다.

 

그래서 코드를 아래 처럼 재수정해서 제출했더니 통과가 되었다.

 

- c++

#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
int N, M;
vector<string> unknown;
vector<string> answer;
 
int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cin >> N >> M;
 
    unknown.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> unknown[i];
    }
 
    sort(unknown.begin(), unknown.end());
 
    string str;
    for (int i = 0; i < M; i++) {
        cin >> str;
 
        if (binary_search(unknown.begin(), unknown.end(), str)) {
            answer.push_back(str);
        }
    }
 
    int answer_size = answer.size();
 
    sort(answer.begin(), answer.end());
 
    cout << answer_size << '\n';
 
    for (int i = 0; i < answer_size; i++) {
        cout << answer[i] << '\n';
    }
 
    return 0;
}