[백준] 1083번 : 소트

1083번: 소트

1083번: 소트

🤔 문제분석

골드5치고 어려웠던 문제였다. 문제의 요점은 정렬이 되어있지 않은 수 중에서 S보다 작거나 같게 움직였을때 가장 큰 수를 골라야한다. 가장 큰 수를 골라야함으로 그리디 유형의 문제이다.

배열을 순회하면서 현재 리터레이션에서 멀리있으면서 가장 큰 수를 찾는다.

1. 현재 값에서 가장 멀리있으면서 가장 큰수의 인덱스와 값을 찾는다.
2. 현재 인덱스와 가장 큰 인덱스를 교체한뒤 움직인 만큼 S값을 갱신한다. (S -= (가장큰인덱스 - 현재 인덱스))

💻 코드

import sys
input = sys.stdin.readline

def max_n(index):
    max_value, idx = arr[index], index
    for i in range(index + 1, min(N, index + S + 1)):
        if arr[i] > max_value:
            max_value = arr[i]
            idx = i
    return max_value, idx

N = int(input())
arr = list(map(int, input().split()))
S = int(input())

for i in range(N - 1):
    max_value, idx = max_n(i)
    if idx != i:
        arr.pop(idx)
        arr.insert(i, max_value)
        S -= (idx - i)
        
print(*arr)

🎯 피드백 및 개선사항

다음주에는 그리디 문제의 유형을 풀어보아야겠다. 정렬문제를 풀면서 그리디한 유형이 많이 나왔는데 아직까지도 부족한것 같습니다.