[알고리즘][백준] 19637. IF문 좀 대신 써줘

문제

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

 

 

문제 아이디어

이 문제에서 시간 초과가 나는 경우는 보통 아래와 같습니다.

 

1. 그냥 O(N) (리스트 한바퀴 쭉 탐색하기) 로 탐색할 경우

10^5 * 10^5 이므로 O(N)이면 무조건 시간 초과입니다. 그런데 문제 조건을 자세히 보면, if ~ else if ~ ... 요 조건이 오름차순으로 되어 있습니다. 정렬된 배열 (리스트) & O(N) 이 시간초과 = 이분 탐색 문제입니다. (무슨 공식도 아니고..)

 

2. 중복값을 제거하거나 맨 앞으로 이동시키려고 while문 안에서 중복값의 맨 앞 위치를 찾는 경우

그런데 문제를 보면 값이 또 같은 값이 들어가 있는 경우가 있습니다. 이 경우에 중복값이 몇개 없으면 상관 없지만, 10^5개가 모두 100으로 같다면? O(N)으로 만드는 것과 다름이 없으니까 이 경우 시간 초과입니다.

 

결국

따라서 이분 탐색에 중복 조건까지 고려를 해야 합니다. 이렇게 정렬된 리스트에서 중복 값이 들어있는 것들 중 원하는 값을 찾는 경우를 Lower Bound & Upper Bound 로 찾습니다. Lower Bound 와 Upper Bound의 설명 및 구현 방법은 아래와 같습니다.

 

Lower Bound: 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치입니다.
1 2 3 3 3 3 4 5 6 7 일 때 3을 찾는다면 Lower Bound는 3이겠군요.

Upper Bound: 특정 값보다 처음 큰 값을 찾는 경우를 말합니다. 
1 2 3 3 3 3 4 5 6 7 일 때 3의 Upper Bound는 4입니다.

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

	# 1 2 3 3 3 4 5 6 중에서 맨 처음 3을 찾는 것이므로
    # 3보다 크면 end를 mid - 1 로 잡고 다시 반띵, 
    # 똑같애도 맨 처음 위치를 찾는 것이므로 똑같이 end = mid - 1로 잡고 반띵
    if targetList[mid] >= a: 
        end = mid - 1
        
    # 작으면 3을 아직 못 찾은거니까 start를 mid 앞으로 보내고 반띵
    elif targetList[mid] < a:
        start = mid + 1

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

	# 1 2 3 3 3 4 5 6 에서 4의 위치를 찾는 것이므로 start를 최대한 앞으로 끌어올려야 됩니다.
    # 3보다 작거나 같은 상태이면 아직 맨 뒤의 3까지 오지 않은거니까 start = mid + 1
    if targetList[mid] <= a:
        start = mid + 1
    
    # 3보다 아직 크면 end를 mid로 내려줍니다.
    elif targetList[mid] > a:
        end = mid

# 정답
import sys
input = sys.stdin.readline

N, M = list(map(int, input().split(' ')))
typeList = []
for t in range(N):
    type, amount = list(map(str, input().split(' ')))
    typeList.append([type, int(amount)])

for n in range(M):
    a = int(input().rstrip())

    start = 0
    end = len(typeList)
    mid = -1
    result = ''
    while start <= end:
        mid = (start + end) // 2

        if typeList[mid][1] >= a: 
             end = mid - 1
             result = typeList[mid][0]
        elif typeList[mid][1] < a:
            start = mid + 1
    print(result)

참고로 
import sys
input = sys.stdin.readline

input().rstrip()

을 안하면 입출력에서 시간 초과가 발생할 것입니다. (아마도..)