[BOJ][Python] 1015번 - 수열 정렬[정렬- 실버 4티어]

알고리즘 태그

[정렬]

태그 설명

정렬이란 데이터의 집합을 어떠한 기준의 대소관계를 따져 일정한 순서로 줄지어 세우는것

문제

백준 문제 - 수열 정렬

링크: 수열 정렬

문제설명

P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.
배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.

문제를 처음에 이해를 못했는데, 여러가지 글을 읽어보고 이해를 했다.

출제자의 의도는 아래와 같다.

예제 입력 

4
2 1 3 1

2 1 3 1 을 오름차순으로 정렬하면 1 1 2 3 이다.

이제 2 1 3 1 각각의 숫자가 정렬한 리스트에서 몇 번째 인덱스인지 출력하면 된다.

따라서 2 0 3 1 을 출력하면 정답이 된다.

즉, 정렬을 했을때 주어진 값들의 인덱스 값을 추출하는 문제였다

📃 소스코드 및 설명

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

# 파이썬dict를 사용해서 key, value를 주고 key값을 찾는 방식으로 접근함
dict_numbers = {index:data for index, data in enumerate(sort_numbers)}

result = []

for num in numbers:
  for key, value in dict_numbers.items():
    if value == num:
      # 내가 찾는 값이 있으면 추가하고, dict에서 삭제해준다.
      # break을 한 이유는 동일한 값이 있을수도 있기 때문에 중첩을 방지하고자 처리함
      result.append(key)
      del dict_numbers[key]
      break
      
# unpacking을 위해서 *를 사용      
print(*result)

출제자의 의도는 이런방식으로 푸는건 아닌거 같은데, 다른사람의 코드를 알아보자

 

📃 소스코드 및 설명

n = int(input())
numbers = list(map(int, input().split()))
sort_numbers = sorted(numbers)
result = []

for index in range(n):
  # 정렬이 된 리스트 내부에서 기존 리스트의 값들의 위치 찾기
  # 즉 정렬된 값 : [1,1,1,3,4,4,6,6] 에서 기존 리스트 [4,1,6,1,3,6,1,4]의 인자값 대입해서
  # 위치를 찾는다.
  
  idx = sort_numbers.index(numbers[index])
  result.append(idx)
  
  # 찾고 난 후에 해당 위치를 다시 찾을수 있으므로 방어적인 코드로 None르로 대체!
  sort_numbers[idx] = None
  
print(*result)

다른 사람의 코드를 살펴보았을때 오히려 정렬문제를 해결하기 더 좋은? 접근법인거 같다.