[알고리즘 스터디 3주 차(2)] 더 맵게

 

 

코딩테스트 연습 - 더 맵게

 

 

내가 생각한 로직 -> 노력은 ... 가상했다..

 

1. sort를 해서 배열을 오름차순으로 정렬한다.

2. i [0] 번째 인덱스 (=가장 작은 값)과 i[1]번째 인덱스(=두번째로 작은 값)을 계산한다.

3. 전역 변수로 선언한  count를 증가시킨다. (=섞는 총 횟수)

4. 2번에서 도출된 값을 i[0]번째 인덱스에 대입한다.

5. 만약 i번째 인덱스의 값이 K보다 작을 경우 continue로 다시 위의 반복을 수행한다.

6. 종료되는 시점은 K의 값보다 작을 경우이다.

 

import java.util.Arrays;

class Solution {
    public int solution(int[] scoville, int K) {
        
        Arrays.sort(scoville);
        int count = 0;
        int mix;
      
        for(int i=0;i<scoville.length;i++){
            if(scoville[0]<K){
                mix = scoville[0] + (scoville[1]*2);
                scoville[0] = mix;
                count++;
                continue;
            }
        }
    
        return count;
    }
}

 

테스트 케이스는 통과했지만, 결과는 오답이다.😂

 

👏 박수 타임 

바로 코딩에 착수하기 전에 로직을 짜서 구현해보았다.

얼레벌레이지만 그래도 지난번에 배운 sort도 사용해보고, 반복문, 조건식도 사용해봤다.

 

 

Array로는 점점 줄어드는 배열을 취급할 수 없다. 왜? 배열은 크기를 바꿀 수 없으니까!

 

풀이 1

 

1. 그래서 위의 배열을 List에 담아주었다.
2. sort를 한다. (List는 Collection.sort를 하면 된다.)
3. 그리고 루프를 사용해서 0번째 인덱스가 K보다 크다면 반복문을 종료시킨다.
4. 0번째 인덱스가 K보다 작다면, 반복문 안에 들어온다.
5. 이때 remove 메소드를 이용해서 가장 값은 값과 두 번째로 작은 값들을 추출하고, 그 값을 각각  d1과 d2에 담아 문제에서 요구한 대로 계산한다. 
6. 그리고 섞은 횟수인 count를 증가해주고, 새로운 배열을 기준으로 다시 sorting 해준다.
7. 마찬가지로 0번째 인덱스의 값이 K보다 작으면 다시 반복문이 실행된다.
8. 만약 0번째 인덱스가 K보다 크다면 반복문이 종료되어 섞은 횟수가 반환된다.

 

import java.util.List;
import java.util.Collections;
import java.util.LinkedList;

class Solution {
    public int solution(int[] scoville, int K) {
        
        List<Integer>dishes = new LinkedList<>();
        for(int s : scoville) dishes.add(s);
        
        Collections.sort(dishes);
        int count = 0;
        
        while(dishes.get(0) < K){
            if(dishes.size()<2) return -1;
            
            int d1 = dishes.remove(0);
            int d2 = dishes.remove(0);
            int mix = d1 + d2*2;
            dishes.add(mix);
            count++;   
            Collections.sort(dishes);
         }
        return count;
    }
}

 

실행 결과 O 효율성 테스트 X

 

이번의 문제점은 효율성 테스트 🤣

 

 

💡 튀김 선생님의 TIP

코테 풀다가 효율성 테스트에서 걸리면, 75점이라도 풀어놓고 다른 문제로 넘기자.

효율성 문제 때문에 다른 문제 다 틀리지 말고 부분점수라도 받자!

 

 

효율성 문제를 해결하는 방법

1. 병목지점을 찾는다. -> 대부분 루프 안에 있다.
2. 그곳을 더 빠른 것으로 대체한다.

 

1. 병목지점을 찾는다.

병목지점은 바로 22번째 라인이다.

 

 

그 이유는 반복문이 돌아갈 때마다 sort를 하기 때문에, sort의 시간 복잡도는 O(nlogn)이고, 반복문의 시간 복잡도는 O(n)이므로 해당 반복문의 시간 복잡도는 O(n^2 longn)이 된다. 따라서 22번째 라인을 O(nlogn)보다 시간 복잡도가 빠른 것으로 바꿔주면 된다. 

 

O(nlogn)보다 시간 복잡도가 빠른 것은?
O(n), O(logn), O(1) 

 

루프가 숨어있는 것을 찾아야 한다. sort안에도 루프가 숨어있다.

따라서, 내부구조를 아는 것이 중요하다 -> 자료구조 공부하자 😂

 

 

2. 더 빠른 것으로 대체한다.

 

데이터를 넣자마자 자동으로 정렬되는 자료구조가 없을까? 🤔

 

HEAP을 사용해보자!

(linked list > graph > tree > binary-tree  > heap > minimum-tree)

 

HEAP 구현할 수 없으니 Java에서 제공하는 Heap을 사용해보자!

Java 언어를 사용한다는 것은 - Java에서 기본으로 제공하는 패키지를 잘 쓸 수 있다는 것이다!

java.lang.*과 java.util.*에 뭐가 있는지를 파악하자! 자바 뽕뽑기 !

 

 

import java.util.List;
import java.util.Collections;
import java.util.Queue;
import java.util.PriorityQueue;

class Solution {
    public int solution(int[] scoville, int K) {
        
        Queue<Integer>dishes = new PriorityQueue<>();
        // 디폴트가 m-heap이기 때문에 가장 작은 값이 맨 앞으로 정렬된다.
        for(int s : scoville) dishes.add(s);
        
        int count = 0;
        
        while(dishes.peek() < K){
            if(dishes.size()<2) return -1;
            
            int d1 = dishes.poll();
            int d2 = dishes.poll();
            int mix = d1 + d2*2;
            dishes.offer(mix);
            count++;   
         }
        return count;
    }
}

 

 

이렇게 풀면 효율성 테스트까지 통과된다.

 

😝 배운 점

문제를 풀지는 못했지만, 로직이 얼추 비슷해서 너무 뿌듯했다. PriorityQueue라는 메소드도 알게 되었다. 

학원에서 java.util, java.lang 패키지에 있는 메소드들 알아두면 좋다고 하셨던 이유가 이것 때문이구나 깨달았던 순간이었다. 자바에서 제공하는 기본적인 메소드들을 적극적으로 뽕뽑 해봐야겠다.