[Baekjoon 10431] 줄세우기 | Python

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

---

문제

 

학생들을 줄 세우면서 학생들이 총 몇 번 뒤로 물러나는지 구하는 문제이다.

학생들을 줄 세우는 방법은 주어진 순서대로 오름차순으로 세우는데 학생이 앞이나 중간에 서게되면 그 뒤 사람들은 모두 한 걸음씩 뒤로 물러난다.

 

---

풀이

 

각 학생이 줄을 설 때 경우의 수는 크게 두 가지로 나뉜다. 해당 차례의 학생이 지금까지 나온 학생들 중 가장 커서 맨 뒤에 서게 되는 경우와 그 외 경우이다. 전자의 경우 뒤로 움직여야 하는 학생이 없지만, 후자의 경우 해당 차례의 학생보다 큰 학생들은 모두 뒤로 한 걸음 물러서야 한다.

따라서 학생들이 움직이는 횟수는 해당 차례의 학생보다 큰 학생의 수를 확인하면 간단하게 알 수 있다. 큰 학생의 수를 확인하는 것은 lambda 를 활용하였다.

 

---

코드

 

import sys

test = int(sys.stdin.readline())
for i in range(1, test+1):
    height_list = list(map(int, sys.stdin.readline().rstrip().split()))
    del height_list[0]
    sort_height_list = []
    sorting = 0
    for height in height_list:
        sorting += len(list(filter(lambda x: x > height, sort_height_list)))
        sort_height_list.append(height)
    print(i, sorting)