[프로그래머스][Level2][Java] 더 맵게

문제

 

풀이코드

처음 내가 풀었던 코드

public int solution(int[] scoville, int K) {
    List<Integer> list = new ArrayList<>();
    int answer = 0;
    int min = 0;
    for(int x : scoville){                      //스코빌 지수를 list에 새로 대입
        list.add(x);
    }
    while(list.size() > 0){                     //list의 크기가 0이 될때까지 반복
        Collections.sort(list);                 //list를 오름차순으로 정렬
        if(list.get(0) >= K){                   //list에서 제일 작은 값이 K이상이면 반복문 탈출
            break;
        }else if(list.size() != 1){             //list에서 제일 작은 값이 K보다 작고, list의 크기가 1이 아닐경우
            min = list.get(0) + list.get(1)*2;  //제일 작은 값 + 그 다음 작은 값*2를 min에 넣는다.
            list.add(min);                      //그리고 min값을 다시 list에 추가
            list.remove(0);               	//그리고 섞었던 값들을 list에서 빼준다.
            list.remove(0);
            answer++;                           //섞은 횟수 추가
        }else{                                  //list에서 제일 작은 값이 K보다 작고, list의 크기가 1일 경우
            answer = -1;                        //답이 나오지 않으므로 -1을 return하고
            break;                              //반복문 탈출
        }
    }
    return answer;
}

처음 풀었던 코드는 이것인데 결과는

보다시피 정확성 테스트는 모두 통과를 하였으나 효율성 테스트에서 모두 시간초과가 뜨고 말았다...

그래서 아무래도 원래의 스코빌 배열에서 ArrayList에 넣는 반복문과 while반복문, 이 두가지가

시간초과가 되는 원인이 되는 것 같아서 다시 코드를 리팩토링을 해봤다.

 

처음엔 저 문제가 힙 유형으로 되어 있어서 힙으로 생각도 해봤는데 힙의 개념만 알지 어떻게 쓰는 것인지를 그동안 몰랐었다. 근데 힙이 우선순위 큐라는 개념을 가지고 풀길래 우선 순위 큐에 관한 내용들을 정리해서 다시 풀어봤다.

https://github.com/crupy/TIL/blob/master/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/%EC%9D%B4%EB%A1%A0/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0.md

GitHub - crupy/TIL: Today I Learned. 하루하루 공부한 내용들을 정리

힙과 우선순위 큐에 대한 내용은 간단하게 여기에 정리해두었다.

 

다시 푼 코드

public int solution(int[] scoville, int K) {        //더 맵게
    int answer = 0;
    PriorityQueue<Integer> list = new PriorityQueue<>();
    for(int x : scoville){                      //스코빌 지수를 list에 새로 대입
        list.add(x);
    }
    while(list.size()>0){                       //list의 갯수가 1개 이하로 떨어질 때까지 반복
        if(list.peek()>=K){                     //list에서 제일 작은 값이 K이상일 때, 반복문 탈출
            break;
        }else{                                  //list에서 제일 작은 값이 K보다 작을 때,
            if(list.size()==1){                 //만약 list의 크기가 1이면 끝까지 섞었는데도 답이 안나온 것이므로 -1반환환
                return -1;
            }
            int s1 = list.remove();             //제일 작은 값을 list에서 제거하고 s1에 저장
            int s2 = list.remove();             //두번째로 작은 값을 list에서 제거하고 s2에 저장
            int mix = s1 + s2*2;                //s1,s2를 정해진 법칙에 따라서 섞음
            list.add(mix);                      //섞은 값을 다시 list에 대입
            answer++;                           //섞은 횟수 추가
        }
    }

    return answer;
}

이렇게 푸니까 반복할 부분도 1개 줄었고 효율성 테스트도 통과를 하였다!!!

우선순위 큐라는 개념은 앞으로도 유용하게 쓰일 것 같다!