[코드업] 3004번 데이터 재정렬

문제

프로그래밍 문제를 풀다 보면 뒤죽박죽인 N개의 데이터를 숫자의 크기 순으로 0 ~ N-1까지의 숫자로 재정렬 해야되는 경우가 종종 있다.

예를 들어 N=5 이고, 50 23 54 24 123 이라는 데이터가 있다면,

2 0 3 1 4 가 된다.

데이터를 재정렬하는 프로그램을 작성하시오.

 

입력

첫째 줄에 데이터의 개수 N이 입력된다. ( 1 <= N <= 50,000)

둘째 줄에 공백으로 분리되어 N개의 서로 다른 데이터가 입력된다. (값의 범위:0~500,000)

 

출력

N개의 데이터를 0 ~ N-1로 재정렬하여 출력하라.

 

---

내 풀이

1차 시도 : 시간 초과

n = int(input())

ls = list(map(int, input().split()))
lsn = [0 for _ in range(n)]

x = 0
while x != n-1 :
    for i in range(x+1,n):
        if ls[x] > ls[i]:
            lsn[x] += 1
        elif ls[x] < ls[i]:
            lsn[i] += 1
    x += 1

for j in lsn:
    print(j, end=" ")

- while문 안에 for문으로 이중 반복문을 실행시켜 복잡도가 증가했다. 당연 시간초과,,,

 

2차 시도 : 딕셔너리 이용해서 이중 반복문 없앰 : 성공!

 

1. 입력

n = int(input())
ls = list(map(int, input().split()))

# ls
## [50, 23, 54, 24, 123]

 

2. 해당 순서 저장할 lsn 빈 리스트 작성, sort한 값은 딕셔너리로 저장

lsn = [0 for _ in range(n)]
lsSort = sorted(ls)
lsDir = {string:idx for idx, string in enumerate(lsSort)}

# lsDir
## {23: 0, 24: 1, 50: 2, 54: 3, 123: 4}

 

3. 딕셔너리의 get 함수를 이용해서 ls에 저장된 순서대로 돌면서 lsDir의 value 찾기 -> lsn에 저장

for i in range(n):  
    lsn[i] = lsDir.get(ls[i])

 

4. 출력 예시와 동일한 형태로 출력

for j in lsn:
    print(j, end=" ")
    
# 2 0 3 1 4