[Python] 백준 10431 줄세우기

 

문제 분석

• 키 순서로 번호를 부여
• 반 아이들은 항상 20명
• 같은 키 x
• 아무 한 명을 맨 앞에 세우고, 그 다음부터는 한 명씩 맨 뒤에 서면서 다음 과정을 거친다.
• 자기 앞에 자기보다 큰 학생이 없다면 그 자리에 서고 끝
• 자기 앞에 본인보다 큰 학생이 존재 한다면 그 중 가장 앞에 있는 학생 바로 앞에 선다.

 

정답 코드

1차 - 실패..

import sys
input = sys.stdin.readline

p = int(input())
stu = []
for _ in range(p):
    stu.append(list(map(int, input().split())))

for i in range(p):
    before = stu[i]
    tc = before[0]
    students = before[2:]
    after = sorted(before[1:])

    line = []
    line.append(before[1])
    # after = sorted(students)
    cnt = 0

    while (line != after) :
        now = students[0]
        del students[0]
        highest = line[-1]
        if line[-1] < now : # 앞에 키 큰 학생 x
            line.append(now)
        else :
            # 나보다 작은 사람들을 찾고
            for j in range(len(line)):
                # 이미 서 있는 줄 중에서 나보다 큰 사람이 있음
                # 그러면 나는 그 사람보다 앞에 서야함
                # 재배열
                if line[j] > now :
                    # 리스트에서 어떻게 뒤로 미루지?
                    # 뒤에 다 빼고 넣고 이어 붙이기
                    tmp = line[j:]
                    del line[j:]
                    line.append(now)
                    line += tmp
                    cnt += 1
                    break
                else :
                    continue
    print(f"{i+1} {cnt}")

 

다른 사람 코드 1

• 모든 아이들을 순회하면서 현재 아이 뒤에 선 아이 중 현재 아이보다 작은 키가 있다면 바꿔준다.
• (버블 정렬)

import sys
input = sys.stdin.readline

p = int(input())
for _ in range(p) :
    arr = list(map(int, input().split()))
    cnt = 0

    for i in range(len(arr)-1) :
        for j in range(i+1, len(arr)) : # i의 뒤에 있는 애들과 비교
            if arr[i] > arr[j] :
                arr[i], arr[j] = arr[j], arr[i]
                cnt += 1
    print(arr[0], cnt)