[프로그래머스/Lv.1] 명예의 전당 (1)

 

https://school.programmers.co.kr/learn/courses/30/lessons/138477

프로그래머스

 

 

틀렸던 코드

1

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        int[] hof = new int[k];
        
        for(int i = 0; i < k; i++) {
            hof[i] = score[i];
            answer[i] = hof[0];
        }
        
        for(int i = k; i < score.length; i++) {
            Arrays.sort(hof);
            if (hof[0] >= score[i]) {
                answer[i] = hof[0];
            } else {
                hof[0] = score[i];
                Arrays.sort(hof);
                answer[i] = hof[0];
            }
            
        }
        
        return answer;
    }
}

테스트케이스 2개 통과

채점하면 4개 통과 / 나머지는 실패 or 런타임 에러

 

2

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        int[] hof = new int[k];
        
        
        
        for(int i = 0; i < k; i++) {
            if (i == 0) {
                Arrays.fill(hof, score[0]);
                answer[0] = hof[0];
            } else {
                hof[i] = score[i];
                Arrays.sort(hof);
                answer[i] = hof[0];
            }
        }
        
        for(int i = k; i < score.length; i++) {
            if (hof[0] < score[i]) {
                hof[0] = score[i];
                Arrays.sort(hof);
                answer[i] = hof[0];
            } else {
                answer[i] = hof[0];
            }
            
        }
        
        return answer;
    }
}

i<k for문 돌때 sort 해주는거도 넣었었는데 hof 배열이 채워지기전에 sort되니 hof 채워질때까지는 score 값과 상관없이 hof 배열 맨 앞에 0이 계속 와있게됐다(int 배열은 값 안 넣은 부분이 0으로 채워지니까) 

hof가 k만큼 채워지기전까지는 0이 최소값일 수 밖에 없어서 k수만큼 0이 주르륵 나오는걸보고 아예 맨처음에 hof 배열 전체에 score[0[으로 채워주자는 생각이 들어서 Arrays.fill(hof, score[0]); 을 넣어주게 됐다

 

근데 결과가 하나씩 밀리거나 조금씩 다르게 나왔다,, 어디서 헤매고 있는걸까 고민을 다시

 

.

.

.

 

천천히 다시 종이에 써보다가 실수를 깨달았다

[0, 300, 40, 300, 20, 70, 150, 50, 500, 1000]

i=0, hof : [0, 0, 0, 0] / answer(0) = hof(0) = 0

i=1, hof : [0, 300, 0, 0] -> sort 후 : [0, 0, 0, 300] / answer(1) = hof(1) = 0

i=2, hof : [0, 0, 40, 300] -> sort 후 : 동일 / answer(2) = hof(2) = 40

 

i=3, hof : [0, 0, 40, 300] 

  -> 여기부터 문제가 시작되는거였다 가장 큰 수가 맨 뒤에 밀려나있는데 hof[i] = score[i]; 때문에 마지막 자리에 score[3] 이 들어가서 값이 덮어씌어진다 정상적이라면 i=3이 되고 hof가 다 채워졌을때 [0, 300, 40, 300] 이렇게 4개의 숫자가 있었어야한다,,

초기 hof부터 엉망이니까 다 틀어진거였다 아예 접근을 잘못했다

다시 해보기!

 

 

3

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        int[] hof = Arrays.copyOfRange(score, 0, 4);
        int n = 0;
        
        
        for(int i = 0; i < k; i++) {
            if (i == 0) {
                answer[0] = score[0];
                n = answer[0];
            } else {
                n = score[i] < n ? score[i] : n;
                answer[i] = n;
            }
        }
        
        Arrays.sort(hof);
        
        for(int i = k; i < score.length; i++) {
            if (hof[0] < score[i]) {
                hof[0] = score[i];
                Arrays.sort(hof);
                answer[i] = hof[0];
            } else {
                answer[i] = hof[0];
            }
            
        }
        
        return answer;
    }
}

 

