HackerRank Minimum Swaps 2

list의 원소를 최소한 몇번 swap해야 정렬되는지 판단하는 문제다
처음 원소부터 제자리를 찾아 swap해야하는데 swap 당한(?) 원소가 제자리를 못찾으면 그 원소를 다시 제자리를 찾도록 swap해주면 된다.

처음엔 문제를 너무 어렵게 생각해서 swap을 했는지 안했는지를 판단하는 swap_list를 만들었고 arr과 동기화를 해줘야 해서 timeout이 났던 것 같다

단순하게 생각하는 연습을 해야겠다

#!/bin/python3

import math
import os
import random
import re
import sys
import copy

# Complete the minimumSwaps function below.
def minimumSwaps(arr):
    swap_count = 0
    
    for i, v in enumerate(arr):
        while v != i + 1:
            tmp = arr[v-1]
            arr[i], arr[v-1] = arr[v-1], arr[i]
            v = tmp
            
            swap_count += 1
            
    return swap_count
    
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    n = int(input())

    arr = list(map(int, input().rstrip().split()))

    res = minimumSwaps(arr)

    fptr.write(str(res) + '\n')

    fptr.close()

좋은 웹페이지 즐겨찾기