서론
난이도
실버 5
문제
구현 문제입니다.
처음 입력 받은 리스트를 자르지 않고 (1, 21)의 범위를 탐색하니 틀렸습니다가 나오다가
첫 번째를 자르고 (0, 20)의 범위를 탐색하니 통과했네요..
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 256 MB |
초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.
하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.
우선 아무나 한 명을 뽑아 줄의 맨 앞에 세운다. 그리고 그 다음부터는 학생이 한 명씩 줄의 맨 뒤에 서면서 다음 과정을 거친다.
자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다.
자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다.
이 과정을 반복하면 결국 오름차순으로 줄을 설 수가 있다.
아이들의 키가 주어지고, 어떤 순서로 아이들이 줄서기를 할 지 주어진다. 위의 방법을 마지막 학생까지 시행하여 줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?
입력
첫 줄에 테스트 케이스의 수 P (1 ≤ P ≤ 1000) 가 주어진다.
각 테스트 케이스는 테스트 케이스 번호 T와 20개의 양의 정수가 공백으로 구분되어 주어진다.
20개의 정수는 줄서기를 할 아이들의 키를 줄서기 차례의 순서대로 밀리미터 단위로 나타낸 것이다.
모든 테스트 케이스는 독립적이다.
출력
각각의 테스트 케이스에 대해 테스트 케이스의 번호와 학생들이 뒤로 물러난 걸음 수의 총합을 공백으로 구분하여 출력한다.
예시
예제 입력 1
4
1 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919
2 919 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900
3 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 900
4 918 917 916 915 914 913 912 911 910 909 908 907 906 905 904 903 902 901 900 919예제 출력 1
1 0
2 190
3 19
4 171풀이
풀이 과정은 단순합니다. 첫 번째 학생부터 마지막 학생까지 순차적으로 탐색하며,
현재 학생(s[i])보다 큰 키를 가진 학생(s[j])이 앞에 있을 시 그 학생의 자리(j)로 인덱스를 이동시키고,
원래 있던 인덱스와 바꾼 자리의 인덱스의 차(i - j)가 곧 움직여야 하는 학생들 수이기에 총 움직인 수(ans)에 더해주면 됩니다.
코드
import sys
input = sys.stdin.readline
for t in range(int(input())):
s = list(map(int, input().split()))[1:] # 첫 요소를 제외하고 리스트 생성
ans = 0 # 총 움직인 수
for i in range(20): # 첫 번째부터 마지막 학생까지 탐색
for j in range(i): # 현재 학생의 앞까지만 탐색
if s[j] > s[i]: # 현재 학생의 키보다 큰 학생이 있다면
tmp = s[i] # 현재 학생의 값 저장
s.remove(tmp) # 현재 학생 제거
s.insert(j, tmp) # 큰 키의 학생 위치에 섬
ans += i - j # 사이에 있는 학생들 움직임
break # 가장 앞에 있는 학생이기에 다음 학생으로 이동
print(t + 1, ans)실행 결과
