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

구현, 정렬, 시뮬레이션 / 실버 5

👩🏻‍🎓

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

10431번: 줄세우기

 

 

 

내 풀이

P = int(input())

for _ in range(P):
    lst = list(map(int, input().split()))
    T = lst[0]
    height = lst[1:]
    line_up = [height[0]] # 첫 번째 학생 추가
    ans = 0


    for i in range(1, 20):
        if height[i] > max(line_up): # 자기 앞에 자기보다 키가 큰 학생이 없다면
            line_up.append(height[i]) # 맨 뒤에 추가
        else: # 자기 앞에 자기보다 키가 큰 학생이 있다면
            for j in range(len(line_up)):
                if line_up[j] > height[i]: # 그중 가장 앞에 있는 학생의 바로 앞에 선다
                    ans += len(line_up) - j
                    line_up.insert(j, height[i])
                    break
            
    print(T, ans)

 

 

 

코드 설명

 

lst: 테스트 케이스 번호 T와 20개의 양의 정수 리스트

T: 테스트 케이스 번호

height: 20개의 양의 정수(학생 20명의 키) 리스트

line_up: 줄 서기를 완료한 학생의 키를 저장하는 리스트. 첫 번째 학생의 키를 추가하여 초기화하였다.

ans: 정답 변수(학생들이 뒤로 물러난 걸음 수의 총합)

lst = list(map(int, input().split()))
T = lst[0]
height = lst[1:]
line_up = [height[0]] # 첫 번째 학생 추가
ans = 0

 

모든 학생을 검사한다.

 

1. line_up에 현재 학생보다 키가 큰 학생이 없다면, append로 맨 뒤에 추가한다.

2. line_up에 현재 학생보다 키가 큰 학생이 있다면, 그중 가장 앞에 있는 학생의 바로 앞에 선다.

➡ line_up을 순차적으로 검사하면서 현재 학생보다 키가 큰 학생을 발견하면, ans에 학생들이 뒤로 물러나야 하는 걸음수를 더해주고, 해당 인덱스(j)에 현재 학생의 키를 추가해준 후, 즉시 종료한다.

for i in range(1, 20):
    if height[i] > max(line_up): # 자기 앞에 자기보다 키가 큰 학생이 없다면
        line_up.append(height[i]) # 맨 뒤에 추가
    else: # 자기 앞에 자기보다 키가 큰 학생이 있다면
        for j in range(len(line_up)):
            if line_up[j] > height[i]: # 그중 가장 앞에 있는 학생의 바로 앞에 선다
                ans += len(line_up) - j
                line_up.insert(j, height[i])
                break

 

 

 

다른 풀이

P = int(input())

for _ in range(P):
    lst = list(map(int, input().split()))
    ans = 0

    for i in range(1, len(lst)-1):
        for j in range(i+1, len(lst)):
            if lst[i] > lst[j]:
                lst[i], lst[j] = lst[j], lst[i]
                ans += 1

    print(lst[0], ans)

버블 정렬을 이용하면 더 간단하게 해결할 수 있었다!