[백준19637] IF문 좀 대신 써줘

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

 

 

 

문제 해결 방법

시간복잡도를 고려햐여 이분탐색을 통해 문제를 풀이해야 함 

 

코드 구현

 

시간초과난 코드

# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
check=[]
for i in range(n):
    k, value = input().split()
    check.append([k, int(value)])
#받은값 정렬해줌 
# check = sorted(check, key = lambda x: x[1])

tmp = []
# 값 받고
for i in range(m):
    value = int(input())
    tmp.append(value)

tmp.sort()

cnt = 0
for i in tmp:
    if i <= check[cnt][1]:
        print(check[cnt][0])
    else:
        while 1:
            cnt+=1
            if i <= check[cnt][1]:
                print(check[cnt][0])
                break

 

 

# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
check=[]
for i in range(n):
    k, value = input().split()
    check.append([k, int(value)])
#받은값 정렬해줌 
# check = sorted(check, key = lambda x: x[1])

tmp = []
# 값 받고
for i in range(m):
    value = int(input())
    tmp.append(value)

tmp.sort()
############################
mid, high, low = (n-1)//2, n-1, 0

print('mid, high, low:', mid, high, low)

for i in range(m):
    target = tmp[i]
    print("target:", target)
    print("check:", check)
    while 1:
        if target <= check[mid][1]:
            print(check[mid][0])
            break
        elif target > check[mid][1]:
            low = mid+1
            mid = (low+high)//2
        elif target < check[mid][1]:
            high = mid-1
            mid = (low+high)//2

 

bisect 모듈을 통해 풀이한 코드

from bisect import bisect_left
import sys
# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, input().split())
checkChing=[]
checkValue=[]

for i in range(n):
    k, value = sys.stdin.readline().split()
    checkChing.append(k)
    checkValue.append(int(value))

# 값 받고
tmp = []
for i in range(m):
    value = int(sys.stdin.readline())
    tmp.append(value)

for i in range(m):
    target = tmp[i]
    tmpIndex=bisect_left(checkValue, target)
    print(check2[tmpIndex])

 

bisect 모듈 없이 풀이한 코드

 

import sys

# 전투력 10,000 이하의 캐릭터는 WEAK
# 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL
# 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호
n, m = map(int, sys.stdin.readline().split())
check=[]
for i in range(n):
    k, value = sys.stdin.readline().split()
    check.append([k, int(value)])
#받은값 정렬해줌 
check = sorted(check, key = lambda x: x[1])

tmp = []
# 값 받고
for i in range(m):
    value = int(sys.stdin.readline().rstrip())
    tmp.append(value)

for i in range(m):
    high = len(check)
    low = 0
    result = 0
    target = tmp[i]
    while low <= high:
        mid = (low + high)//2
        if target <= check[mid][1]:
            high = mid-1
            result = mid
        elif target > check[mid][1]:
            low = mid+1
    print(check[result][0])

 

시간/공간 복잡도

 

모든 경우를 다 조회할 경우 N은 100만까지 가능함. 

이 경우, 시간 초과를 면하기 위해서는 O(NlogN)의 시간복잡도가 되게끔 코드를 작성해야 한다. 

 

(기존에 작성한 코드에서 사용한 이중 반복문으로 구현하면 안됨,,)

 

(백준한정)추가시간 없음 이라는 말은 파이썬은 기존에 1초에 2천만번 연산 가능함 원래는 이런말 없으면 1초에 1억번 연산가능함 

 

최적화 및 개선

 

sys 모듈 sys.stdin.readline()을 사용하여 반복적으로 입력받을 때 input()에 비해 시간을 확 줄였음

 

 

어려웠던 점

이분탐색 개념이 가물가물 했다. 

 

어이없는 실수: 받은 값을 정렬함으로써 아무리 알고리즘을 맞게 짜도 출력 자체가 이상하게 되도록 함; (스스로 재앙을 불러옴)

 

알게된 것

• 이분탐색
  • 따로 포스팅 했음. https://dayae-dev.tistory.com/341
• bisect 모듈
  •  
• sys 모듈 sys.stdin.readline: 반복적으로 입력받을 때 input()에 비해 시간을 확 줄여줌
  • 단, 반복적으로 받지만 하나의 값만을 받는 경우 rstrip()을 통해 받은 값의 오른쪽에 붙는 개행문자를 지워줘야함.