[백준/자바] 10431 줄세우기
📌 문제
초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1번, 그 다음이 2번, ... , 가장 큰 아이가 20번이 된다. 강산이네 반 아이들은 항상 20명이며, 다행히도 같은 키를 가진 학생은 한 명도 없어서 시간이 조금 지나면 아이들은 자기들의 번호를 인지하고 한 줄로 세우면 제대로 된 위치에 잘 서게 된다.
하지만 매년 첫 며칠간 강산이와 강산이네 반 아이들은 자기가 키 순으로 몇 번째인지 잘 알지 못해 아주 혼란스럽다. 자기 위치를 찾지 못하는 아이들을 위해 강산이는 특별한 방법을 생각해냈다.
우선 아무나 한 명을 뽑아 줄의 맨 앞에 세운다. 그리고 그 다음부터는 학생이 한 명씩 줄의 맨 뒤에 서면서 다음 과정을 거친다.
자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다.자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다.
이 과정을 반복하면 결국 오름차순으로 줄을 설 수가 있다.
아이들의 키가 주어지고, 어떤 순서로 아이들이 줄서기를 할 지 주어진다. 위의 방법을 마지막 학생까지 시행하여 줄서기가 끝났을 때 학생들이 총 몇 번 뒤로 물러서게 될까?
⚔ 입력
첫 줄에 테스트 케이스의 수 P (1 ≤ P ≤ 1000) 가 주어진다.
각 테스트 케이스는 테스트 케이스 번호 T와 20개의 양의 정수가 공백으로 구분되어 주어진다.
20개의 정수는 줄서기를 할 아이들의 키를 줄서기 차례의 순서대로 밀리미터 단위로 나타낸 것이다.
모든 테스트 케이스는 독립적이다.
📣 출력
각각의 테스트 케이스에 대해 테스트 케이스의 번호와 학생들이 뒤로 물러난 걸음 수의 총합을 공백으로 구분하여 출력한다.
💡 코드 구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
private static final BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
public static void main(String[] args) throws IOException {
int testCases = Integer.parseInt(bufferedReader.readLine());
while (testCases-->0){
int[] students = new int[20];
StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
int testCaseNo = Integer.parseInt(st.nextToken());
students[0] = Integer.parseInt(st.nextToken());
int stepBackCount =0;
for (int i =1; i< 20; i++){
int student = Integer.parseInt(st.nextToken());
students[i] =student;
stepBackCount = compare(student, students, i - 1, stepBackCount);
}
// System.out.println("students = " + Arrays.toString(students));
System.out.println(testCaseNo + " " + stepBackCount);
}
}
private static int compare(int student, int[] students, int idx, int stepBackCount){
if (idx <0){
return stepBackCount;
}
if(student < students[idx]){
students[idx+1] =students[idx];
students[idx] = student;
stepBackCount++;
}
return compare(student, students, idx-1, stepBackCount);
}
}
문제에서 요구하는 것을 그대로 구현해주면 된다.
일반적인 정렬과 다른 점은 배열을 다 받은다음에 정렬을 해서는 안되고 받으면서 비교를 해주어야 요구조건에 맞다는 것이다.
특이한 점은 이 부분 반복문에서 재귀 함수 compare()를 호출해 주기 전에 배열 초기화를 해주어야 빈 공간이 생기지 않고 전부 담을 수 있다는 것.
for (int i =1; i< 20; i++){
int student = Integer.parseInt(st.nextToken());
students[i] =student;
stepBackCount = compare(student, students, i - 1, stepBackCount);
}
한편, 이처럼 구현한 코드의 시간 복잡도는 다음과 같다.
입력 처리: testCases 변수에 한 번에 입력되므로 시간 복잡도는 O(1)이다.
테스트 케이스 반복문: testCases 변수의 값에 따라 반복하므로 이 반복문의 시간 복잡도는 O(testCases)이다. 문제에서 P 값의 최대 범위는 1000이다.
내부 반복문: for (int i =1; i< 20; i++) 구문은 항상 20번 반복한다. 따라서 이 반복문의 시간 복잡도는 O(1)이다.
compare 재귀함수: 반복문 내부에서는 compare 메서드를 호출하고, compare 메서드의 시간 복잡도는 재귀 호출을 사용하여 O(N)이다. 점화식은 다음과 같다.
재귀 함수 compare의 호출 횟수를 T(n)이라고 할 때, 두 가지 경우를 따진다.
idx < 0인 경우, 재귀 호출을 멈추고 stepBackCount를 반환하므로 재귀 함수가 호출되지 않아 시간 복잡도에 영향을 주지 않는다.
idx >= 0인 경우, 재귀 함수가 호출되면서 idx를 1씩 감소시킨다. 따라서 재귀 함수 compare의 호출 횟수는 n에 대해 T(n) = T(n-1) + 1로 표현할 수 있다. 이를 폐쇄형으로 변환하기 위해 n을 n+1로 바꾸고 T(n)을 T(n+1)로 대체하면 점화식은 T(n+1) = T(n) + 1이 되고, 이를 풀면 최종 폐쇄형은 T(n) = T(0) + n으로 시간 복잡도는 O(n)이다.
따라서 이 코드의 전체 시간 복잡도는 O(testCases * N)이다. testCases의 값이 최대 1000이므로 선형 시간 복잡도를 가지며 문제 풀이에 충분한 시간을 가진다.
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준/자바] 3273 두수의 합 (0) | 2023.06.08 |
---|---|
[백준/자바] 10989 수 정렬하기 3 (삽입 정렬, 합병 정렬, 힙정렬, 계수 정렬) (0) | 2023.06.08 |
[백준/자바] 10158 개미 (0) | 2023.06.07 |
백준 1543 문서 검색 자바 풀이 (0) | 2023.06.06 |
백준 11365 !밀비 급일 (자바 & 파이썬 풀이) (0) | 2023.01.19 |