.leetcode(414. Third Maximum Number)

https://leetcode.com/problems/third-maximum-number/

 

1. 2022/04/26 시도

소요시간: 10분(array이용), 5분(priorityQueue이용)

// array
class Solution {
    public int thirdMax(int[] nums) {
        Arrays.sort(nums);

        // remove duplicated
        int prev = nums[0];
        int index = 1;
        for (int i=1; i<nums.length; i++) {
            if (prev == nums[i]) {
                continue;
            }
            prev = nums[i];
            nums[index++] = nums[i]; 
        }

        if (index < 3) {
            return nums[index-1];
        }
        
        return nums[index-3];
    }
}

// priorityQueue
class Solution {
    public int thirdMax(int[] nums) {
        Set<Integer> set = new HashSet<>();
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        for (int each: nums) {
            if (set.contains(each)) {
                continue;
            }
            set.add(each);
            pq.offer(each);           
        }
        
        if (pq.size() < 3) {
            return pq.poll();
        }
        
        pq.poll();
        pq.poll();
        return pq.poll();
    }
}

풀이 접근 과정

배열(array)이용한 풀이
- 일단 정렬하고 중복을 제거해준다. index에 최대 길이값이 저장된다.
- 3개 미만일때는 max값인 nums[index-1]을 리턴한다.
- 3개 이상일 때는 3번째 max값인 nums[index-3]을 리턴한다.

우선순위큐(priorityQueue)이용한 풀이
- 중복은 set으로 제거한다.
- 우선순위 큐에 저장할 때, 순서는 큰거가 위로 오도록 한다.(Collections.reverseOrder())
- 길이가 3이 안되면 첫번째 poll()해서 max값을 리턴하고, 길이가 3이 되면 3번 poll()해서 리턴한다.

 

느낀점

• 핵심은 중복을 어떻게 제거할 것인가라고 보인다. 배열은 배열알고리즘에서 배웠듯이 in-place로 덮어씌우는 방법이다. 그리고 전통적으로 set을 이용한 중복제거 방법도 사용해보았다.
• int[] 를 내림차순으로 정렬하려고 Arrays.sort(new int[]{1,2,3}, Collections.reverseOrder())를 사용하려고 하였는데, primitive는 안되고 쓰고 싶다면 Arrays.sort(new Integer[]{1,2,3}, Collections.reverseOrder())로 사용할 수 있다. 근데 완전 별로라고 생각해서 위에서 배열로 풀 때는 index를 뒤에서 부터 읽도록 코딩하였다.

 

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형