[Python] 10431. 줄세우기

문제

초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.

하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.

우선 아무나 한 명을 뽑아 줄의 맨 앞에 세운다. 그리고 그 다음부터는 학생이 한 명씩 줄의 맨 뒤에 서면서 다음 과정을 거친다.

• 자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다.
• 자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다.

이 과정을 반복하면 결국 오름차순으로 줄을 설 수가 있다.

아이들의 키가 주어지고, 어떤 순서로 아이들이 줄서기를 할 지 주어진다. 위의 방법을 마지막 학생까지 시행하여 줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?

풀이

반복문을 사용해 한 번에 한 줄씩 받아 배열에 저장한 뒤, 그 원소를 하나씩 순차적으로 꺼내어 새로운 빈 배열에 삽입하며 발생하는 뒤로가기 횟수를 누적합으로 구하는 방법을 구상했다. 이때 for문의 제어 변수를 활용한 이중 for문으로 현재까지 삽입된 원소들 중 지금 삽입하려는 값보다 큰 값을 찾고, 파이썬 내장 함수를 사용해서 특정 인덱스 삽입+뒤 원소들은 자동으로 한 칸씩 뒤로 밀리기를 구현하였다. 뒤로가기 횟수는 수식으로 계산하였다.

첫 번째 코드

import sys

input = sys.stdin.readline
n = int(input())
arr = []
for p in range(n):
    arr.clear()
    cnt = 0
    lst = list(map(int, input().split()))
    for i in range(20):
        insert = 0
        if i == 0:
            arr.append(lst[i + 1])  # 첫번째 원소면 무조건 맨 앞에 넣기
            continue
        for j in range(i):
            if arr[j] > lst[i + 1]:  # 나보다 키가 큰 맨 앞 학생 발견
                cnt += i - j  # 움직인 걸음 수
                arr.insert(j, lst[i + 1])  # 삽입
                insert = 1
                break
        if insert == 0:
            arr.append(lst[i + 1])
    print(p + 1, cnt)

 

원하던 대로 동작은 하지만 아직 파이썬의 내장 함수와 로직 구현에 익숙하지 않아서 가독성이 많이 떨어진다.

그래서 몇 가지를 수정하였다.

 

1. 배열 arr을 상단에 선언한 후 for문 내에서 매번 arr.clear() 호출

: 아예 for문 내에서 매번 새로운 배열을 할당하도록 수정하였다.

 

2. lst[i+1]을 사용하여 lst[0](테스트 케이스 넘버) 이후부터 접근

: 리스트 슬라이싱을 활용하여 for문 자체를 lst[1:]에 대하여 동작하도록 수정하였다.

 

3. for문 내에서 삽입이 이루어졌는지 확인하기 위해 index 변수 사용

: for-else문을 사용하여 index 변수와 if i=0문을 제거하였다.

(첫 번째 원소일 때와 for문에서 삽입이 안 되었을 경우를 통합)

 

최종 코드

import sys

input = sys.stdin.readline
n = int(input())
for p in range(n):
    arr = []
    cnt = 0
    lst = list(map(int, input().split()))
    for s in lst[1:]:
        for j in range(len(arr)):
            if arr[j] > s:  # 나보다 키가 큰 맨 앞 학생 발견
                cnt += len(arr) - j  # 움직인 걸음 수
                arr.insert(j, s)  # 삽입
                break
        else:  # break문 1번도 안 걸렸을 때
            arr.append(s)
    print(p + 1, cnt)

 

첫 번째 코드보다 가독성도 좋아지고 최적화되었다!

물론 이보다 더 효율적이고 좋은 알고리즘도 많겠지만 일단 내가 구현하고자 한 알고리즘을 최적화해서 구현한 데에 만족한다.

 

배운 것

• for-else문: for문이 내부 break문에 의하여 종료되지 않았을 경우 else문에 도달한다.
• arr.insert(idx, value) : arr[idx] 위치에 value 값을 삽입한다. 이때 index의 기존 값 포함 이후 값들은 자동으로 뒤로 한 칸씩 밀려난다.
• arr.append(value) : 배열 arr의 맨 뒤에 value 값을 삽입한다.
• list(map(int, input().split())): map을 사용하여 생성한 배열의 개별 인덱스에 바로바로 접근하기 위해선 제일 바깥을 list()로 감싸줘야 한다. 처음에 그걸 몰라서 오류남...