본문 바로가기
Programming/알고리즘

[백준 / Python] 1015번 수열 정렬

by castberry_ 2024. 3. 28.
반응형

문제

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

 

1015번: 수열 정렬

P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다. 배열 A가 주

www.acmicpc.net

 

풀이

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

sortdata = sorted(data)
answer = [0] * n

for i in range(n):
    answer[i] = sortdata.index(data[i])
    sortdata[sortdata.index(data[i])] = -1
    
print(*answer)

 

 

이 문제는 조금 헷갈릴 수 있다. 

배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾아야한다. 

비내림차순은 연속되는 원소가 존재하는 오름차순이라고 이해하면 된다. 

(ex. 1 1 2 2 3 4 4) 

 

이 문제를 푸는 방법은 다음과 같다. 

 

2 3 1이 A 배열이고, 

1 2 3이 비내림차순이 된 A 배열이다. 

 

P는 아래와 같이 구한다.   

배열의 길이는 3이니 인덱스는 0~2이다. 

1. 인덱스가 0일때 A배열은 2이고, 비내림차순이 된 A배열에는 2가 인덱스 1에 있다.  -> 배열 P에 1을 추가

2. 인덱스가 1일때 A배열은 3이고, 비내림차순이 된 A배열에는 3이 인덱스 2에 있다.  -> 배열 P에 2을 추가

3. 인덱스가 2일때 A배열은 1이고, 비내림차순이 된 A배열에는 1이 인덱스 0에 있다.  -> 배열 P에 0을 추가

 

배열P은 1 2 0이 된다. 

 

 

반응형

댓글