수열 정렬
난이도 2
구분: 정렬
문제
P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.
배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.
입력
첫째 줄에 배열 A의 크기 N이 주어진다. 둘째 줄에는 배열 A의 원소가 0번부터 차례대로 주어진다. N은 50보다 작거나 같은 자연수이고, 배열의 원소는 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 비내림차순으로 만드는 수열 P를 출력한다.
예제 입력
3
2 3 1예제 출력
1 2 0문제 링크
https://www.acmicpc.net/problem/1015
문제 접근
- P배열은 0~n-1 의 값을 원소로 하나씩 가진다
- P 배열 -> A 배열-> B 배열
- B 배열은 비내림차순 (b1 <= b2 <= b3 ...) => A배열 정렬, sort()함수 이용
- B[P[i]] = A[i]를 예제 배열에 하나씩 적용하여 패턴 파악
- P의 i번째 요소 값 => B가 A[i]을 원소로 가지는 인덱스 값
코드 1
import sys
n = int(sys.stdin.readline())
arr_a = list(map(int, sys.stdin.readline().split())
arr_b = sorted(arr_a) # b배열은 비내림차순
arr_p = [0]*n
for i in range(n):
p[i] = arr_b.index(arr_a[i])
for i in range(n):
sys.stdout.write(str(p[i]) + ' ')오류
문제 조건 중,
만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다
🛠 중복처리
p[x] = y 에서 y의 값이 같을 때 예외처리 안함!
✔️ index()함수는 가장 먼저 있는 원소의 인덱스 값 출력
해결 방법
- 중복되는 값은? b배열에 원소가 중복될 때, index값도 여러개
- arr_b 배열에 방문처리 하기
- arr_b[] = -1
- arr_b는 0~n-1 수를 하나씩 가짐
- 제거만 생각하고 변경을 생각하지 못했다
코드 2
import sys
n = int(sys.stdin.readline())
arr_a = list(map(int, sys.stdin.readline().split())
arr_b = sorted(arr_a) # b배열은 비내림차순
arr_p = [0]*n
for i in range(n):
index = arr_b.index(arr_a[i])
p[i] = index
arr_b[index] = -1 # 방문처리
for i in range(n):
sys.stdout.write(str(p[i]) + ' ')