1015. [Python]수열 정렬

1. 문제

 

https://www.acmicpc.net/problem/1015

1015번: 수열 정렬

 

2. 접근 방법

 

• 시간 제한: 2초
• 메모리 제한: 128MB
• 정렬

 

3. 파이썬 코드

 

N = int(input())
A = list(map(int,input().split()))
# 리스트 길이를 확인해서 정답 리스트 생성
A_length = len(A)
# 0으로 이루어진 길이 리스트 생성
P = [0]*A_length
# 정렬한 리스트 생성
sorted_A = sorted(A)
# 리스트 번호를 매겨줄 변수
cnt = 0

for i in range(N):
    # 오름차순 정렬된 작은 값부터 넣어서 비교
    check = sorted_A[i]
    for j in range(N):
        # 목표값과 A리스트 값이 같으면 A리스트 값을 -1로 변환 후 P리스트에 순서 저장 후 순서값 증가
        if A[j] == check:
            P[j] = cnt
            A[j] = -1
            cnt += 1
            break
print(*P)

 

4. 문제를 풀고난 후 생각

 

• 정답으로 출력할 리스트 길이를 똑같이 만들어 준 후 A 리스트를 오름차순 정렬한 리스트를 새로 생성해준다.
• 반복문을 통해서 i 값이 0~N 까지 진행되는 동안 이중 for문을 통해서 check 라는 변수에 정렬된 리스트의 낮은 값부터 i 인덱스를 반복해가며 A 리스트에 그 값의 위치에 같은 경우 P 라는 리스트의 j 인덱스에 cnt 라는 변수를 넣어준 후 cnt 변수를 증가시킨다.
• 불필요한 연산을 하지않기 위해서 break를 걸어줬다.
• 구현보다는 문제가 무엇을 요구하는지를 생각하는 것에 시간이 좀더 들었던 것 같다.

ex) 2 3 0 이 주어져 있다면 1 2 0 이 출력되야 한다. 각 자리마다 몇번째로 작은 숫자인지를 찾는 문제이다.

 

5. 문제를 푸는데 도움이 되는 지식

 

• 정렬