[백준 1764번] 듣보잡(이분탐색, C++ / python)

 

처음에 map에다 때려 박고 M개를 비교했는데,

400ms가 나왔다. 실버에서 400ms라..

뭔가 이상해서 C++로 푸신분들 보니 30ms도 안나와서 알고리즘 분류를 보니 이분탐색으로 되어있더라..

그래서 이분탐색으로도 한번 풀어보고, 파이썬으로 이분탐색 안풀어봤으니 풀어보고자한다.

#include <bits/stdc++.h>

using namespace std;
vector<string> v;
map<string,int> m;
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    for(int i = 0 ; i< N; i++)
    {
        string s;
        cin >> s;
        m[s]; // 다 넣고
    }
    for(int i = 0 ; i< M; i++)
    {
        string s;
        cin >>s;
        if(m.find(s) != m.end()) v.push_back(s); // 중복되는게 있으면 v에 넣기.
    }
    sort(v.begin(), v.end());
    cout << v.size() << endl;
    for(int i = 0; i< (int)v.size(); i++)
    {
        cout << v[i] << endl;
    }
}

---

C++ 이분탐색 풀이

#include <bits/stdc++.h>

using namespace std;
vector<string> v;
vector<string> res;
map<string,int> m;

bool bi_search(string& s){

    int left =0, right = (int)v.size()-1, mid;
    while(left <= right)
    {
        mid = left + (right-left)/2;
        if(s.compare(v[mid])==0) return true;
        else if(s.compare(v[mid]) <0) {
            right = mid-1;
        }
        else if(s.compare(v[mid]) >0){
            left = mid+1;
        }
    }
    return false;
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N, M;
    cin >> N >> M;
    for(int i = 0 ; i< N; i++)
    {
        string s;
        cin >> s;
        v.push_back(s);
    }
    sort(v.begin(), v.end());
    for(int i = 0 ; i< M; i++)
    {
        string s;
        cin >> s;
        if(bi_search(s)) res.push_back(s);
    }
    sort(res.begin(), res.end());
    cout << res.size() << endl;
    for(int i = 0 ; i< (int)res.size(); i++)
    {
        cout << res[i] << '\n';
    }
}

---

Python 풀이

흠.. 위 C++ 첫번째 풀이에서 map을 썼듯이 python의 dictionary를 사용했는데, 꽤나 속도가 좋았다.

기억해야 하는점은 input받는거... 아직 python에서 input받는게 익숙치 못했다.

import sys
sys.stdin = open("data.txt","r")
input = sys.stdin.readline

주피터에서 했는데 data.txt에 백준 testcase를 입력해두고 local에서 테스트 했었다.

아래 코드에서 strip을 해주지 않으면

이처럼 \n이 str에 포함되니 유의하자. strip, lstrip, rstrip이 있다.

1차원 list를 입력으로 받는 것, 2차원 list를 입력으로 받는것 등등 입력에 대한 연습이 필요해보인다.

또한 dictionary에서 has_key(key)가 있던데 3.x버전에서는 사라졌다고 한다 . in을 그냥 쓰자.

import sys
input = sys.stdin.readline

N,M = map(int, input().split())

listen = { input().strip() : 0 for _ in range(N) }
listen_see = list()
for _ in range(M):
    a = input().strip()
    if a in listen:
        listen_see.append(a)
listen_see.sort()

print(len(listen_see))
for name in listen_see:
    print(name)

아 그리고 나중에 dictionary가 아니라 list로 받고, binary_search로도 풀어보자. 

 

Python 이진탐색 풀이

아닛... ? dictionary가 더 빨랐다.. 그것도 3배나..

import sys
input = sys.stdin.readline

def bi_search(ary,target):
    left, right = 0, len(ary)-1
    while left <= right:
        mid = left+ (right-left)//2
        if target == ary[mid]:
            return True
        elif target < ary[mid]:
            right = mid-1
        elif target > ary[mid]:
            left =mid+1
    return False
    
N,M = map(int, input().split())

listen = [input().strip() for _ in range(N)]
listen.sort()
listen_see = list()
for _ in range(M):
    a = input().strip()
    if bi_search(listen,a):
        listen_see.append(a)

listen_see.sort()
print(len(listen_see))
for name in listen_see:
    print(name)

 

C++28ms인 분이 계시길레 이래저래 해봤는데... 32ms가 한계더라 ㅠㅠ