99클럽 코테 스터디 20일차 TIL - 소트(백준 #1083)

❇️오늘의 학습 키워드 : 소트(백준 #1083)

문제

크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.

입력

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 원소가 차례대로 주어진다. 이 값은 1000000보다 작거나 같은 자연수이다. 마지막 줄에는 S가 주어진다. S는 1000000보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1 

7
10 20 30 40 50 60 70
1

예제 출력 1 

20 10 30 40 50 60 70

예제 입력 2 

5
3 5 1 2 4
2

예제 출력 2 

5 3 2 1 4

예제 입력 3 

10
19 20 17 18 15 16 13 14 11 12
5

예제 출력 3 

20 19 18 17 16 15 14 13 12 11

정답 코드

n = int(input())
arr = list(map(int, input().split()))
s = int(input())

for i in range(n):
    if s <= 0:  # 교환 횟수가 모두 소진되면 종료
        break

    # 현재 위치에서 S 범위 내 가장 큰 값의 인덱스 찾기
    max_idx = i
    for j in range(i + 1, min(i + s + 1, n)):
        if arr[j] > arr[max_idx]:
            max_idx = j

    # 가장 큰 값이 이미 현재 위치라면 스킵
    if max_idx != i:
        # max_idx의 값을 앞으로 이동
        for k in range(max_idx, i, -1):
            arr[k], arr[k - 1] = arr[k - 1], arr[k]
        # 이동 횟수 차감
        s -= (max_idx - i)

print(*arr)

❇️오늘의 회고

  - s == 0이 아니라 s <= 0을 하는 이유는 s가 음수가 됐을 경우 불필요한 연산을 줄이기 위함임!

  - 처음에 문제를 잘못 이해해서 버블정렬을 하려다가 이상하다 싶어 질문게시판을 활용했다...

  - 내일 11시, 문제를 풀기 전에 위 문제를 한번 더 복습하고 내일 문제에 사용된 알고리즘에 대해서 공부할 것이다!🙂