📌 문제
외과의사 머쓱이는 응급실에 온 환자의 응급도를 기준으로 진료 순서를 정하려고 합니다. 정수 배열 emergency가 매개변수로 주어질 때 응급도가 높은 순서대로 진료 순서를 정한 배열을 return하도록 solution 함수를 완성해주세요.
⚔ 제한 사항
중복된 원소는 없습니다.
1 ≤ emergency의 길이 ≤ 10
1 ≤ emergency의 원소 ≤ 100
👀 문제 해석
이 문제에서는 환자들의 응급 상황을 나타내는 정수 배열 emergency가 주어진다. 배열에서 주어지는 숫자를 기준으로, 응급도가 높은 순서대로 환자들에게 진료 순서를 부여해야 한다. 여기서 각 숫자는 응급도를 의미한다.
정렬 알고리즘이 사용되는 문제라고 볼 수 있다. 주어진 배열을 정렬하되, 원래 배열의 순서에 대한 정보도 유지해야 하기 때문에 단순한 정렬보다는 조금 더 복잡한 접근이 필요하다. 주어진 숫자를 기반으로 응급도, 즉 순서를 판단하고, 이를 기반으로 재정렬된 배열을 리턴하는 것이 과제이다.
문제의 제한사항을 보면, 응급도를 나타내는 숫자들은 중복되지 않고, 배열의 크기는 최대 10으로 매우 작다. 프로그래머 코딩테스트 난이도에서 입문이라 그런지 제약 사항이 사실상 없는 수준이나 마찬가지이므로 시간 복잡도에 크게 신경 쓰지 않아도 해결하는 데 무리는 없다.
🔎 접근
우선 문제의 본질을 이해해보자. '진료 순서를 정한다'는 요구는 사실상 '우선 순위를 매긴다'는 것과 동일하다. 그러나 이번에는 단순히 정렬된 결과를 반환하는 것이 아니라, 각 원소가 최초 배열에서 어느 위치에 있었는지에 따라 그 우선 순위를 매기는 것이 핵심이다.
여기서 문제의 크기가 매우 작기 때문에(배열의 길이가 최대 10), 사실상 직관적인 방법으로 접근해도 된다. 즉 배열의 각 원소를 직접 비교하여 순위를 매길 수 있는 방법을 생각해 볼 수 있다. 이 방법은 각 원소를 다른 모든 원소와 비교하여, 자신보다 큰 원소의 개수를 세는 것이다. 이 개수가 곧 그 원소의 우선 순위가 된다. 이 방법의 장점은 별도의 자료구조나 알고리즘이 필요 없지만 시간 복잡도가 n^2으로 좋지는 않다. 그렇다면 다른 접근도 가능할까?
정렬을 이용하는 방법이 있다. 비교기반 정렬의 하한이 nlogn이기 때문에 시간복잡도를 낮출 수 있지 않을까? 한 번 살펴보도록 하자.
💡 풀이 코드
1. 브루트 포스 - 직접 순위 비교하기 방식
먼저 첫 번째 방식의 풀이이다.
배열의 각 원소를 모든 다른 원소와 비교하여, 주어진 원소보다 큰 원소의 수를 세어 해당 원소의 순위를 결정한다. n개의 원소에 대해서 반복문을 돌면서, 내부 반복문(for (int j = 0; j < n; j++))을 통해 자신을 제외한 원소들을 비교하는데, 현재 요소(emergency[i])와 배열의 다른 모든 요소(emergency[j])를 비교하여 현재 요소보다 큰 요소의 수를 센다. 이때, if 조건문을 사용하여 만약 emergency[i]가 emergency[j]보다 작다면, count 변수가 증가시킨다.
class Solution {
public int[] solution(int[] emergency) {
int n = emergency.length;
int[] result = new int[n];
for (int i = 0; i < n; i++) {
int count = 0;
for (int j = 0; j < n; j++) {
if (emergency[i] < emergency[j]) {
count++;
}
}
result[i] = count + 1; // 현재 값의 순위를 저장
}
return result;
}
}
각 요소에 대해, 비교가 완료되면 count에 1을 더해 해당 요소의 순위를 최종 결정한다. 1을 더하는 이유는 순위가 1 base이기 때문이다. 즉 자기보다 큰 값이 1개 있으면 나의 순위는 2순위이다. 이를 배열 result에 저장한다. 모든 반복이 끝난 후 result를 리턴하면 정답이 된다.
예를 들어 {30, 10, 23, 6, 100}이 주어질 때 배열 내부가 어떻게 초기화되는지 살펴보자.
먼저 초기화 시점에서 배열은 다음과 같이 초기화될 것이다.
반복문이 1번 돌면 어떨까? 즉 i가 0일때이다. 30 입장에서 다른 값들과 비교한다. 이때 30보다 큰 값은 100 밖에 없으므로 emergency[i] < emergency[j]가 true인 경우는 1번 밖에 없다. 따라서 count 값은 1회 올라가므로 count = 1 + 1 = 2가 된다. 이를 살펴보면 다음과 같다.
i가 1일 때는 이제 10과 다른 요소들이 비교 대상이 된다. 10보다 큰 값들은 총 3개이다. 그러므로 10은 4위이다. 따라서 result 배열의 1번 인덱스가 4로 초기화되어야 한다.
이와 같은 방식으로 i = 4까지 모두 마치면 배열의 값은 [2, 4, 3, 5, 1]이 되고, 곧 정답이므로 이를 리턴한다.
이 방법은 브루트 포스 접근 방식으로 모든 가능한 원소 쌍을 비교하는 것이다. 각 원소의 순위를 직접 계산할 수 있고, 추가적인 메모리 사용 없이 입력 배열과 동일한 크기의 결과 배열만을 필요로 하다는 게 장점이다. 단, 배열의 크기가 상대적으로 작고 시간 제한이 없기 때문에 수용가능한 점을 고려해야 한다!
2. 정렬 사용 1 - 정렬과 인덱스 배열 사용하기
이제 정렬을 사용해서 문제를 풀어보자. 정렬을 사용한 첫 번째 접근은 정렬과 인덱스 배열을 함께 활용하는 것이다.
이번에는 원소의 값을 기준으로 우선 순위를 정하는 것이 아니라, 각 원소의 원래 위치와 값을 동시에 고려하여 처리해보자. 이를 위해 각 원소와 그 인덱스를 쌍으로 하는 배열을 생성한다. 이 배열을 응급도 값에 따라 내림차순으로 정렬하게 되면, 가장 응급도가 높은 원소부터 낮은 순으로 배열이 재구성된다.
int[][] indexedEmergency = new int[emergency.length][2];
for (int i = 0; i < emergency.length; i++) {
indexedEmergency[i][0] = emergency[i]; // 응급도 값
indexedEmergency[i][1] = i; // 원래 인덱스
}
// 응급도 값에 따라 내림차순 정렬
Arrays.sort(indexedEmergency, (a, b) -> Integer.compare(b[0], a[0]));
마찬가지로 {30, 10, 23, 6, 100}을 예시로 살펴보자.
정렬 전
정렬 후
이와 같이 응급도 순서대로 정렬된 것을 볼 수 있다. 이 배열의 각 요소는 원래 배열의 응급도 값과 그 위치 인덱스를 포함한다. 정렬된 배열을 이제 어떻게 해야 할까? 사실상 정렬이 모두 완료되었기 때문에 이제는 결과 배열을 만들고 이 정렬된 배열을 활용해 순위를 결과로서 만들어주기만 하면 되지 않을까?
코드는 다음과 같다.
// 정렬된 배열을 순회하면서 순위 할당
for (int rank = 0; rank < indexedEmergency.length; rank++) {
int originalIndex = indexedEmergency[rank][1];
result[originalIndex] = rank + 1; // 순위는 1부터 시작
}
정렬된 indexedEmergency 배열을 순회하면서, 각 원소의 원래 인덱스 위치에 순위를 저장한다. 반복문의 i는 순위이다. 이때 0번째부터 순회하되, 실제는 1부터 시작하도록 +1을 한다.
예를 들어보자.
정렬된 indexedEmergency 배열은 다음과 같다.
- [[100, 4], [30, 0], [23, 2], [10, 1], [6, 3]]
여기서 각 배열의 두 번째 요소는 원래 emergency 배열에서의 인덱스를 나타내므로, 순위를 의미하는 반복문이 순회할 때 1회 반복의 rank는 곧 1순위를 의미할 것이다. 이때 이미 정렬된 배열에서의 첫 번째 인덱스가 정렬에서의 의미에 따라, 1순위를 의미하므로, 해당 요소의 원래 인덱스가 1순위임을 의미하는 것이다.
전체 순회 과정에서의 데이터 흐름을 보면,
indexedEmergency[0]의 원래 인덱스는 4, 따라서result[4] = 1
다른 과정도 동일하다.
indexedEmergency[1]의 원래 인덱스는 0, 따라서result[0] = 2indexedEmergency[2]의 원래 인덱스는 2, 따라서result[2] = 3indexedEmergency[3]의 원래 인덱스는 1, 따라서result[1] = 4indexedEmergency[4]의 원래 인덱스는 3, 따라서result[3] = 5
이렇게 순위가 할당된 result 배열은 다음과 같이 최종적으로 [2, 4, 3, 5, 1]의 형태를 가지게 된다. 이 배열은 각 환자의 응급도에 따른 진료 순서를 나타내므로 리턴하면 정답이 된다.
import java.util.Arrays;
public class Solution {
public int[] solution(int[] emergency) {
// 인덱스와 값을 쌍으로 하는 배열 생성
int[][] indexedEmergency = new int[emergency.length][2];
for (int i = 0; i < emergency.length; i++) {
indexedEmergency[i][0] = emergency[i]; // 응급도 값
indexedEmergency[i][1] = i; // 원래 인덱스
}
// 응급도 값에 따라 내림차순 정렬
Arrays.sort(indexedEmergency, (a, b) -> Integer.compare(b[0], a[0]));
// 결과 배열
int[] result = new int[emergency.length];
// 정렬된 배열을 순회하면서 순위 할당
for (int rank = 0; rank < indexedEmergency.length; rank++) {
int originalIndex = indexedEmergency[rank][1];
result[originalIndex] = rank + 1; // 순위는 1부터 시작
}
return result;
}
}
이 방식의 핵심은 정렬 과정에서 각 원소의 원래 인덱스를 유지하고 있다는 점이다. 따라서 원본 배열의 순서를 변경하지 않고도 즉 원래 배열을 수정하지 않으면서도, 각 원소의 정확한 순위를 파악할 수 있다는 장점이 있다.
3. 정렬 사용 2 - 우선순위 큐 사용
이번에는 우선순위 큐를 활용한 정렬 방법을 살펴보자.
우선순위 큐는 추상 자료형 중 하나로, 각 요소가 우선순위에 따라 처리된다. 각 요소가 우선순위를 가지고 있으며, 이를 기반으로 최소값 또는 최대값을 먼저 추출할 수 있는 게 특징이다. 자바에서는 PriorityQueue 클래스를 통해 이 구조를 구현하며, 내부적으로는 힙(Heap)을 사용하여 요소들을 정렬한다. 힙은 완전 이진 트리의 일종으로, 각 노드가 하위 노드보다 작거나 같은(최소 힙) 또는 크거나 같은(최대 힙) 순서를 유지하는 자료구조이다. 또 하나의 특징은 삽입과 삭제가 O(log n)의 시간 복잡도로 처리된다는 점이다.
자바에 구현된 PriorityQueue를 사용해서 응급도가 높은 순서대로 환자를 진료 순서에 따라 정렬해보자.
- 우선순위 큐 초기화:
Collections.reverseOrder()를 사용하여 내림차순 우선순위 큐를 생성한다. 이렇게 함으로써 가장 큰 값이 가장 먼저 나오게 된다.
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int value : emergency) {
pq.add(value);
}
우선순위 큐에 저장된 값들이 정말로 내림차순으로 되어 있을까? Java 에서 제공하는 기능이므로 보장받을 수 있겠지만, 그래도 확인해볼 수 있다.
// pq에 정렬이 되었는지 확인을 위해 출력하는 코드
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
이제 우선순위 큐에 저장된 값들을 하나씩 꺼내면서 해당 값이 원본 배열 emergency에서 몇 번째 위치에 있는지 찾는다. 그리고 그 위치에 순위를 할당한다.
- 우선순위 큐를 통한 순위 할당
int[] result = new int[emergency.length];
Arrays.fill(result, -1); // 초기에 모든 순위를 -1로 설정
int rank = 1; // 순위는 1부터 시작
while (!pq.isEmpty()) {
int max = pq.poll(); // 가장 큰 값을 가져옴
// 해당 값의 인덱스를 찾아서 순위를 할당
for (int i = 0; i < emergency.length; i++) {
if (emergency[i] == max && result[i] == -1) {
result[i] = rank++;
break; // 중복된 원소가 없으므로 찾은 후 반복 종료
}
}
}
우선순위 큐에서 poll()은 값을 꺼내면서 제거한다. 따라서 큐가 비어있지 않을 때까지 반복문을 순회하면서 값을 꺼낼 수 있다. 이때, 꺼낸 값에 대해서 우선순위 큐에서 값을 꺼낼 때마다 해당 값이 원래 배열 emergency에서 몇 번째 위치에 있는지를 확인한다. 각 요소에 대한 순위는 처음으로 해당 값을 발견한 위치에 부여되고, 이미 순위가 할당된 위치는 건너뛰기 위해 result 배열을 초기에 -1로 설정하여 사용한다.
즉 꺼낸 값을 emergency 배열에서 몇 번째에 있는지를 검사하고, 그 위치의 result 배열 값이 -1인 경우, 즉 아직 순위가 할당되지 않은 위치에 현재 순위를 저장한다. 이렇게 함으로써, 배열 전체를 순회하면서 최초로 해당 값이 나타난 위치에만 순위를 할당할 수 있다. 중복된 원소가 없기 때문에, 한 번 순위를 할당하면 해당 인덱스에 대한 검사는 중지하고 다음 최대값을 우선순위 큐에서 꺼내서 동일한 과정을 반복한다.
구체적으로 예를 들어보자.
예를 들어, emergency 배열이 [30, 10, 23, 6, 100]일 경우, 우선순위 큐는 [100, 30, 23, 10, 6]의 순서로 값을 반환한다. 우선순위 큐에서 100을 꺼내면, emergency 배열에서 100의 위치는 인덱스 4이다. 100은 순위가 1이므로 result 배열에서 1을 차지해야 한다. 이때, result++에 의해서 result[4]는 1이 된다.
마찬가지로 이후 30을 꺼내면 emergency에서의 위치는 인덱스 0이므로 result[0]은 2가 된다.
이러한 방식으로 모든 요소에 대해 순위를 할당한다.
이처럼 우선순위 큐를 활용하여 정렬과정 없이 각 요소의 최대값을 효과적으로 추출하고, 각 값에 대한 순위를 효율적으로 매길 수 있다.
그렇다면 전체 시간 복잡도는 어떻게 될까? 각 원소를 우선순위 큐에 삽입하는 과정과, 우선순위 큐에서 원소를 꺼내어 순위를 할당하는 과정이 핵심이다.
첫 번째로, n 개의 원소를 우선순위 큐에 삽입하는 부분을 보자. 각 삽입 연산은 우선순위 큐의 힙 구조를 유지하기 위해 O(log n)의 시간이 소요된다다. 따라서 n 개의 원소를 모두 삽입하는 데 필요한 총 시간은 n * O(log n)이다. 삽입 과정 전체의 시간 복잡도는 따라서 O(n log n)이다.
두 번째로, 우선순위 큐에서 원소를 하나씩 꺼내는 연산을 살펴보자. 역시 O(log n)의 시간을 소요한다. 우선순위 큐가 비어있을 때까지 n 번의 꺼내기 연산을 수행하므로, 이 과정에서도 n * O(log n)의 시간 복잡도가 발생한다. 결과적으로 이 부분의 시간 복잡도 역시 O(n log n)이다.
따라서, 전체적으로 이 알고리즘의 시간 복잡도는 우선순위 큐에 원소를 삽입하고, 우선순위에 따라 원소를 꺼내 순위를 매기는 과정을 모두 합친 O(n log n)으로 요약할 수 있다.
결론적으로 정렬 기반의 하한의 시간복잡도에서 풀이할 수 있다.
전체 코드
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
public class Solution {
public static void main(String[] args) {
solution(new int[] {30, 10, 23, 6, 100});
}
public static int[] solution(int[] emergency) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
for (int value : emergency) {
pq.add(value);
}
// pq에 정렬이 되었는지 확인을 위해 출력하는 코드
while (!pq.isEmpty()) {
System.out.println(pq.poll());
}
int[] result = new int[emergency.length];
Arrays.fill(result, -1); // 임시로 -1로 초기화하여 순위가 할당되지 않은 것을 나타냄
// 순위 할당
int rank = 1;
while (!pq.isEmpty()) {
int max = pq.poll(); // 가장 큰 값 제거
// 이 값의 인덱스 찾기
for (int i = 0; i < emergency.length; i++) {
if (emergency[i] == max && result[i] == -1) {
result[i] = rank;
break; // 중복 원소가 없으므로 바로 빠져나감
}
}
rank++;
}
return result;
}
}
4. 정렬 사용 3 - HashMap 사용
마찬가지로 정렬을 사용하되 이번에는 다른 자료구조로 풀이하는 방법을 살펴보자. HashMap을 사용해볼 수 있다.
HashMap을 사용하는 방법은 해시 테이블을 이용하여 각 원소의 인덱스를 빠르게 찾을 수 있다. 이 접근법은 특히 원소와 그 위치를 연결해야 할 때 유용하다. 복잡한 정렬 로직 없다는 게 장점이다.
먼저 HashMap을 초기화한다.
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < emergency.length; i++) {
indexMap.put(emergency[i], i);
}
각 원소의 인덱스를 저장할 HashMap을 생성하는 코드이다. 이 맵은 원소 값을 키로, 그 원소의 인덱스를 값으로 저장한다.
원본 배열을 유지하기 위해 원본 배열 emergency를 복사하여 sortedEmergency라는 새 배열을 만들고, 이 배열을 오름차순으로 정렬하자. 정렬된 배열을 사용하여 문제에서 요구하는 각 원소의 순위를 결정할 수 있다.
int[] sortedEmergency = emergency.clone();
Arrays.sort(sortedEmergency);
이번에는 역순이 아니라 정순으로 정렬을 해보았다.
이제 이 정렬된 배열로 어떻게 해야할까? 위의 우선순위큐나 인덱스를 활용한 풀이 방법에서와 마찬가지로 이제 순위를 원래 인덱스에 맞추어 매핑을 해주기만 하면 된다. 정렬이 정순으로 되어 있으니 sortedEmergency 배열을 역순으로 순회하면서 각 원소의 순위를 할당한다. 이 때 HashMap에서 원소의 원래 인덱스를 조회하여 result 배열에 순위를 저장할 수 있다. 배열의 끝에서부터 시작하여 가장 큰 값부터 순위를 1부터 할당하면 된다.
int[] result = new int[emergency.length];
int rank = 1;
for (int i = sortedEmergency.length - 1; i >= 0; i--) {
int value = sortedEmergency[i];
int originalIndex = indexMap.get(value);
result[originalIndex] = rank++;
}
예를 들어서 4번 인덱스 원소인 100이 어떻게 처리되는지 살펴보자. sortedEmergency[i]에서 4번째 항목인 100이 먼저 추출될 것이다. 이후 hashMap에서 해당 value가 key로서 조회되면 4라는 값이 획득되는데 이것이 곧 100의 원래 인덱스이다. 따라서 이 100을 rank 1과 매핑해주어면 되되, 원래의 인덱스를 사용하여 결과 배열에서 원래 인덱스 부분 주소에 rank로 초기화해준다.
↓
↓
HashMap을 사용하는 부분은 원소의 값을 키로 사용하여 그 값의 원래 인덱스를 빠르게 찾을 수 있다. 이 부분은 O(1)이다. 정렬 부분에서 비교 기반 정렬의 하한 만큼 시간 복잡도를 쓸 것이므로, 전체 순위 할당 과정의 시간 복잡도는 배열을 정렬하는 데 필요한 O(n log n)이다.
전체 코드
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public static void main(String[] args) {
solution(new int[] {30, 10, 23, 6, 100});
}
public static int[] solution(int[] emergency) {
// 해시맵으로 각 값과 인덱스 매핑
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < emergency.length; i++) {
indexMap.put(emergency[i], i);
}
// 배열 복사 및 정렬
int[] sortedEmergency = emergency.clone();
Arrays.sort(sortedEmergency);
// 결과 배열 초기화 및 순위 매기기
int[] result = new int[emergency.length];
int rank = 1;
for (int i = sortedEmergency.length - 1; i >= 0; i--) {
int value = sortedEmergency[i];
int originalIndex = indexMap.get(value);
result[originalIndex] = rank++;
}
return result;
}
}
5. 정렬 사용 4 - 객체 지향
자료구조로 푸는 것도 좋지만 객체지향으로 풀어볼 수도 있을까? 자바에서는 정렬 관련 클래스가 잘 구현이 되어있고 이를 객체에 맞물려서 사용하기가 쉽게 되어 있기 때문에 객체로 푸는 것도 좋은 선택지가 될 것이다.
객체 클래스를 정의하고 이를 활용하여 문제를 해결해보자.
Patient 클래스의 구현
Patient 클래스는 환자의 응급도(emergency)와 원본 배열에서의 위치(index) 두 가지 속성을 가지고 있다. 클래스는 Comparable 인터페이스를 구현하여, 환자 객체들을 응급도에 따라 자동으로 정렬할 수 있도록 있다.
class Patient implements Comparable<Patient> {
int emergency;
int index;
Patient(int emergency, int index) {
this.emergency = emergency;
this.index = index;
}
@Override
public int compareTo(Patient other) {
return Integer.compare(other.emergency, this.emergency); // 내림차순 정렬
}
}compareTo 메서드에서는 other.emergency와 this.emergency를 비교함으로써 내림차순 정렬을 지정한다. 이렇게 함으로써 가장 응급도가 높은 환자가 리스트의 가장 앞에 오게 된다.
간단하게 Comparable이 어떻게 작동하는지를 짚고 넘어가보자.
Comparable 인터페이스의 compareTo 메서드는 객체 간의 순서를 비교하는 메서드로, 정렬 시 기준이 되는 메서드이다. 이 메서드는 정수를 반환하며, 반환 값에 따라 정렬 순서가 결정된다.
- 반환 값이 음수인 경우: 현재 객체가 비교 객체보다 '작다'
- 반환 값이 0인 경우: 두 객체가 '같다'
- 반환 값이 양수인 경우: 현재 객체가 비교 객체보다 '크다'
Integer.compare(other.emergency, this.emergency)를 사용하면, other의 응급도가 this의 응급도보다 클 때 음수를 반환한다. 따라서 이는 정렬 순서를 역으로 하여 응급도가 높은 환자가 먼저 오도록 내림차순으로 정렬되게 한다.
응급도에 따른 환자 리스트 정렬
이제 이렇게 만든 객체를 어떻게 사용하면 좋을까?
파라미터를 받을 때 해당 객체로 초기화해준다.
환자의 응급도를 기반으로 진료 순서를 결정하기 위해 ArrayList에 환자 객체들을 추가하고, Collections.sort() 메서드를 사용하여 리스트를 정렬한다.
List<Patient> patients = new ArrayList<>();
for (int i = 0; i < emergency.length; i++) {
patients.add(new Patient(emergency[i], i));
}
Collections.sort(patients);
각 환자의 응급도와 배열에서의 인덱스를 사용하여 Patient 객체를 생성하고, 이를 리스트에 추가한다. 그 후, 리스트를 정렬하여 응급도가 높은 순으로 배열된다.
그림으로 살펴보면 다음과 같다.
정렬 전
정렬 후
이제 정렬이 되었으니 결과를 만들어주기만 하면된다. 어떻게 할까? 이전과 동일하다! 원래 인덱스를 찾아서 순위를 매핑해주기만 하면 된다.
결과 배열 생성
정렬된 리스트를 순회하면서, 각 환자 객체의 인덱스 속성을 사용하여 결과 배열에 순위를 할당하자.
int[] result = new int[emergency.length];
for (int i = 0; i < patients.size(); i++) {
result[patients.get(i).index] = i + 1; // 순위 할당
}
이 부분에서 patients.get(i).index는 원본 배열 emergency에서 해당 환자의 위치를 나타내고, i + 1은 해당 환자의 진료 순위를 의미한다.
i가 0 -> 1로 변환될 때 결과 배열이 변화하는 모습을 다음과 같이 확인해보자.
전체 코드
import java.util.*;
class Patient implements Comparable<Patient> {
int emergency;
int index;
Patient(int emergency, int index) {
this.emergency = emergency;
this.index = index;
}
// 내림차순 정렬을 위한 compareTo 구현
@Override
public int compareTo(Patient other) {
return Integer.compare(other.emergency, this.emergency);
}
}
class Solution {
public int[] solution(int[] emergency) {
List<Patient> patients = new ArrayList<>();
// 환자 객체 초기화
for (int i = 0; i < emergency.length; i++) {
patients.add(new Patient(emergency[i], i));
}
// 환자 리스트 정렬
Collections.sort(patients);
// 결과 배열 초기화
int[] result = new int[emergency.length];
for (int i = 0; i < patients.size(); i++) {
result[patients.get(i).index] = i + 1; // 순위 할당
}
return result;
}
}
덧니, 객체와 자료구조
문제를 풀다보니 객체 구현에서 int 타입 필드가 두 개 있는 객체가 생성이 되었는데, 재밌는 포인트가 있다. 객체와 자료구조에 대해 생각해볼 점이다.
'객체'라는 용어는 특정 클래스의 인스턴스를 의미한다. 클래스는 필드(속성)와 메소드(행동)를 정의하는 틀이며, 이 틀을 사용해 생성된 각각의 인스턴스가 객체이다. 하지만 흥미로운 점은, 이러한 객체의 구조가 기본적으로 자료구조의 확장이라는 사실이다.
특히 이번 문제에서 사용한 Patient 클래스는 이를 여실히 드러내는 예시이다. Patient 객체는 단순히 두 개의 정수 필드, 즉 emergency와 index를 가진다. 이는 어떤 면에서 보면, 두 개의 데이터 열을 가진 2차원 배열이나, 두 개의 서로 다른 자료형을 키와 값으로 가지는 해시맵과 유사한 구조를 지닌다.
class Patient {
int emergency; // 응급도
int index; // 배열에서의 위치
}
힙에 생성되는 데이터 저장 방식을 보자. 동일하다. 이름만 붙어 있을 뿐?!
마치 Map<Integer, Integer> 구조에서 키와 값을 저장하는 것과 비슷한 구조를 가지며, 각 키와 값은 특정 응급도와 그 응급도가 위치한 인덱스를 나타낸다.
여기서 재밌는 포인트가 나온다. 객체의 필요성을 자료구조의 확장에서부터 생각해볼 수 있다는 점이다.
그렇다면 차이점은 무엇일까?
배열이나 HashMap 같은 자료구조는 데이터를 효율적으로 저장하고 접근하는데 초점을 맞춘다. 예를 들어, 배열은 인덱스를 통해 빠르게 데이터에 접근할 수 있는 반면, HashMap은 키-값 쌍을 통해 데이터를 빠르게 조회할 수 있다. 그러나 당연히 자료구조는 데이터에 대한 복잡한 조작이나 추가적인 동작을 설계하는 데에는 한계가 있다. 객체는 어떨까?
객체의 특징은 데이터와 그 데이터를 다루는 메소드를 한데 묶음으로써, 데이터의 구조와 그 데이터를 처리하는 방식을 객체 내부에 통합하여 관리할 수 있다는 점이다! 따라서 단순히 데이터를 저장하고 조회하는 대리인의 역할에 그친다면 객체는 자료구조와 큰 차이점이 없을 수도 있다.
Patient 객체가 '객체 지향'일 수 있는 이유는 무엇일까? 마치 "지능적인 배열"처럼, 각 Patient 객체는 자신의 데이터를 가지고 있을 뿐만 아니라, 그 데이터를 어떻게 처리할지에 대한 로직도 포함하고 있기 때문이다. 이를테면, emergency와 index라는 데이터를 내부적으로 저장하면서, 이 데이터에 대한 특정 행동인 compareTo 메소드를 통해 다른 Patient 객체와의 비교를 가능하게 하는 점이다. 이는 객체가 단순한 자료 저장 매체 이상의 역할을 한다는 것을 보여준다. compareTo 메소드는 Patient 객체들을 특정 기준(여기서는 emergency)에 따라 정렬할 수 있는 기능을 제공하며, 즉 자신의 데이터에 대해 자율적으로 전적인 책임을 지며, 이는 Patient 객체가 단순한 데이터 이상의 가치를 가질 수 있게 하는 것이다. 이로써 객체의 데이터는 단지 두개의 정수에 머물러 있지 않고 로직이 적용된 의미 있는 자료로 '추상화'된다.
물론, 객체가 가진 엄밀한 구조적 특성을 고려해보면, 배열이나 자료구조와 다르게 개수에 제한 없이 서로 다른 자료형을 담을 수 있는 바구니 역할을 한다는 점도 있다. 예제에서 사용된 Patient 객체의 경우 두 필드 모두를 int 타입으로 갖게 되었기 때문에 유사성이 도드라진 측면이 있다. 서로 다른 자료형을 담는 점도 자료구조와 객체의 간극임이 맞다. 하지만 데이터 타입에만 국한될 때 객체의 역할은 너무 축소되고, 객체지향스럽지 못할 수 있다.
이 예시에서 톺아볼 포인트는 객체의 자료구조 확장성, 그리고 차이점이었다.
📦 제출
다시 문제로 돌아와서 이제 각각의 문제들을 제출해보자. 이런 의문이 들 것 같다. 어떤 게 제일 빠를까?
아마 이 글을 읽는 모든 사람이 1번이 가장 느리고 나머지는 고만고만하다고 생각하지 않을까 싶다.
최소한 나는 그랬다... 😅
방법1: 브루트포스
방법2: 정렬과 인덱스 배열
방법3: 정렬와 우선순위큐
방법4: 정렬과 해시맵
방법5: 정렬과 객체
왠걸?!
1번 방법이 제일 빠르다.
데이터 수가 적어서 아마 java.util을 불러와서 사용하는 비용, 객체를 초기화하고 관리하는데 쓰이는 비용이 단순 연산보다 훨씬 컸기 때문인 것 같다.
'알고리즘 > 프로그래머스' 카테고리의 다른 글
| [프로그래머스/자바] 옹알이 (1) - 두 가지 풀이 방식 (0) | 2024.01.11 |
|---|---|
| [백준/자바] 2775 부녀회장이 될테야 (1) | 2022.12.01 |
| [프로그래머스/파이썬] 레벨 0 피자 나눠 먹기 2 (0) | 2022.10.13 |
| [프로그래머스/파이썬] 레벨 0 최빈값 구하기 (1) | 2022.10.13 |
| [프로그래머스/파이썬] 레벨 0 옷가게 할인 받기 (0) | 2022.10.13 |