이번에도 1이랑 같은 결과,,, 테스트케이스는 다 통과 / 채점하면 4개 통과, 나머지는 실패 or 런타임 에러

 

일단 바꿔준거 쓰면

hof를 k만큼 채울떼 score를 복사해와서 초기화해줬다, 그리고 score 첫 값 이후에는 비교를 해주며 작은값을 answer에 넣어줬다 i=k 이후부터는 sort 써가며 맨 앞에 있는 배열값을 유지시키거나 바꾸거나 하는식,, 어디서 잘못했을까?

 

.

.

.

다시 해보다가 발견

너ㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓㅓ무 어이없는 실수를 했다

int[] hof = Arrays.copyOfRange(score, 0, 4);

이부분ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ k=4일때로 해보다가 그냥 저렇게 넣었던거다 제발 꼼꼼해지자,,,,,,,,,,,

4 들어간 곳을 k로 바꿔줬더니 

 

4

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        int[] hof = Arrays.copyOfRange(score, 0, k);
        int n = 0;
        
        
        for(int i = 0; i < k; i++) {
            if (i == 0) {
                answer[0] = score[0];
                n = answer[0];
            } else {
                n = score[i] < n ? score[i] : n;
                answer[i] = n;
            }
        }
        
        Arrays.sort(hof);
        
        for(int i = k; i < score.length; i++) {
            if (hof[0] < score[i]) {
                hof[0] = score[i];
                Arrays.sort(hof);
                answer[i] = hof[0];
            } else {
                answer[i] = hof[0];
            }
            
        }
        
        return answer;
    }
}

 

 

9, 11번 빼고 통과!! 런타임 에러만 잡으면 된다

 

.

.

.

.

.

.

 

고민하고 고민하다가 해결이 안나서 짝꿍이랑 의견나눴고 드디어 해결했다

 

최종 코드

import java.util.*;

class Solution {
    public int[] solution(int k, int[] score) {
        int[] answer = new int[score.length];
        k = k > score.length ? score.length : k;
        int[] hof = Arrays.copyOfRange(score, 0, k);
        int n = 0;
        
        for(int i = 0; i < k; i++) {
            if (i == 0) {
                answer[0] = score[0];
                n = answer[0];
            } else {
                n = score[i] < n ? score[i] : n;
                answer[i] = n;
            }
        }
        
        Arrays.sort(hof);
        
        for(int i = k; i < score.length; i++) {
            if (hof[0] < score[i]) {
                hof[0] = score[i];
                Arrays.sort(hof);
                answer[i] = hof[0];
            } else {
                answer[i] = hof[0];
            }
            
        }
        
        return answer;
    }
}

 

k = k > score.length ? score.length : k;

hof 배열 초기화하기 전에 이 한줄을 추가하니까 런타임 에러까지 해결됐다

 

명예의 전당 목록의 점수의 개수(k)가 출연한 가수들의 점수의 개수(score)보다 많을 수 있다는걸 고려하지 않았던거다. 명예의 전당 목록은 많은데 출연자가 적게 올 수도 있는거니까!!!

예를 들어 만약 k=15, score.length=13이라면        

for(int i = k; i < score.length; i++)  < 이부분에서 에러가 발생하는거다
그래서 hof 배열을 초기화하기 전에 k = k > score.length ? score.length : k; 를 이용해 k값이 더 클 경우 score.length와 맞춰주면 되는거였다 다양한 경우의 수를 생각해보며 풀어야겠음

 

틀리고 에러나고 헤매느라 시간이 오래 걸려서 답답했지만 해결하고나니까 뿌듯하다🤗🤗

 

 

다른 사람 풀이

-> 우선순위 큐로 대부분 많이 풀었다 엄청 간단하게 푸는듯,, 역시 자료구조를 확실히 공부해야하나보다

 

https://coderkoo.tistory.com/10

max-heap, min-heap - 이진트리의 활용

 

https://kbj96.tistory.com/49

[JAVA] PriorityQueue 우선순위 큐 사용법