[Java] Baekjoon Online Judge 10431: 줄세우기

10431번: 줄세우기

💡문제

---

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

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

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

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

 

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

 

✏️입력

---

첫 줄에 테스트 케이스의 수 P (1 ≤ P ≤ 1000) 가 주어진다.

각 테스트 케이스는 테스트 케이스 번호 T와 20개의 양의 정수가 공백으로 구분되어 주어진다.

20개의 정수는 줄서기를 할 아이들의 키를 줄서기 차례의 순서대로 밀리미터 단위로 나타낸 것이다.

모든 테스트 케이스는 독립적이다.

 

📑출력

---

각각의 테스트 케이스에 대해 테스트 케이스의 번호와 학생들이 뒤로 물러난 걸음 수의 총합을 공백으로 구분하여 출력한다.

 

⏳제한

---

• 시간 제한 1초
• 메모리 제한 256MB

 

예제입력 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

 

🔎알고리즘 분류

---

• 구현
• 시뮬레이션

 

📌풀이

---

코드 1

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int P = scanner.nextInt(); // 테스트 케이스의 개수

        // 후위 감소 연산자(--)를 사용하여 P의 값을 1씩 감소시키면서, 감소된 값이 0보다 큰 동안에만 반복
        while (P-- > 0) {
            int T = scanner.nextInt(); // 테스트 케이스 번호
            int[] heights = new int[20]; // 학생들의 키
            for (int i = 0; i < 20; i++) {
                heights[i] = scanner.nextInt();
            }

            int totalSteps = 0; // 뒤로 물러난 걸음 수
            for (int i = 1; i < 20; i++) {
                for (int j = 0; j < i; j++) {
                    if (heights[j] > heights[i]) {
                        totalSteps++;
                    }
                }
            }

            System.out.println(T + " " + totalSteps);
        }

        scanner.close();
    }
}

주어진 조건에 따라 학생들이 뒤로 물러나는 걸음 수를 계산한다.
P만큼의 테스트 케이스가 입력으로 주어지고, 각 테스트 케이스마다 학생들의 키가 배열로 주어지게 된다.
이에 대한 뒤로 물러난 걸음 수를 계산하여 출력하는 문제이다.

 

프로그램 동작

1. 테스트 케이스의 개수 P를 입력 받는다.
2. P번 반복하면서 각 테스트 케이스를 처리한다.
3. 각 테스트 케이스에서 학생들의 키를 배열에 저장한다.
4. 중첩된 반복문을 사용하여 각 학생에 대해 자기 앞에 자기보다 키가 큰 학생이 있는지 확인하고, 있다면 그 학생의 앞에 서면서 뒤로 물러나는 걸음 수를 증가시킨다.
5.각 테스트 케이스마다 결과를 출력한다.

 

후위 감소 연산자

후위 감소 연산자는 변수의 값을 1 감소시킨 후에 현재 값을 반환하는 연산자이다.

자바에서는 -- 기호로 표현되며, 피연산자 뒤에 위치한다.

후위 감소 연산자를 변수 뒤에 사용하면 해당 변수의 값을 먼저 사용하고 난 후에 1을 감소시킨다.

int x = 5;
int y = x--;
System.out.println("x: " + x); // 출력 결과: x: 4
System.out.println("y: " + y); // 출력 결과: y: 5

위 코드에서 x--는 후위 감소 연산자로, x의 현재 값인 5를 y에 할당한 후에 x의 값을 1만큼 감소시킨다. 따라서 x는 4가 되고, y는 할당 시점의 x의 값인 5가 된다.
후위 감소 연산자는 다양한 상황에서 사용될 수 있으며, 주로 반복문에서 변수를 감소시키면서 사용되어 코드의 가독성을 높이는 데 도움을 줄 수 있다.

 

[Java] 연산자 7가지: 산술, 비교, 논리, 대입, 증감, 조건, 비트

자바의 연산자에 대해서는 위 글을 참고한다.