[Silver V] 줄세우기 - 10431
성능 요약
메모리: 15768 KB, 시간: 148 ms
분류
구현, 시뮬레이션
제출 일자
2023년 12월 11일 10:43:22
문제 설명
초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.
하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.
우선 아무나 한 명을 뽑아 줄의 맨 앞에 세운다. 그리고 그 다음부터는 학생이 한 명씩 줄의 맨 뒤에 서면서 다음 과정을 거친다.
- 자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다.
- 자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다.
이 과정을 반복하면 결국 오름차순으로 줄을 설 수가 있다.
아이들의 키가 주어지고, 어떤 순서로 아이들이 줄서기를 할 지 주어진다. 위의 방법을 마지막 학생까지 시행하여 줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?
입력
첫 줄에 테스트 케이스의 수 P (1 ≤ P ≤ 1000) 가 주어진다.
각 테스트 케이스는 테스트 케이스 번호 T와 20개의 양의 정수가 공백으로 구분되어 주어진다.
20개의 정수는 줄서기를 할 아이들의 키를 줄서기 차례의 순서대로 밀리미터 단위로 나타낸 것이다.
모든 테스트 케이스는 독립적이다.
출력
각각의 테스트 케이스에 대해 테스트 케이스의 번호와 학생들이 뒤로 물러난 걸음 수의 총합을 공백으로 구분하여 출력한다.
풀이방법
1. 본인보다 키가 큰 학생의 수를 세어서 더해주면된다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringBuilder sb = new StringBuilder();
for(int tc = 1; tc <= T; tc++){
int count = 0;
StringTokenizer st = new StringTokenizer(br.readLine());
st.nextToken();
int[] students = new int[20];
for(int i = 0; i < 20; i++){
students[i] = Integer.parseInt(st.nextToken());
}
for(int i = 1; i< 20; i++){
for(int j = i -1; j >= 0; j--){
if(students[i] < students[j]){
count++;
}
}
}
sb.append(tc + " ").append(count).append("\n");
}
System.out.println(sb.toString());
}
}
'알고리즘 - Baekjoon > Silver' 카테고리의 다른 글
[백준] 2630번 : 색종이 만들기 Silver2(실버2) - JAVA[자바] (0) | 2023.12.12 |
---|---|
[백준] 14940번 : 쉬운 최단거리 Silver1(실버1) - JAVA[자바] (0) | 2023.12.12 |
[백준] 2331번 : 반복수열 Silver4(실버 4) - JAVA[자바] (1) | 2023.12.10 |
[백준] 4963번 : 섬의 개수 Silver2(실버 2) - JAVA[자바] (0) | 2023.12.10 |
[백준] 10451번 : 순열 사이클 Silver 3(실버 3) - JAVA[자바] (1) | 2023.12.10 |