문제
프로그래밍 문제를 풀다 보면 뒤죽박죽인 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
728x90
'코딩 어쩌구 > 코딩테스트' 카테고리의 다른 글
[코드업] 3015번 성적표 출력 (0) | 2021.11.10 |
---|---|
[코드업] 1805번 입체기동장치 생산공장 (0) | 2021.11.09 |
[이것이 코딩테스트다] 1. 출제 경향 분석 및 파이썬 문법 (1) | 2021.11.08 |
[코드업] 6098번 성실한 개미 (0) | 2021.11.08 |
[코드업] 6097번 설탕과자 뽑기 (0) | 2021.11.08 |