위메프 면접 스크립트의 추억. (릿코드 414. Third Maximum Number)

과거 위메프에 다닐때 면접관이나 스크립터로 면접에 자주 참여하였었는데, 팀장님께서 탈락할 것 같은 인원에게 마지막 찬스 비슷하게 내던 문제가 Leetcode에서 나와서 신기하여 포스팅 해본다. 

 

문제는 약간 다르지만, 거의 같은문제의 수준이다. 그때 묻던 문제는 다음과 같다.

 

문제

무작위 배열이 있을때, distinct하게 10번째로 큰 수를 출력하도록 하려면 어떤식으로 알고리즘을 짤 것인가? 

 

화상면접 특성상 입코딩 + 압박감 때문에 10 ~ 20분내에 풀어냈어야 하므로 면접자들은 더 어려운 상황이었을 것이다. 

많은 사람들이 답을 잘 못하였고, 알고리즘을 좀 풀어본 사람들은 정렬후 세번째 숫자를 출력하는 정도로 말하였던것 같다. 

 

하지만, 추가적인 문제로 정렬을 사용하지 않고 풀려면 어떻게 해야할까가 문제의 관건이었다. 당시 내 머릿속으로도 문제를 풀어봤는데, 

내 생각은 크기 10짜리 List를 따로두고 배열을 훑으면서 크기 10짜리 배열안에 든 수보다 큰 수가 들어오면 배열의 값을 빼고, 아닐 경우 배열에 값을 넣지않는? 그런 방식이다. 

 

릿코드 문제의 경우 3번째로 큰 값을 구하라기에 그때 생각한 방식과 비슷하게 아래와 같이 풀어보았다.

class Solution {
    public int thirdMax(int[] nums) {
        List<Integer> list = new LinkedList<>();

        for (int i = 0; i < nums.length; i++) {
            if (!list.contains(nums[i])) {
                tryAddValue(list, nums[i]);
            }
        }

        return list.size() < 3 ? list.get(list.size() - 1) : list.get(0);
    }

    public void tryAddValue(List<Integer> list, int num) {
        if (list.size() < 3) {
            for (int i = list.size() - 1; i >= 0; i--) {
                if (list.get(i) < num) {
                    list.add(i + 1, num);
                    return;
                }
            }
            list.add(0, num);
        } else {
            for (int i = list.size() - 1; i >= 0; i--) {
                if (list.get(i) < num) {
                    list.remove(0);
                    list.add(i, num);                    
                    return;
                }
            }
        }
    }
}

 

풀이결과 아래와같이 순위가 뜬다.

 

그런데,,, 여러 풀이법이 있었는데 개인적으로 놀란 풀이법은.. TreeSet이라는 알고리즘을 이용해서 풀어낸 녀석.. 

아침부터 굴욕감을 맛보고 미친xx 라는 혼잣말을 하게된다.

class Solution {
    public int thirdMax(int[] nums) {
        TreeSet<Integer> ts = new TreeSet<>();
         for (int i : nums){
             ts.add(i);
         }
          if (ts.size()>=3){
              ts.pollLast();
              ts.pollLast();
          }
             System.gc();
             return ts.last();
    }
}