문제 바로가기
문제:
지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제를 준비했다. 먼저 제자들에게 N개의 원소를 가진 배열 A를 주고, A의 원소들이 오름차순으로 정렬된 배열 B를 만들게 한다. 그다음 M개의 질문을 한다. 각 질문에는 정수 D가 주어진다. 제자들은 주어진 정수 D가 B에서 가장 먼저 등장한 위치를 출력하면 된다. 단, D가 B에 존재하지 않는 경우에는 -1를 출력한다. Sort 마스터의 자리를 너무나도 물려받고 싶은 창국이를 위해 지훈이의 문제를 풀 수 있는 프로그램을 만들어 주자.
입력:
첫째 줄에 배열 A의 원소의 개수 N과 질문의 개수 M이 공백으로 구분되어 주어진다. 다음 줄부터 N줄에 걸쳐 정수 A_0, A_1, ... , A_{N-1}이 주어진다. 다음 줄부터 M줄에 걸쳐 정수 D가 주어진다.
출력:
M개의 질문에 대해서 주어진 D가 B에서 처음으로 등장한 위치를 출력한다. 단, 존재하지 않는다면 -1를 출력한다. (배열에서 가장 앞의 원소의 위치는 0이다.)
풀이 :
골드 같은 실버문제인 탐색 문제.. 이분탐색 싫다.
1차 시도.
import sys
n, m =map(int,sys.stdin.readline().split(" "))
lst = sorted([int(input()) for _ in range(n)])
targrt_lst = [int(input()) for _ in range(m)]
res = []
for i in targrt_lst:
if i in lst:
res.append(lst.index(i))
else:
res.append(-1)
print(*res, sep = '\n')
첫 아이디어는 배열을 정렬해놓고.
질문 리스트를 돌면서 index 로 찾으려고 했는데 시간초과이다. 나중에 알고보니 딕셔너리로 하면 통과된다고 한다. 빅오가 o(1) 이여서 그런거 같다.
정답풀이 :이분탐색
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m =map(int,sys.stdin.readline().split(" "))
lst = sorted([int(input()) for _ in range(n)])
targrt_lst = [int(input()) for _ in range(m)]
def bisec(lst , target):
left = 0; right = len(lst)-1
while left <= right:
mid = (left + right) // 2 # 중간 값
if lst[mid] < target :
left = mid + 1
elif lst[mid] > target: #
right = mid - 1
elif lst[mid] == target:
# 해당 숫자가 가장 먼저 시작 되는 곳까지 간다.
if right == mid:
break
right = mid
if lst[mid] == target:
return mid
else:
return -1
for i in targrt_lst:
print(bisec(lst, i))
# bisect_left(lower) bisect_right 지
파이썬은 이분탐색 lower, 와 right 를 지원해준다.
똑같은 숫자중에 가장앞, 가장뒤를 찾아주는것이다. 하지만 연습겸 구현을 해보았다.
elif lst[mid] == target:
# 해당 숫자가 가장 먼저 시작 되는 곳까지 간다.
if right == mid:
break
right = mid
이 부분이 중요한대
지금 숫자와 target_number 가 같으면 가장 앞의 인덱스인지 확인한다.
[2, 3, 3, 3, 4, 4, 5, 9] 일때
첫 번째 while 문을 통해
left = 0, right = 7, mid = 3 , lst[mid] = 3 이 된다.
list[mid] 와 target = 3으로 일치하지만. 가장 오른쪽에 있는 값을 가져오게 된다.
중복된 값이 있을 때, right를 현재 mid로 설정하여 계속해서 이진 탐색을 한다.
이렇게 하면 중복된 값 중에서 가장 왼쪽에 있는 값이 마지막으로 업데이트된 right에 저장된다.
이해가 되지 않는다면
이분의 그림을 한 번 보도록 하자!.
https://ojt90902.tistory.com/531
댓글