[Python] 백준 10431번 - 줄세우기

문제

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

 

---

해당 문제는 삽입 정렬(insertion sort)이 이루어 질 때 shifting 횟수를 구하는 문제임.

 

표준입력을 위해 sys모듈 추가.

입력을 표준입력으로 대체.

테스트 케이스 수 입력.

import sys


input = sys.stdin.readline
t = int(input())

 

테스트 케이스 수 만큼 반복.

- 입력받은 정수들을 리스트에 저장.

- 맨 앞 요소를 n에 저장.

- 맨 앞 요소를 제외한 나머지를 리스트에 저장.

- 횟수를 세기 위한 변수 생성(0으로 초기화).

for _ in range(t):
    arr = list(map(int, input().split()))
    n = arr[0]
    arr = arr[1:]
    count = 0

 

1번째 요소부터 19번째 요소까지를 삽입정렬 해야하므로 반복.

- 반복문을 이용하여 삽입할 위치 찾기.

- 삽입할 위치를 찾은 뒤 해당 번째부터 삽입할 위치까지 right shifting.

=> shifting할 때마다 횟수 증가.

- n과 횟수 출력.

for i in range(1, 20):
    idx = i
    for j in range(i):
        if arr[j] > arr[i]:
            idx = j
            break
    if idx != i:
        temp = arr[i]
        for j in range(i, idx, -1):
            arr[j] = arr[j-1]
            count += 1
        arr[idx] = temp
print(n, count)

 

전체 코드.

import sys


input = sys.stdin.readline
t = int(input())
for _ in range(t):
    arr = list(map(int, input().split()))
    n = arr[0]
    arr = arr[1:]
    count = 0
    for i in range(1, 20):
        idx = i
        for j in range(i):
            if arr[j] > arr[i]:
                idx = j
                break
        if idx != i:
            temp = arr[i]
            for j in range(i, idx, -1):
                arr[j] = arr[j-1]
                count += 1
            arr[idx] = temp
    print(n, count)