문제
풀이
- HashMap 사용
- int 배열 중 가장 높은 순위 1, 2, 3을 각각 string으로 맵핑해야 한다.
- 3위 밖은 차례대로 rank 값으로 치환해줘야 함
- Gold, Silver, Bronze의 Enum과 rank를 기록한 HashMap을 사용
- rank(최대 3위) 안의 rank는 Enum을 사용하여 medal로 변환, 그 외는 차례대로 rank로 치환
- Max Heap 사용
- heap 구현 후 int 배열을 heap에 insert
- for문을 순회하며 heap에서 delete하고 answer에 차례대로 저장
코드 HashMap
import java.util.Arrays;
import java.util.ArrayList;
import java.util.List;
class Solution {
public String[] findRelativeRanks(int[] score) {
int maxRank = 3;
int[] copiedScore = Arrays.copyOf(score, score.length);
Arrays.sort(copiedScore);
int[] reversedSorted = reverse(copiedScore);
Map<Integer, Integer> rankMap = getRankMap(reversedSorted);
String[] answer = new String[score.length];
for(int i = 0; i < score.length; i++){
Integer rank = rankMap.get(score[i]);
if(rank < maxRank){
answer[i] = Medal.getMedalByIndex(rank).getMedal();
} else {
answer[i] = String.valueOf(rank + 1);
}
}
return answer;
}
public static int[] reverse(int[] array){
int length = array.length;
int[] reversedArray = new int[length];
for(int i = 0; i < length; i++){
reversedArray[length - i - 1] = array[i];
}
return reversedArray;
}
public static Map<Integer, Integer> getRankMap(int[] array){
Map<Integer, Integer> rankMap = new HashMap<>();
for(int i = 0; i < array.length; i++){
rankMap.put(array[i], i);
}
return rankMap;
}
public enum Medal {
GOLD("Gold Medal"),
SILVER("Silver Medal"),
BRONZE("Bronze Medal");
private final String medal;
Medal(String medal){
this.medal = medal;
}
public String getMedal(){
return medal;
}
public static Medal getMedalByIndex(int index){
switch(index){
case 0:
return GOLD;
case 1:
return SILVER;
case 2:
return BRONZE;
default:
throw new IllegalArgumentException("존재하지 않은 순위" + index);
}
}
}
}코드 Max Heap
class Solution {
public String[] findRelativeRanks(int[] score) {
MaxHeap myHeap = new MaxHeap();
String[] answer = new String[score.length];
for(int i = 0; i < score.length; i++){
myHeap.insert(score[i], i);
}
for(int i = 0; i < score.length; i++){
Node node = myHeap.delete();
if(i < 3){
answer[node.index] = Medal.getMedalByIndex(i).getMedal();
} else {
answer[node.index] = String.valueOf(i + 1);
}
}
return answer;
}
public enum Medal {
GOLD("Gold Medal"),
SILVER("Silver Medal"),
BRONZE("Bronze Medal");
private final String medal;
Medal(String medal){
this.medal = medal;
}
public String getMedal(){
return medal;
}
public static Medal getMedalByIndex(int index){
switch(index){
case 0:
return GOLD;
case 1:
return SILVER;
case 2:
return BRONZE;
default:
throw new IllegalArgumentException("존재하지 않은 순위" + index);
}
}
}
}
class Node {
int value;
int index;
Node(int value, int index){
this.value = value;
this.index = index;
}
}
class MaxHeap {
private List<Node> heap;
public MaxHeap(){
this.heap = new ArrayList<>();
}
private int getLeftChildIndex(int parentIndex) {
return parentIndex * 2 + 1;
}
private int getRightChildIndex(int parentIndex) {
return parentIndex * 2 + 2;
}
private int getParentIndex(int childIndex) {
return (childIndex - 1) / 2;
}
private Node peek(){
return heap.isEmpty() ? null : heap.get(0);
}
private boolean hasParent(int index) {
return getParentIndex(index) >= 0;
}
public int size(){
return heap.size();
}
public void insert(int value, int index){
Node node = new Node(value, index);
heap.add(node);
heapifyUp();
}
private void swap(int index1, int index2){
Node temp = heap.get(index1);
heap.set(index1, heap.get(index2));
heap.set(index2, temp);
}
private void heapifyUp() {
int currentIndex = heap.size() - 1;
while(hasParent(currentIndex)){
int parentIndex = getParentIndex(currentIndex);
if(heap.get(parentIndex).value < heap.get(currentIndex).value){
swap(parentIndex, currentIndex);
currentIndex = parentIndex;
} else {
break;
}
}
}
public Node delete(){
if(heap.isEmpty()){
return null;
}
Node max = heap.get(0);
Node last = heap.remove(heap.size() - 1);
if (!heap.isEmpty()) {
heap.set(0, last);
heapifyDown();
}
return max;
}
private void heapifyDown(){
int currentIndex = 0;
int count = heap.size();
while(true){
int leftChildIndex = getLeftChildIndex(currentIndex);
int rightChildIndex = getRightChildIndex(currentIndex);
int largestIndex = currentIndex;
if(leftChildIndex < count && heap.get(leftChildIndex).value > heap.get(largestIndex).value){
largestIndex = leftChildIndex;
}
if (rightChildIndex < count && heap.get(rightChildIndex).value > heap.get(largestIndex).value) {
largestIndex = rightChildIndex;
}
if (largestIndex != currentIndex) {
swap(currentIndex, largestIndex);
currentIndex = largestIndex;
} else {
break;
}
}
}
public void printHeap() {
for (Node node : heap) {
System.out.println("Value: " + node.value + ", Index: " + node.index);
}
}
}정리
- 예전에 동일한 문제를 최대힙으로 풀었던 기억이 있어서 최대힙으로 풀어보려고 했는데, 구현 불가 이슈로 예전에 js로 만들었던 max heap java로 옮겨달라 해서 풀었다
- 문제 잘못 읽어서 빙 돌아감
- heapifyDown 다시 봐도 이해가 잘 안간다.
- 확실히 자료구조를 사용하는 쪽이 사용처에서 코드가 더 깔끔하고 직관적 인 거 같다.
- java로 sort 내림차순하려니까 stream이 나오느데, 잘 몰라서 for문으로 바꿨다.
- 1번의 경우, 절차지향이라 읽기가 어려운 거 같다.
프론트엔드 개발