[PS] 수 찾기

수열을 입력받고, 찾아야 하는 수들이 포함된 배열을 추가로 입력받아

수열 내에 수들이 포함되어 있는 지에 대한 여부를 1 또는 0으로 출력해야 하는 문제이다.

 

n = int(input())
entries = input().split()

m = int(input())
tofind = input().split()

result =[0]*m

for i in entries:
	for b in range(0,m):
		if int(i) == int(tofind[b]):
			result[b] = 1
			
for u in result:
	print(u)

<1차 시도>

우선 입력받은 수열을 반복문으로 전체 순회하고,

하나의 요소를 찾아야할 수열 중에 하나와 일치하는 지를 반복문으로 순회하여 판별하는 방식으로 진행.

결과는 당연히 시간 초과!

 

import sys

input = sys.stdin.readline

n = int(input())
entries = input().split()

m = int(input())
tofind = input().split()

result =[0]*m

for i in entries:
	for b in range(0,m):
		if int(i) == int(tofind[b]):
			result[b] = 1
			break
			
for u in result:
	print(u)

<2차 시도>

1차 시도 코드에서 비효율적인 부분이 어느 곳이 있을까 생각해보았는데,

입력된 수열의 수 하나와 찾아야할 수열 중의 하나를 비교하는 과정에서,

중간에 해당 수를 찾아도, 순회를 계속하고 있었기 때문에, break를 통해 이후의 순회는 버렸다.

결과는 이번에도 시간 초과.

 

import sys

input = sys.stdin.readline

n = int(input())
entries = input().split()

m = int(input())
tofind = input().split()

result =[0]*m

for i in entries:
	if len(tofind) < 1:
			break
	for b in range(0,len(tofind)):
		if int(i) == int(tofind[b]):
			result[b+(len(result)-len(tofind))] = 1
			tofind.remove(tofind[b])
			break
			
for u in result:
	print(u)

<3차 시도>

더 나아가서, 찾아야 할 수를 찾았다고 판단되면,그 배열에서 해당 수를 빼서 순회할 개수를 줄이는 방식으로 진행하였다.

하지만 그와 함께 해당 배열의 인덱스가 변경된다.

결과를 담을 배열이 원본 배열의 크기와 같으므로,해당 크기에서 현 배열의 크기를 빼면,

몇 개를 빼었는지 나오므로,인덱스에 그만큼 더해주면 원래 인덱스가 나오게 된다.

이런 방식으로 비교를 계속하다, 찾아야 할 수들의 배열 갯수가 0이 되면 배열 순회를 그만두고 결과를 출력한다.

 

import sys

input = sys.stdin.readline

n = int(input())
entries = input().split()

m = int(input())
tofind = input().split()

result =[0]*m

for i in entries:
	if len(tofind) < 1:
			break
	if i in tofind:
		result[tofind.index(i)+(len(result)-len(tofind))] = 1
		tofind.remove(i)
			
for u in result:
	print(u)

<4차 시도>

더 간결하게 만들어볼 수 없을까 생각하다가 나온 방안이 파이썬의 문법을 이용하는 것.

코드는 상당히 간결해졌으나, 실행 시간을 측정해보니 실제로는 전의 내가 짠 코드가 훨씬 빨랐다.

 

 

import sys
import time

import math


def mergesort(entries):
	if isinstance(entries,list) and len(entries) > 1 :
		pivot = math.floor(len(entries)/2)-1
		first = mergesort(entries[:pivot+1])
		second = mergesort(entries[pivot+1:])
		return merge(first,second)
	else:
		return entries
		
def merge(first,second):
	unit=[]
	
	if not isinstance(first,list):
		first = [first]
	if not isinstance(second,list):
		second = [second]
		
	first_p = second_p = 0
	
	while first_p <len(first) and second_p <len(second):
		if first[first_p]<second[second_p]:
			unit.extend([first[first_p]])
			first_p+=1
		else:
			unit.extend([second[second_p]])
			second_p+=1
			
	if first_p>=len(first) and second_p<len(second):
		unit.extend(second[second_p:])
	else:
		unit.extend(first[first_p:])
		
	return unit

def binarysearch(entries,target):
  left = 1
  right = len(entries)
  mid = 0
  while left<=right:
    mid = math.floor((left+right)/2)
    if entries[mid-1] == target:
      break
    elif entries[mid-1] <  target:
      left = mid+1
    else:
      right = mid -1
  if entries[mid-1] == target:
  	return 1
  else:
  	return 0



n = int(input())
entries = input().split()
entries = list(map(int,entries))


m = int(input())
tofind = input().split()
tofind = list(map(int,tofind))

entries = mergesort(entries)
entries = list(map(int,entries))

for x in tofind:
	print(binarysearch(entries,x))
			

<최종 시도>

앞의 코드들로는 더 효율적으로 만들 수 없을 것 같아 리서치를 진행했더니,

이진 탐색이 훨씬 빠르다는 말이 있었다.

나는 그것을 듣고 조금 의아했다.왜냐하면 이진 탐색은 정렬된 배열을 전제로 하는 탐색이기 때문이다.

정렬을 하면 그만큼의 시간이 더 들어가는 것이 아닌가?하고 생각했지만,

다른 사람들은 다 그렇게 하고 있는 것 같았다.

정렬 알고리즘은 병합 정렬을 사용하였고, 이진 탐색을 진행하여 찾은 결과가 맞으면 1,0을 반환하도록 응용하였다.

 

결과는 성공.

전에 해왔던 것들보다 훨씬!훨씬 빨랐다.

 

이진탐색이 꽤나 쓸만하다는 것을 직접 피부로 경험한 순간이었다.