[Java / 코딩테스트] 최대 길이 연속수열

 

1. 생각

• 중복을 제거해야 하므로 Set을 쓰면 될거같은데
• 정렬을 해야하나? 
• nums의 길이가 300,000 이므로 시간복잡도를 최대한 적게 써야한다.
• 정렬 없는 HashSet으로 해결

 

2. 코드

import java.util.*;
class Solution {
    public int solution(int[] nums){
        int answer = 0;
        HashSet<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        for (Integer i : numSet) {
            if(numSet.contains(i-1)) continue;
            int cnt = 0;
            while (numSet.contains(i)) {
                cnt++;
                i++;
            }
            answer = Math.max(answer, cnt);
        }
        return answer;
    }

    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(T.solution(new int[]{8, 1, 9, 3, 10, 2, 4, 0, 2, 3}));
        System.out.println(T.solution(new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 0, 0, 0, 0}));
        System.out.println(T.solution(new int[]{3, 3, 3, 3, 3, 3, 3, 3}));
        System.out.println(T.solution(new int[]{-3, -1, -2, 0, 3, 3, 5, 6, 2, 2, 1, 1}));
        System.out.println(T.solution(new int[]{-5, -3, -1, -4, 3, 3, 5, 6, 2, 2, 1, 1, 7}));
        System.out.println(T.solution(new int[]{-5, -3, -1, -4, 3, 3, 5, 6, 2, 2, 1, 1, 7, 8, 9, 10, 11}));
    }
}

 

5
10
1
7
3
7