[오답노트/파이썬] 코드업 - 기억력 테스트 3

문제

풀지 못한 이유

• 시간 초과가 문제였다. 첫 번째 시도는 입력값의 범위를 신경 쓰지 않고 순차 탐색으로 풀이해서 시간 초과되었다. 두 번째 시도는 문제에서 입력값을 오름차순 정렬하여 준 이유가 있을 거라 생각하여 이진 탐색으로 풀었지만 그래도 시간 초과되었다.(문제의 도움말은 보지 않았다.)
• 이진 탐색으로 풀어도 시간 초과되었던 이유는 이진 탐색의 결과로 True/False를 반환했고, for문 안에 if문을 한 번 더 타서 값을 찾았을 때와 못찾았을 때 print 했기 때문이다.

풀이

이진 탐색을 하기 위해선 반드시 탐색할 리스트가 정렬되어 있어야 한다. 그리고 정가운데 지점(mid)을 기준으로 찾으려는 값이 mid보다 작으면 왼쪽 부분을 탐색하고, 찾으려는 값이 mid보다 크면 오른쪽 부분을 탐색한다. mid가 찾는 값이 될 때까지 이 과정을 반복한다.

n = int(input())
nums = list(map(int, input().split()))
m = int(input())
ques = map(int, input().split())

# 이진탐색으로 찾기
def findNum(start, end, arr, target):

    # 시작지점이 끝지점보다 작거나 같을 때까지 반복
    while start <= end:
        mid = (start + end) // 2    # 중간지점

        # 숫자를 찾았을 때 인덱스 값 반환
        if arr[mid] == target:    
            return mid + 1

        # 중간지점이 찾는 값보다 크면 왼쪽 부분 탐색
        elif arr[mid] > target:   
            end = mid - 1
            
        # 중간지점이 찾는 값보다 작으면 오른쪽 부분 탐색
        else:
            start = mid + 1
            
    return -1    # 찾는 숫자가 없으면 -1 반환

for n in ques:
    print(findNum(0, len(nums)-1, nums, n), end=' ')

원래 for 문을 아래와 같이 작성했었다. 다시 보니 정말 생각 없이 짠 것 같다. 위의 코드와 비교했을 때 시간이 더 걸리는 건 당연하다. for 문안에 if 문으로 값을 판별하는 것도 모자라 숫자를 찾았을 때 다시 nums 리스트에서 인덱스를 찾아 가져오다니.. 정신 차리자!!!

for n in ques:
	if findNum(0, len(nums)-1, nums, n):
    	print(nums.insert(n)+1, end=' ')
    else:
    	print(-1, end=' ')

풀이 회고

제발 문제 읽을 때 입출력 값 제한 사항 꼭 확인하자.. 그리고 어떻게 하면 실행 속도를 빠르게 할 수 있는지, 최소한의 코드로 작성할 수 있을지 고민하며 풀자..!