[백준] S5. 줄세우기 (Python)

❓ 문제

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

10431번: 줄세우기

 

 

 

💡 해결하기

1️⃣

테스트 케이스의 개수를 입력을 받아 그 수만큼 반복문을 돌게 하여 출력한다.

그 반복문 안에서도 한줄씩 입력을 받는다.

첫번째 요소는 테스트 케이스 번호에 해당하고, 그 이후 요소들은 학생들의 키에 해당하므로 리스트에 담아준다.

 

2️⃣

주의해야 할 점이, 이미 모든 학생이 줄을 서 있는 상태에서 자리를 바꾸면서 정렬하는 것이 아니다.

빈 공간에 한 명씩 들어가면서 줄을 서야 하는 것이다. 

따라서 줄을 서기 위한 빈 리스트 하나를 만들어 준다.

 

3️⃣

아무나 한명을 뽑아 줄의 맨 앞에 세우라고 하였으므로 키 리스트에서 0번 인덱스에 해당하는 학생의 키부터 줄 리스트에 요소로 추가하여 줄을 세운다.

 

4️⃣

키 리스트에서 인덱스 1번에 해당하는 학생부터 마지막 인덱스에 해당하는 학생의 키를 차례로 탐색한다.

줄 리스트의 가장 마지막 요소는 바로 이전까지 줄을 선 학생들 중 가장 키가 큰 학생의 키이다.

 

➡️ 따라서 줄 리스트의 가장 마지막 요소보다 현재 키가 더 크다면 현재 키는 리스트의 맨 뒤에 추가하기만 하면 된다.

➡️ but 현재 키가 더 작다면 줄 리스트의 요소 하나하나를 탐색하며 처음으로 현재 키보다 커지는 순간을 찾아 그 부분 이상의 학생들은 모두 한 걸음씩 물러나고 현재 키는 그 인덱스 부분에 삽입되면 된다. 이렇게 물러난 걸음 수를 누적한다.

 

이 과정을 통해 줄 리스트는 항상 오름차순의 상태를 유지하게 되고, 이것이 줄 리스트의 가장 마지막 요소가 바로 이전까지 줄을 선 학생들 중 가장 키가 큰 학생의 키가 되는 이유이다.

 

마지막으로 테스트 케이스의 번호와 학생들의 뒤로 물러난 걸음 수를 같이 출력하면 된다.

 

 

 

💻 Python으로 코드 작성하기

 

p = int(input())     # 테스트 케이스의 개수
for _ in range(p):
    row = []     # 학생들을 줄세우기 위한 리스트 (아래의 코드로 인해 항상 오름차순 유지)
    cnt = 0     # 학생들이 물러난 걸음의 수
    info = list(map(int, input().split()))     # 테스트 케이스 번호와 학생들의 키 입력받기
    case_num = info[0]     # 테스트 케이스 번호
    height = info[1:]     # 학생들의 키 리스트

    for h in height:
        if len(row) == 0:     # 줄이 비어 있으면
            row.append(h)      # 그냥 그 학생 추가
        else:     # 줄이 비어 있지 않다면
            if h >= row[-1]:     # 현재 학생의 키가 맨 뒤에 서있는 학생(지금까지 row에서 가장 키가 큰 학생)의 키보다 크거나 같다면
                row.append(h)      # 그냥 맨 뒤에 서고 끝내기 (물러서기 없음.)
            else:      # 현재 학생의 키가 맨 뒤에 서있는 학생보다 작다면
                for i in range(len(row)):
                    if row[i] > h:     # row에 있는 학생들의 키를 0번 인덱스부터 살펴 처음으로 h보다 큰 학생이 나오면
                        cnt += len(row) - i     # i번 자리 학생부터 한 걸음씩 뒤로 물러나고 그 걸음 수를 기록
                        row.insert(i, h)     # 그 자리에 h 삽입
                        break     # 삽입한 이후에는 break로 반복문을 종료해야 한다.
    
    print(case_num, cnt)     # 테스트 케이스 번호와 물러난 걸음 수를 공백을 두고 함께 출력

 

 

 

🙂 돌아보기

문제를 제대로 이해하지 못해 위에 적어놓은 주의할 점을 지키지 못해서 정렬 결과는 올바르게 나오지만 물러선 걸음 수가 틀렸던 문제였다.