1월4일 문제 풀기

2244. Minimum Rounds to Complete All Tasks

0번 부터 시작하는 인덱스가 주어지고 한번의 테스크는 2,3 개 만 이루어진다. 동일한 레벨 만 동시에 작업할수 있다.

최소 라운드 를 구해라 만약 없다면 -1 을 리턴 하라는 문제이다.

 

최대 갯수가 10000 개 밖에 되지않는다.

 

Map 을 이용해 저 숫자들 을 분류하고, bfs 를 이용해 최소 라운드 를 찾아갈 생각을 했다.

 

class Solution {
    public int minimumRounds(int[] tasks) {
        Map<Integer,Integer> map = new HashMap();
            for(int a:tasks){
                Integer b = map.getOrDefault(a,0);
                map.put(a,b+1);
            }

            int round = 0;
            for(Map.Entry<Integer,Integer> entry : map.entrySet()){
                Integer value = entry.getValue();
                if(value < 2) return -1;
                int calculate = calculate(value);
                if(calculate < 0) return -1;
                round += calculate;
            }

            return round;
    }

    private int calculate(Integer value) {
            int round =0;
            boolean found = false;

            Queue<Integer> q = new ArrayDeque<>();
            Set<Integer> set = new HashSet();
            q.add(0);

            while(!q.isEmpty()){
                int size = q.size();
                for(int i =0;i<size;i++){
                    int poll = q.poll();

                    int a = poll + 2;
                    if( a == value) return round+1;
                    int b = poll + 3;
                    if( b == value) return round+1;

                    if(a < value && set.add(a)) q.offer(a);
                    if(b < value && set.add(b)) q.offer(b);
                }
                round++;
            }

            return found ? round : -1;
        }
}

이렇게 작성했더니 무려 126ms 나 나와버렸더 무진장 느리다 ...  아무래도 저 bfs 부분이 문제인거 같은데 나름 최적화 가 되어있다고 생각하는데 이렇게 느린걸 보면 다른 규칙이 있는것 같다.

1번	2,3
2번	4,5,6
3번	7,8,9
4번	10,11,12

연산 을 한번 두번 .... 했을때 중복 값을 제외하고 나올 경우의 수를 작성해 보면 위와 같다. 파란색으로 마킹된 부분을 살펴보자. 

모두 3의 배수이다. 2,3 을 이용한다면 모든수 를 작성할수 있다 단 1 인 경우를 제외한다면 이다. caculate 함수 부분을 변경하자.

    private int calculate(Integer value) {
        if(value%3 == 0) return value/3;
        return (value/3)+1;
    }

좋다 이렇게 변경하니 속도가 개선 되었으나 여전히 36ms 로 상위 19% 이다. 많이 느리다. 어떤 부분을 놓친걸까...

 

class Solution {
    public int minimumRounds(int[] tasks) {
        Arrays.sort(tasks);
        int round = 0;
        int cnt = 1;
        if(tasks.length < 2) return -1;

        for(int i=1;i<tasks.length;i++){
            if(tasks[i-1] != tasks[i]){
                if(cnt < 2) return -1;
                round += calculate(cnt);
                cnt =1;
            }else{
                cnt++;
            }
        }
        
        if(cnt < 2) return -1;
        else round += calculate(cnt);

        return round;
    }

    private int calculate(Integer value) {
        if(value%3 == 0) return value/3;
        return (value/3)+1;
    }
}

 

로직을 변경해 배열을 정렬하고 for loop 으로 로직 변경 => 10ms  98.8% 까지 나왔다.

 

음 ? 다른사람의 풀이도 별반 다르지 않다... 다 이런 2가지 방식으로 풀었다.

 

83. Remove Duplicates from Sorted List

연결 노드상 에서 중복된 값을 지워주는 로직을 구현하면 된다. 재귀 를 노드 의 마지막 까지 이동을 하고

현재 헤드 기준으로 헤드 의 다음을 계속 업데이트 해주면서 날려주는 로직을 재귀 안에 구성하면 될것같다.

 

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        helper(head);
        return head;
    }
    public void helper(ListNode head){
        if(head == null || head.next == null) return;
        while(head.next != null && head.val == head.next.val){
            ListNode next = head.next;
            if(next == null){
                head.next = null;
                break;
            }
            head.next = next.next;
        }
        helper(head.next);
    }
}

null 체크 를 제대로 하지않아서 nullPointer exception 을 여러번 맞았다 ㅎㅎㅎ... while 을 next 의 null 까지 돌리지 않는다면 

1,1,1,1,1,1,1 케이스 에서 1,1 로 반환되는 불상사가 발생한다. 주의 하자

Solution 중에 가독성 좋은 코드가 있어서 가져와 봤다.

public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode list = head;
         
         while(list != null) {
        	 if (list.next == null) {
        		 break;
        	 }
        	 if (list.val == list.next.val) {
        		 list.next = list.next.next;
        	 } else {
        		 list = list.next;
        	 }
         }
         
         return head;
    }
}

while 을 이용해서 loop 를 돌리는게 확실히 재귀보다 직관적 이다.

 

1619. Mean of Array After Removing Some Elements

정렬하고 5% 계산해서 평균 구해주면 되는 Easy 난이도 에 맞는 문제이다.

class Solution {
    public double trimMean(int[] arr) {
        Arrays.sort(arr);
        int cut = (int) ((double) arr.length * 0.05);
        double sum = 0;
        for(int i = cut;i<arr.length-cut;i++){
            sum+=arr[i];
        }
        return sum/(arr.length-(cut*2));
    }
}

 

깔끔한 코드 20 개 의 배수가 주어진다는 문제의 요구사항에 따라 미리 20 을 나눠서 계산하는 모습이 인상적이다.

    public double trimMean(int[] arr) {
        int n = arr.length;
        double sum = 0d;
        Arrays.sort(arr);
        for (int i = n / 20; i < n - n / 20; ++i) {
            sum += arr[i];
        }
        return sum / (n * 9 / 10);
    }