[백준 10431 / Python / 실버5] 줄세우기

문제

 

구현, 정렬, 시뮬레이션 문제이다. 모든 학생이 각자 물러선 총 횟수를 구해야 한다.

 

import sys

input = sys.stdin.readline

def binary_search(child, arr):

    start = 0

    end = len(arr) - 1

    result = len(arr)

    while start <= end:

        mid = (start + end) // 2

        if arr[mid] > child:

            result = mid

            end = mid - 1

        else:

            start = mid + 1

   

    return len(arr) - result

P = int(input())

for _ in range(P):

    number, *children = map(int, input().split())

    result = 0

    standing = [children[0]]

    for i in range(1, len(children)):

        count = binary_search(children[i], standing)

        result += count

        idx = len(standing) - count

        standing.insert(idx, children[i])

    print(number, result)

 

해결 방법은 문제 내용을 그대로 구현하면 된다.

 

주어진 순서대로 아이들을 줄세우되, 아이가 추가될 때마다 뒤쪽 아이들이 뒷걸음 하는 횟수를 전부 더하면 된다.

이 때, 아이가 어떤 위치에 끼어들어야 하는가? 를 구하기 위해 이분 탐색을 활용했다. binary_search 함수는 뒷걸음 하는 횟수를 리턴하는 함수이다.

 

줄 길이 - 끼어든 인덱스 -> 뒷걸음 하는 아이의 수

줄 길이 - 뒷걸음 하는 아이의 수 -> 끼어든 인덱스

이것을 참고해서 구현하면 되겠다.

 

끼어들 좌표를 구한 후, 실제로 끼어들도록 insert 해주는 작업도 잊어선 안된다.