[백준] 23881번 알고리즘 수업 - 선택 정렬 1 - 파이썬

https://www.acmicpc.net/problem/23881

23881번: 알고리즘 수업 - 선택 정렬 1

풀이:

이 문제에서는 선택정렬을 위쪽에서 시작해서 아래로 내려가는 방식으로 구현하였다. c++과 다르게 내림차순 for문이 익숙하지 않아서 구현하는데 시간이 좀 걸렸다. 그냥 의사코드를 따라서 적기만 하면 되는데 코드를 조금이라도 줄이겠다고 내 맘대로 바꾸니까 되지 않았다. 오답 코드에서 arr[j]가 arr[i]보다 크기만 하면 괜찮을 줄 알았는데 알고보니 [9, 3, 4, 7, 6]과 같은 경우에는 불가능하다는걸 깨달았다... 

 

오답 코드:

n, exchange = map(int, input().split())
arr = list(map(int, input().split()))
index = 0
swap = 0

for i in range(n-1, 0, -1):
    index = i

    for j in range(1, i+1):
        if arr[j] > arr[i]:
            index = j

    if i != index:
        arr[i], arr[index] = arr[index], arr[i]
        swap += 1
        if swap == exchange:
            print(arr[index], arr[i])
            exit()

print(-1)

결국 max값을 찾는 방법으로 코드를 변경하였는데 이번에는 시간초과가 떴다. pypy3로 변경하니 괜찮았는데 구글링을 통해서 함수안에 구현하면 시간초과가 안나온다고 했다.??? stackoverflow를 참고하니 함수내에서 for문을 실행하면 i가 local로 지정되는데 밖에서 for문을 실행하면 i가 global이 되기 때문에 속도가 느려진다고 나와있었다. 허허... 어렵다.

 

https://stackoverflow.com/questions/11241523/why-does-python-code-run-faster-in-a-function

Why does Python code run faster in a function?

 

정답 코드:

import sys

n, exchange = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
swap = 0


def selection(arr):
    global swap
    result = []

    for i in range(n - 1, 0, -1):
        max, index = arr[0], 0

        for j in range(0, i + 1):
            if arr[j] > max:
                max, index = arr[j], j

        if i != index:
            arr[i], arr[index] = arr[index], arr[i]
            swap += 1

            if swap == exchange:
                result.append(arr[index])
                result.append(arr[i])
                return result

    result.append(-1)
    return result


print(*selection(arr))