인프런 커뮤니티 질문&답변

현이님의 프로필 이미지

작성한 질문수

자바 코딩테스트 - it 대기업 유제

1. "최대 길이 연속수열" 문제 해법

최대 길이 연속수열 질문

24.05.01 17:48 작성

·

97

0

정답의 경우 아래와 같이 되어있습니다.

public int solution(int[] nums){
    int answer = 0;
    HashSet<Integer> set = new HashSet<>();
    for(int x : nums) set.add(x);
    for(int x : set){
        if(set.contains(x - 1)) continue;
        int cnt = 0;
        while(set.contains(x)){
            cnt++;
            x++;
        }
        answer = Math.max(answer, cnt);
    }
    return answer;
}

제가 푼 방식 : set으로 중복되지 않은수만 우선순위 큐(pQ)에 넣어 계산.

  • 물론 풀이에서의 코드가 간결하고 사용하는 자료형도 적으니 좋은 코드같습니다만은 이렇게 풀었을때 시간 복잡도 면에서도 많이 불리한지 피드백 부탁드립니다.

public int solution(int[] nums){
    int answer = 1 , cnt=1;
    PriorityQueue<Integer> pQ= new PriorityQueue<>();
    HashSet<Integer> set = new HashSet<>();
    for(int i : nums){
        if(!set.contains(i)) pQ.offer(i);//
        set.add(i);
    }
    int N = pQ.poll();
    while ( !pQ.isEmpty() ){
        int nextN = pQ.poll();
        if( N+1 == nextN ){
            cnt++;
            N = nextN;
        }
        else if( N+1 != nextN ) {
            cnt = 1;
            N = nextN;
        }
        answer=Math.max(answer,cnt);
    }
    return answer;
}

답변 1

0

인프런 AI 인턴님의 프로필 이미지

2024. 05. 03. 17:51

안녕하세요, 인프런 AI 인턴입니다.

제시하신 코드의 시간 복잡도에 대해 피드백 드리겠습니다.

기존 해법에서는 HashSet을 사용하여 각 원소가 존재하는지 확인하는 과정에서 O(1)의 시간 복잡도를 가집니다. 그리고 모든 원소에 대해 한 번씩만 확인하기 때문에 전체 시간 복잡도는 주어진 배열의 크기인 N에 대하여 O(N)이 됩니다.

반면, 우선순위 큐(PriorityQueue)를 사용한 귀하의 접근 방식에서는, 우선 PriorityQueue에 원소를 추가하는 과정에서 N개의 원소 각각에 대해 O(log N)의 시간이 소요됩니다. 따라서 전체적으로 N개의 원소를 큐에 추가하는 데 O(NlogN)의 시간이 소요됩니다. 추가적으로, PriorityQueue에서 원소를 추출하면서 최대 길이 연속 수열을 구하는 과정은 O(NlogN) 안에 완료됩니다.

결론적으로, 우선순위 큐를 사용한 귀하의 방식은 기존 해법에 비해 시간 복잡도 면에서 불리합니다. 기존 해법은 O(N)에 처리가 가능한 반면, 귀하의 방식은 O(NlogN)에 처리되기 때문입니다. 따라서 대량의 데이터를 처리할 경우, 우선순위 큐를 사용한 방식보다는 HashSet만을 사용한 방식이 효율적일 수 있습니다.

현이님의 프로필 이미지

작성한 질문수

질문하기