[백준/BOJ/알고리즘/파이썬(python)/C++]#1920_수 찾기[이분탐색]

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

1920번: 수 찾기

이 문제는 많은 분들이 저를 포함해서 첫 시도에 (쉬운문제네~)하고 시간초과를 맛보셨을 것 같습니다 ^^;;;

이분탐색으로 풀어야한다고 문제에 적어줘야하는거 아니냐구~ㅋㅋㅋ

 

시간초과 나서 실패한 파이썬 코드

import sys
input = sys.stdin.readline

N = int(input())
n_list = []
n_list = map(int, input().split())
n_list = sorted(n_list)

M = int(input())
m_list = []
m_list = map(int, input().split())

for i in m_list:
    if i in n_list:
        print("1")
    else:
        print("0")

파이썬의 in이 시간복잡도를 많이 잡아먹는다는 것을 알았다.

 

이 문제 아래에 분류를 누르면 '이분 탐색'이라고 써있다 ^^;;; 이분탐색으로 진작에 풀라고 하지!!

 

import sys
input = sys.stdin.readline

N = int(input())
n_list = []
n_list = map(int, input().split())
n_list = sorted(n_list)

M = int(input())
m_list = []
m_list = map(int, input().split())

def bin_search(x, n_list):
    start = 0
    end = N-1

    while start <= end:
        mid = (start + end) // 2

        if n_list[mid] == x:
            return "1"
        elif n_list[mid] < x:
            start = mid+1
        else:
            end = mid-1
    return "0"

for i in m_list:
    print(bin_search(i, n_list))

이분탐색 함수는 초보몽키님의 블로그를 참고했다.

https://wayhome25.github.io/cs/2017/04/15/cs-16/

강의노트 15-2. [탐색] 이진탐색(Binary Search) 알고리즘 · 초보몽키의 개발공부로그

 

바이너리서치 자료구조 STL을 활용하면 C++은 훨씬 쉽게 풀릴 것 같아서 C++도 오랜만에 짜봤다.

그런데 무슨일인지 또 시간초과가 나는 것이다..!!ㅜㅜ

 

C++ 시간초과 코드

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n_arr[100001];
	int m_arr[100001];
	int N;
	cin>>N;
	int n_element;
	for(int i=0;i<N;i++){
		cin>>n_arr[i];
	}
	sort(n_arr,n_arr+N);
	
	int M;
	cin>>M;
	for(int i=0;i<M;i++){
		cin>>m_arr[i];
	}
	for(int i=0;i<N;i++){
		if(binary_search(n_arr,n_arr+N,m_arr[i]))
			cout<<"1"<<endl;
		else
			cout<<"0"<<endl;
	}
}

대체 여기에 무엇이 문제인가..!! 싶어서 벡터가 아닌 그냥 배열을 써보았는데 (물론 이게 문제는 아니었을 것 같다.)

또 시간초과가 나길래 질문게시판을 가보니 cin cout 최적화를 해주어야한다고...(허탈)

endl도 왠만하면 백준에서 쓰지 말아야겠다.

그래서 어떤분들은 c++도 printf로 바꿔서 쓴다고 알고 있다.

 

맞았습니다! C++코드 

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n_arr[100001];
	int N;
	cin>>N;
	int n_element;
	for(int i=0;i<N;i++){
		cin>>n_arr[i];
	}
	sort(n_arr,n_arr+N);
	
	int M;
	cin>>M;
	int m_element;
	for(int i=0;i<M;i++){
		cin>>m_element;
		cout<<binary_search(n_arr,n_arr+N,m_element)<<"\n";
	}

}

파이썬이 문자열, 리스트 구현하는 코드에서는 압도적으로 편리하지만

STL을 활용하는 문제에선 C++이 유리한 것 같다 확실히

코테 사용언어가 C++이 아직 1위인데는 다 이유가 있다! 

 

binary_search()를 사용하면 파이썬처럼 자료구조 구현을 다 해주지 않아도 된다