[백준] 1015 - 수열 정렬

🖥️ 시작하며

솔직히 해법이 직관적으로 와닿지 않았고, 문제가 바로 이해되지는 않았다. 핵심은 배열 A가 주어졌을 때, 수열 P를 적용한 결과가 비내림차순이 되는 수열을 찾아야 한다. 비내림차순은 간단하게 중복되는 원소가 존재하는 오름차순이라고 보면 된다. 그래도 ?한다. 예시로 이해하자.

예시를 보면, 결국 수열 P는 배열 A의 각 숫자가 몇번째로 작은 수인지를 비내림차순으로 정리한 수열이라고 할 수 있다. 이것만 알면 구현 자체는 그리 어렵지 않다.

1. indexed_A 생성


indexed_A = list(enumerate(A))

결과: [(0, 2), (1, 3), (2, 1)]

indexed_A 정렬


indexed_A.sort(key=lambda x: x[1])

정렬 후 상태: [(2, 1), (0, 2), (1, 3)]

new_A딕셔너리 생성 과정


new_A = {}
for new_index, (original_index, value) in enumerate(indexed_A):
    new_A[original_index] = new_index

첫 번째 반복: new_indices[2] = 0

두 번째 반복: new_indices[0] = 1

세 번째 반복: new_indices[1] = 2

최종 new_A 딕셔너리


{2: 0, 0: 1, 1: 2}

P 배열 구성


P = [new_A[i] for i in range(len(A))]

⚙️ 코드


def Solution(N, A):
    indexed_A = list(enumerate(A))

    # 원소 값을 기준으로 정렬
    indexed_A.sort(key=lambda x: x[1])

    # 새로운 인덱스 할당
    new_A = {}
    for new_index, (original_index, value) in enumerate(indexed_A):
        new_A[original_index] = new_index

    # P 배열 구성
    P = [new_A[i] for i in range(N)]

    return P


if __name__ == "__main__":
    import sys

    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))

    result = Solution(N, A)
    print(*result)

[백준] 1015 - 수열 정렬

🖥️ 시작하며

⚙️ 코드

📌 소감

댓글