문제
P[0], P[1], ...., P[N-1]은 0부터 N-1까지(포함)의 수를 한 번씩 포함하고 있는 수열이다. 수열 P를 길이가 N인 배열 A에 적용하면 길이가 N인 배열 B가 된다. 적용하는 방법은 B[P[i]] = A[i]이다.
배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾는 프로그램을 작성하시오. 비내림차순이란, 각각의 원소가 바로 앞에 있는 원소보다 크거나 같을 경우를 말한다. 만약 그러한 수열이 여러개라면 사전순으로 앞서는 것을 출력한다.
풀이
내가 생각한 알고리즘
- 수열 A를 입력 받는다
- 수열 B에 저장한 후, 정렬한다.
- A를 돌면서 B의 인덱스를 P에 저장한다. 찾은 인덱스의 원소는 0으로 초기화 시켜 중복을 방지한다.
- P를 출력한다.
정답 코드
n = int(input())
A = []
B = []
P = []
# for i in range(0, n):
A = list(map(int, input().split(' ')))
B = A.copy()
B.sort()
r = 0
for j in range(0, n):
r = B.index(A[j])
P.append(r)
B[r] = 0
print((' ').join(map(str, P)))개선
주어진 코드의 공간 복잡도와 시간 복잡도를 평가해보겠습니다.
-
공간 복잡도:
- 입력 리스트
A와B의 크기는 입력으로 주어진n에 비례합니다. - 추가적으로 결과를 저장하는 리스트
P의 크기도 입력으로 주어진n에 비례합니다. - 따라서 전체적으로 공간 복잡도는 O(n)입니다.
- 입력 리스트
-
시간 복잡도:
- 입력 리스트
A를 생성하는 데 O(n)의 시간이 소요됩니다. - 리스트
B를 생성하고 정렬하는 데 O(n log n)의 시간이 소요됩니다. - 이후 중복된 수를 처리하면서
B.index()를 호출하는 데 최악의 경우 O(n)의 시간이 소요됩니다. 그리고 중복된 수의 처리를 위해B리스트의 해당 값에 0을 대입하는 데 상수 시간이 걸립니다. - 따라서 전체적으로 시간 복잡도는 O(n log n) + O(n) = O(n log n)입니다.
- 입력 리스트
따라서 주어진 코드의 공간 복잡도는 O(n)이며, 시간 복잡도는 O(n log n)입니다.
공간 복잡도 면에서는 입력 리스트인 A와 B, 그리고 결과를 저장하는 리스트 P가 모두 입력 크기에 비례하여 O(n)의 공간을 사용합니다. 따라서 전체적으로 공간 복잡도는 O(n)입니다.
시간 복잡도 면에서는 다음과 같은 부분을 고려해야 합니다.
- 입력 리스트 A를 생성하는 데 O(n)의 시간이 걸립니다.
- 리스트 B를 A를 복사하고 정렬하는 데 O(n log n)의 시간이 소요됩니다.
- 이후 중복된 수를 처리하면서 B.index()를 호출하는 데 최악의 경우 O(n)의 시간이 소요됩니다. 이때 중복된 수를 처리하기 위해 B 리스트를 업데이트하는 데는 O(1)의 시간이 걸립니다.
따라서 전체적으로 시간 복잡도는 O(n log n) + O(n) = O(n log n)입니다.
이러한 공간 복잡도와 시간 복잡도를 고려하면 주어진 코드가 입력 크기가 작을 때에는 효율적으로 동작할 수 있지만, 입력 크기가 커지면 성능 저하가 발생할 수 있습니다. 따라서 입력 크기에 따라 최적화가 필요할 수 있습니다.
원래 딕셔너리 사용하는 것도 고려해봤는데, (키-밸류) 식으로 저장하면 중복 처리가 어려울거 같아서 이렇게 코드를 짰다.
Lesson Learn
이 문제를 풀면서 가장 헷갈렸던 것은
마지막 출력을 하는 부분이다.
print(' ).join(map(str, P)))암기하자 !!
