[백준] 1083 파이썬

문제

---

• 백준 1083 (골드 4)

백준 1083

크기가 n인 배열 a에서 s번 연속된 두 개의 원소를 교환할 때, 그 결과 중 사전순으로 가장 뒷서는 것을 출력하는 문제였다.
시간 제한은 널널한 문제였고, 무엇보다 문제가 깔끔해서 좋았다.

내 코드

---

처음에는 버블 정렬처럼 앞에서부터 두 원소를 비교해 교환하는 방식으로 코드를 작성하였다.
제공하는 테스트 코드는 모두 통과하였지만 제출하니 틀린 것을 확인할 수 있었다.
다른 테스트 케이스들을 확인해보니 최대값이 리스트의 뒤쪽에 위치하는 경우, 이를 앞으로 가져오지 못한다는 것을 알게 되었다.

틀린 코드

input = sys.stdin.readline

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

for i in range(s):
    for j in range(n-1):
        if a[j] < a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
            break

print(*a)

그래서 아예 접근 방식을 바꾸어서 슬라이싱한 리스트의 최대값을 앞쪽으로 가져오는 방식으로 구현해보았다.
남은 s의 값이 충분하다면 전체 리스트에서 최대값을 구하고 target 위치에 이를 삽입해준다.
남은 s의 값이 충분하지 않다면 가능한 길이 만큼 슬라이싱해서 최대값을 구한뒤 target 위치에 삽입한다.
이를 s가 모두 소진되거나 전체 리스트가 정렬될 때까지 반복해준다.

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
s = int(input())
target = 0

while s > 0 and target < n:
    if a[target] == max(a[target:min(target+s+1, n)]):
        target += 1
        continue

    idx = a.index(max(a[target:min(target+s+1, n)]))
    temp = a[idx]
    s -= idx - target
    a.remove(temp)
    a.insert(target, temp)
    target += 1

print(*a)

아마 이게 코딩테스트였다면 테스트 코드를 모두 통과한 첫번째 코드를 제출하였을 수도 있겠다는 생각이 들었다.
논리적으로 아예 잘못된 코드라 해당 문항에서 0점을 받았을 것 같다.
문제를 풀 때 항상 내가 생각한 아이디어의 방향성이 옳은 방향인지 고민해봐야겠다.