[백준/1015] 수열 정렬

수열 정렬

Baekjoon Online Judge

---

알고리즘

입력된 배열 A의 오름차순을 새로운 배열에 저장하는 문제다. 처음에 문제 이해 자체가 좀 어려웠는데, 예시를 통해서 비교적 쉽게 이해할 수 있었다.

 

일단 배열 A는 수열 P처럼 0부터 N-1까지의 수를 한 번씩 포함하는게 아니라 예시의 2 1 3 1 처럼 같은 숫자가 2번 이상 반복될 수 있기 때문에 가장 작은 값부터 큰 값까지 하나씩 차례대로 순서를 찾았다. 복잡도를 따졌을 때 이러한 방식으로 문제를 해결하더라도 N <= 50이기에 큰 문제는 없었다.  

 

같은 숫자를 어떻게 처리할 것이냐가 관건이었는데, k라는 변수를 하나 만들어서 indexing하도록 지정해주었다.

---

 

전체 코드

import sys; input = sys.stdin.readline

n=int(input())
a=list(map(int, input().split()))
k = 0
b = [0]*(n)
start = min(a)
end = max(a)

for i in range(start, end+1):
    for j in range(n):
        if a[j] == i :
            b[j] = k
            k += 1
print(*b)

다른 사람의 풀이

import sys; input = sys.stdin.readline

n=int(input())
a=list(map(int, input().split()))
sorted_a = sorted(a)

solve = []
for i in a:
    solve.append(sorted_a.index(i))
    sorted_a[sorted_a.index(i)] = -1
    
print(solve)

---

알게된 점

문제를 풀고 구글링을 해보니까 굉장히 다양한 풀이를 참고할 수 있었다.

우선 입력받은 배열 A를 오름차순 정렬한 뒤, A 값을 sorted_A의 인덱스로 찾아 새로운 배열에 넣어주면서 정의하는 풀이를 봤는데 더 효율적이고 내장함수를 잘 활용한 풀이라는 생각이 들었다. 나도 처음에는 sorted()와 index()를 활용한 풀이를 생각 못한 건 아닌데 풀다가 포기했기에 이러한 풀이를 확인하는게 더 재밌었다!! PS 권태기가 와서(ㅠ) 외면하고 있었는데 조급해하지말고 다시 차근차근 풀어나가야겠다