[leetcode] Third Maximum Number

https://leetcode.com/explore/learn/card/fun-with-arrays/523/conclusion/3231/

Explore - LeetCode

Success

 

해당 문제는 배열이 주어졌을 때 세번째로 큰 값을 리턴하는 문제이다.

이때 배열의 길이가 3보다 작을경우엔 가장 큰 값을 리턴하며, 중복된 원소는 하나의 원소로 취급하면 된다. 

 

먼저 배열을 오름차순으로 정렬한 후, 배열 내의 중복된 원소를 제거하였다. 

중복된 원소를 제거하는 방식은 투 포인트 방식을 사용하였고,  j의 인덱스까지만 중복이 제거 원소로 다시 채워지게된다. 

이 과정에서 새로운 자료구조를 사용하지 않아 공간에 대한 메모리는 줄일 수 있었다. 

class Solution {
    public int thirdMax(int[] nums) {
        if (nums == null) return -1;

        // 정렬
        Arrays.sort(nums);

        int j=0;
        // 중복제거
        for (int i=0; i<nums.length; i++) {
            if (nums[j] != nums[i]) {
                nums[j+1] = nums[i];
                j++;
            }
        }

        // 중복이 제거된 값만 가져온다.  
        // j 까지만 값을 가져오면 된다.
        if (j<2) {
            return nums[j];
        }

        return nums[j-2];
    }
}

 

다른 풀이 방법으로는

 

1. Set을 이용하여 중복을 없애고, 최대값을 구하고 지우고 과정을 2번 거쳐 세번째 최대값을 구하는 방법

 

2. Set을 이용하여 배열의 원소를 Set으로 add 를 시킨다. 이 때 Set 안의 원소의 개수는 3 으로 유지하기 위해 원소의 개수가 3 이상이 되면 Set 내에 제일 작은 작은 값을 지우며 계속해서 add 작업을 진행한다. 배열의 원소를 다 옮긴 후 Set 안에는 가장 큰 값 3개만 남았을 것이고 여기서 가장 작은 값을 리턴하는 방법이 있다.