해결 과정
단순한 문제인데 시간초과를 고려해야겠구나 싶어서 이진탐색으로 풀었다. 다른 풀이들을 보니 이보다 더 빠르게 푸는 방법이 있어서 이 아이디어를 얻어갈 수 있는 문제.
나의 풀이
이진 탐색을 이용한 풀이
이진 탐색은 라이브러리가 있지만 다시 구현해볼 겸 직접 구현했다.
N = int(input())
arr = list(map(int, input().split()))
sortedArr = sorted(list(set(arr)))
def binarySearch(arr, num):
answer = -1
start, end = 0, len(arr)-1
while start <= end:
mid = (start + end) // 2
if arr[mid] == num:
return mid
elif arr[mid] < num:
start = mid + 1
elif arr[mid] > num:
end = mid - 1
return answer
answer = []
for num in arr:
answer.append(str(binarySearch(sortedArr, num)))
print(' '.join(answer))
다른 풀이
여기서 얻어갈 수 있는 IDEA가 있어서 가져왔다.
n = input()
nums = list(map(int, input().split(" ")))
arr = sorted(set((nums)))
print(arr)
num_dict = {n: i for i, n in enumerate(arr)}
print(" ".join([str(num_dict[num]) for num in nums]))
dictionary와 for 문을 사용해서 한 줄로 만드는 방법
그리고 풀이 아이디어.
set, sorted를 해주고 난 뒤에 dictionart로 만들어두고 index를 뽑는 방식. 이게 곧 그 수보다 작은 개수가 되기에.
IDEA
'Coding Test > 문제 풀이' 카테고리의 다른 글
[문제 풀이] 짝지어 제거하기 (0) | 2022.06.08 |
---|---|
[문제 풀이] 방금그곡 (0) | 2022.05.05 |
[문제 풀이] 백준 1167 (0) | 2022.04.08 |
[문제 풀이] 백준 1043 (0) | 2022.04.08 |
[문제 풀이] 백준 1149 (0) | 2022.04.08 |