CodeUp-3004 (데이터 재정렬)

이번 포스트에서는 CodeUp의 3004번 "데이터 재정렬" 문제를 풀어보겠다.

CodeUp

---

문제 설명은 다음과 같다.

문제 설명

입력과 출력은 다음과 같다.

입력

출력

1. ## 문제 해석:

우선 처리할 데이터의 개수를 입력 받는다. 그런 다음에 입력받은 개수를 기반으로 각 데이터를 입력받는다. 마지막으로 각 데이터의 크기 인덱스를 출력하면 된다.

2. ## 문제 풀이:

먼저 처리할 데이터의 수를 입력 받는 코드를 작성한다. 값의 범위를 검증하는 코드도 역시 추가한다.

      

      

      

    
    

      <python />
    
n = int(input())
if n < 1 or n > 50000:
    print("n의 범위는 1~50000이다.")
    quit()

그런 다음에 입력한 데이터의 수를 바탕으로 각 데이터를 입력받는 코드를 작성한다.

      

      

      

    
    

      <python />
    
n = int(input())
if n < 1 or n > 50000:
    print("n의 범위는 1~50000이다.")
    quit()

data = list(map(int, input().strip().split()))
if len(data) != n:
    print(f"{n}개의 데이터를 삽입하시오.")
    quit()

이제 각 데이터의 순서 인덱스를 구해야 하는데, 여기서는 이진탐색법을 사용해서 시간 복잡도를 최대한 줄여보는 방식으로 구해보겠다.

      

      

      

    
    

      <python />
    
def binarysearch(data, target, first, last):
    if first > last:
        return 1
    mid = int((first + last) / 2)
    if data[mid] == target:
        return mid
    elif data[mid] > target:
        return binarysearch(data, target, first, mid-1)
    else:
        return binarysearch(data, target, mid+1, last)
        
n = int(input())
if n < 1 or n > 50000:
    print("n의 범위는 1~50000이다.")
    quit()

data = list(map(int, input().strip().split()))
if len(data) != n:
    print(f"{n}개의 데이터를 삽입하시오.")
    quit()

3. ## 최종 코드:

      

      

      

    
    

      <python />
    
def binarysearch(data, target, first, last):
    if first > last:
        return 1
    mid = int((first + last) / 2)
    if data[mid] == target:
        return mid
    elif data[mid] > target:
        return binarysearch(data, target, first, mid-1)
    else:
        return binarysearch(data, target, mid+1, last)


n = int(input())
if n < 1 or n > 50000:
    print("n의 범위는 1~50000이다.")
    quit()

data = list(map(int, input().strip().split()))
if len(data) != n:
    print(f"{n}개의 데이터를 삽입하시오.")
    quit()

sorted_data = sorted(data)

for i in range(n):
    print(binarysearch(sorted_data, data[i], 0, n-1), end=" ")

4. ## 실행 결과:

코드 제출

성공