[codeup] 3004. 데이터 재정렬

https://codeup.kr/problem.php?id=3004

데이터 재정렬

1. 문제

데이터를 오름차순으로 정렬했을 때의 순위를 각 원소 순위에 맞게 출력하라.

2.  알고리즘

데이터를 정렬하여 순위를 찾고 해당 순위를 각 원소에 부여한다.

3. 주의할 점

python에서 제공하는 index()함수는 시간복잡도가 O(N)이므로 이 함수를 이용했을 경우에는 시간초과가 발생한다. 따라서 binary search를 구현하고 해당 알고리즘을 사용해서 index를 찾아야한다.

 

4. 소스코드

n = int(input())
# 입력 처리
data = list(map(int, input().split()))

# binary search 함수
def bin_search(data, start, end, k):
    while start <= end:
        mid = (start + end) // 2
        if data[mid] == k:
            return mid
        elif data[mid] < k:
            start = mid + 1
        else:
            end = mid - 1

# 데이터의 각 원소에 오름차순 순위 부여
def resort(data):
    index_memo = ""
    sorted_data = sorted(data)
    for i in data:
        index_memo += str(bin_search(sorted_data, 0, len(data)-1, i)) + " "
    return index_memo

# 결과값 출력
print(resort(data))