백준 10431. 줄세우기

삽입 정렬 알고리즘을 사용해서 간단하게 풀 수 있는 문제다.

import sys


input = sys.stdin.readline

def insertion_sort(ls: list) -> int:
    cnt = 0
    for idx, val in enumerate(ls[1:]):
        tmp_idx = idx
        while idx >= 0 and val < ls[idx]:
            ls[idx+1] = ls[idx]
            idx -= 1
            cnt += 1
        if idx != tmp_idx:
            ls[idx+1] = val
    return cnt


T = int(input())
for _ in range(T):
    tc, *ls = map(int, input().split())
    print(tc, insertion_sort(ls))
    

삽입 정렬 알고리즘은 The Algorithms 깃허브를 참고했다. 필자가 예쁘다고 생각하는 구현 중 하나이다.