오늘의 학습 키워드
- Relative Ranks
공부한 내용 본인의 언어로 정리하기
class Solution {
public String[] findRelativeRanks(int[] score) {
Map<Integer, Integer> scores = new HashMap<>(); //key 와 value를 함께 가져갈 수 있는 HashMap 생성
for(int i = 0; i < score.length; i++){
scores.put(i, score[i]); //i는 인덱스, score[i]는 i번째 점수
}
List<Map.Entry<Integer,Integer>> entries = new ArrayList<>(scores.entrySet()); //Map.Entry를 사용하면 Map에 저장된 모든 Key-Value 쌍을 각각 Key-Value를 갖고 있는 하나의 객체로 얻을 수 있음.
entries.sort((a,b) -> b.getValue().compareTo(a.getValue())); //내림차순 정렬
String[] result = new String[score.length];
for(int i = 0; i < score.length; i++){
int originalIndex = entries.get(i).getKey(); //i번째 Entry 객체를 가져와서 그 객체의 키(key)를 추출한다. 이 키는 원래 점수 배열의 인덱스(key)이다. 결론적으로 i번째 객체의 원래 인덱스를 같이 가져온다.
switch (i) {
case 0 -> result[originalIndex] = "Gold Medal";
case 1 -> result[originalIndex] = "Silver Medal";
case 2 -> result[originalIndex] = "Bronze Medal";
default -> result[originalIndex] = String.valueOf(i + 1);
}
}
return result;
}
}오늘의 회고
오늘 문제는 이전 문제와 다르게 한번에 인덱스와 값을 한번에 가져와야 해서 굉장히 어렵게 느껴졌다.
처음에는 똑같이 배열로 내림차순을 한 뒤, 인덱스 순서에 따라 금, 은, 동메달으로 변환하고 나머지 값들은 i+1을 하면 된다고 생각했다.
그리고 변환 후에는 원래의 배열로 되돌려 놓으면 완성될 것 같아서 시도를 하였고, 도중에 내림차순을 해서 변환을 한 값들을 다시 원래 인덱스로 돌려 놓을 방법이 도저히 생각이 나지 않아서 새로운 방법을 고민을 했다.
고민 중 떠오른 것은 최근에 많이 봤던 HashMap이었고 다행히 공부를 하면서 Key와 Value가 한 쌍으로 만들어 진다는 것을 기억해냈다.
그래서 int[] score를 HashMap으로 만드는 것 부터 시작했다. 새 HashMap을 생성하고 score의 값들을 기본 인덱스 처럼 0부터 시작해서 score의 길이만큼 만들어서 score의 배열에 Key를 부여했다.
Map<Integer, Integer> scores = new HashMap<>(); //key 와 value를 함께 가져갈 수 있는 HashMap 생성
for(int i = 0; i < score.length; i++){
scores.put(i, score[i]); //i는 인덱스, score[i]는 i번째 점수
}출력 시도 :
{0=10, 1=3, 2=8, 3=9, 4=4}그리고 내림차순으로 정렬하기 위해 찾아보다 Map.Entry라는 것을 발견했고 Map.Entry를 사용하면 Map에 저장된 모든 Key-Value 쌍을 각각 Key-Value를 갖고 있는 하나의 객체로 얻을 수 있다는 것을 배우고 List로 만들어서 정렬을 시도했다.
//Map.Entry를 사용하면 Map에 저장된 모든 Key-Value 쌍을 각각 Key-Value를 갖고 있는 하나의 객체로 얻을 수 있음.
List<Map.Entry<Integer,Integer>> entries = new ArrayList<>(scores.entrySet());
entries.sort((a,b) -> b.getValue().compareTo(a.getValue())); //내림차순 정렬, a.getValue().compareTo(b.getValue())는 오름차순출력 시도 :
{0=10, 3=9, 2=8, 4=4, 1=3}이제는 entries의 배열을 인덱스 값 순서에 따라 금, 은, 동메달과 각 순위를 부여해야 했다.
그래서 i번째 값을 가져올 때 원래의 인덱스 값을 가져와서 result 배열의 인덱스에 넣어야 변환된 값이 처음 배열의 자리로 찾아가기 때문에 아래 코드를 이용해서 값을 가져왔다.
entries.get(i).getKey();그래서 내림차순으로 정렬된 List를 순회하며 원래의 인덱스 값을 찾아내고 result[key]로 원래 순서를 정렬해서 반환했다.
entries의 index(0)의 값의 키는 0이고, index(1)의 값의 키는 3이고... score.length 만큼 반복된다.
그 결과 10점은 result[0], 9점은 result[3], 8점은 result[2], 4점은 result[4], 3점은 result[1]이 된다.
이 결과를 result[] 배열의 순서대로 적용하면 [10, 3, 8, 9, 4]가 된다.
그리고 case에 맞춰 i가 0 이었던 10점은 "Gold Medal", i 가 1이었던 9점은 "Silver Medal", i가 2였던 8점은 "Bronze Medal", 그 이후 3, 4는 각각 i+1인 4와 5로 result[]의 순서에 맞춰서 반환이 된다.
String[] result = new String[score.length];
for(int i = 0; i < score.length; i++){
//i번째 Entry 객체를 가져와서 그 객체의 키(key)를 추출한다. 이 키는 원래 점수 배열의 인덱스(key)이다. 결론적으로 i번째 객체의 원래 인덱스를 같이 가져온다.
int originalIndex = entries.get(i).getKey();
switch (i) {
case 0 -> result[originalIndex] = "Gold Medal";
case 1 -> result[originalIndex] = "Silver Medal";
case 2 -> result[originalIndex] = "Bronze Medal";
default -> result[originalIndex] = String.valueOf(i + 1);
}
}그 결과 result[] 배열에 맞게 [Gold Medal, 5, Bronze Medal, Silver Medal, 4]로 완성이 된다.
AI 코드리뷰
현재 코드 리뷰:
장점:
HashMap을 사용하여 원래 인덱스와 점수를 연결하여 저장합니다. 이는 정렬 후에도 원래 위치를 추적할 수 있게 해줍니다.Map.Entry를 사용하여 키-값 쌍을 효과적으로 다룹니다.- 람다식을 사용하여 간결하게 정렬 로직을 구현했습니다.
switch문을 사용하여 상위 3개의 순위에 대한 메달 할당을 명확히 처리했습니다.
단점:
- 시간복잡도가 O(n log n)입니다. 이는 정렬 과정 때문입니다.
- 추가적인 공간(
HashMap,ArrayList)을 사용하여 공간복잡도가 O(n) 입니다.
개선된 코드 제안
class Solution {
public String[] findRelativeRanks(int[] score) {
int n = score.length;
String[] result = new String[n];
int[] sortedScore = Arrays.copyOf(score, n);
Arrays.sort(sortedScore);
Map<Integer, String> rankMap = new HashMap<>();
for (int i = n - 1; i >= 0; i--) {
if (i == n - 1) rankMap.put(sortedScore[i], "Gold Medal");
else if (i == n - 2) rankMap.put(sortedScore[i], "Silver Medal");
else if (i == n - 3) rankMap.put(sortedScore[i], "Bronze Medal");
else rankMap.put(sortedScore[i], String.valueOf(n - i));
}
for (int i = 0; i < n; i++) {
result[i] = rankMap.get(score[i]);
}
return result;
}
}개선된 버전의 장점:
이 코드의 시간복잡도는 여전히 O(n log n) 이지만, 원본 배열을 직접 정렬하지 않고 복사본을 사용하여 원래 순서를 유지합니다. 또한, 한 번의 순회로 순위를 매깁니다.
Heap을 이용한 방법
class Solution {
public String[] findRelativeRanks(int[] score) {
int n = score.length;
String[] result = new String[n];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
for (int i = 0; i < n; i++) {
pq.offer(new int[]{score[i], i});
}
int rank = 1;
while (!pq.isEmpty()) {
int[] current = pq.poll();
int index = current[1];
if (rank == 1) result[index] = "Gold Medal";
else if (rank == 2) result[index] = "Silver Medal";
else if (rank == 3) result[index] = "Bronze Medal";
else result[index] = String.valueOf(rank);
rank++;
}
return result;
}
}이 코드는 최대 힙(Max Heap)을 사용하여 구현되었습니다. 시간복잡도는 여전히 O(n log n) 이지만, 공간 효율성이 개선되었고 코드가 더 간결해졌습니다. 또한, 전체 배열을 정렬하지 않고도 순위를 매길 수 있습니다.
각 접근 방식의 장단점:
- 원래 코드: 직관적이지만 추가 공간을 많이 사용합니다.
- 개선된 코드: 원본 배열 순서를 유지하면서 효율적으로 순위를 매깁니다.
Heap사용 코드: 공간 효율적이며, 전체 정렬 없이 순위를 매길 수 있습니다.
선택은 구체적인 요구사항과 제약조건에 따라 달라질 수 있습니다.
내일 공부할 것 :
원래 인덱스에 맞춰서 다시 정렬시켜주는 부분이 확실히 이해가 되지 않고 있고, 오늘 주제였던 Heap에 대해서도 시도 조차 못하고 있다.
정리 할 것들이 많지만 더욱 빡빡하게 공부하고 정리 해야 할 필요성이 절실하다.
문제
