Longest Consecutive Sequence - 리트코드

https://leetcode.com/problems/longest-consecutive-sequence

평가

결과 : 1회 실패 후 성공
풀이시간 : 첫 풀이 : 41분, 이후 5분 추가 소요

실패원인 : 비어있는 배열이 입력되는 경우를 생각하지 못했습니다.

아이디어

O(n)의 시간복잡도를 갖습니다.
그 말은 nums를 입력받는 동시에 한 큐에 처리해야 한다는 말입니다.

제가 생각한 아이디어는 다음과 같습니다.
num이 입력되는 순간, num의 왼쪽 숫자와 오른쪽 숫자를 확인하면서 길이를 갱신합니다.
말로 설명하면 참 어려우니 예시를 통해서 설명하겠습니다.

예시

[1,3,7,4,1,2] 순서대로 입력이 들어옵니다.

먼저 1이 들어옵니다. 현재 1의 자리는 비어있습니다.
1과 연결된 숫자는 0과 2입니다.

0과 2를 확인해보니 비어있습니다.
즉, 현재 1이라는 값을 통해 만들 수 있는 연속 숫자 묶음의 최대 길이는 1이 됩니다.

다음은 3이 들어옵니다. 3을 기준으로 2와 3 역시 비어있습니다.
즉, 3이 포함된 연속 숫자 묶음 의 최대 길이는 1입니다.

7 역시 동일하니 설명은 생략하겠습니다.

다음은 4가 들어옵니다.
4를 기준으로 왼쪽의 숫자인 3은 길이가 1입니다.
다시 말해, 4가 추가되면서 [3,4] 라는 숫자 묶음을 만들 수 있습니다.

3과 4의 위치에서 만들 수 있는 숫자 묶음의 길이는 2가 됩니다.
3에서 만들 수 있는 숫자묶음 크기(1) + 1개(추가된 값 4) == 2

다음은 1이 들어옵니다. 그런데 이미 1을 사용해 숫자 묶음이 만들어져 있으니, 해당 값은 무시합니다.

다음은 2가 들어옵니다.
2는 왼쪽과 오른쪽에 모두 숫자 묶음이 존재합니다.
2가 추가되면서 [1,2,3,4] 라는 숫자 묶음의 길이는 4가 됩니다.
1에서 만들 수 있는 숫자묶음 크기(1) + 3에서 만들 수 있는 숫자묶음 크기(3) + 1개(추가된 값 2) == 4

정리하면, 값을 넣을 때 왼쪽 값과 오른쪽 값을 이어주면서 숫자 묶음의 길이를 갱신해주면 됩니다.
[왼쪽 숫자 묶음 + 오른쪽 숫자묶음 + 1]

수도코드

왼쪽, 오른쪽 양쪽에 숫자 묶음이 존재하면 두 숫자 묶음을 하나의 묶음으로 변경해야 합니다.

객체를 변경하지 않고 단순하게 값만 바꾸면 아래와 같은 상황에서 문제가 생깁니다.

저는 포인터를 사용해 해결했는데요, 말로 설명하기가 참 어려운 부분입니다...
어떻게 해야 할지 감이 오지 않는다면 정답 코드에서 Length 클래스의 change, add 메서드를 보시는 걸 추천드립니다.

max = 0;
hash = new HashMap<>();
for (num: nums):
  // 양쪽 다 숫자묶음이 있을 때
  if hash.containsKey(num - 1) and hash.containsKey(num + 1):
    왼쪽숫자_묶음길이 = 왼쪽숫자묶음길이 + 오른쪽길이 + 1;
    현재위치_묶음길이 = 왼쪽숫자_묶음길이
    
	오른쪽숫자묶음 = 왼쪽숫자묶음으로 변경
    // (주의!) 오른쪽 숫자묶음과 왼쪽 숫자 묶음은 별개의 객체입니다.
    // 포인터를 사용해서 오른쪽 숫자묶음을 확인하면 왼쪽 숫자묶음을 사용하도록 변경해줘야 합니다.
    
  // 왼쪽 값을 확인
  else if hash.containsKey(num - 1):
	왼쪽숫자_묶음길이 += 1;
	현재위치_묶음길이 = 왼쪽숫자_묶음길이

  // 오른쪽 값을 확인
  else if hash.containsKey(num + 1):
	오른쪽숫자_묶음길이 += 1;
	현재위치_묶음길이 = 오른쪽숫자_묶음길이
    
  // 양쪽 다 없을때
  else:
	현재위치_묶음길이 = 1
    
  	max = Math.max(max, 현재위치_묶음길이);

정답 코드

class Solution {
    public int longestConsecutive(int[] nums) {
	    // -10억부터 10억의 범위를 갖기 때문에 배열을 만들 수 없습니다.
        // 배열 대신 Map을 사용해 연결을 확인합니다.
        Map<Integer, Length> hash = new HashMap<>();

        int max = 0; 
        for(int num: nums) {
            // 해당 위치에 값이 처음 나오면 왼쪽 오른쪽을 연결한다
            if (!hash.containsKey(num)) {
                // 둘 다 값이 있으면
                if (hash.containsKey(num - 1) && hash.containsKey(num + 1)) {

                    Length left = hash.get(num - 1);
                    Length right = hash.get(num + 1);

                    // left += (right + 1)
                    left.add(right.value + 1);

                    // right를 left로 변경합니다.
                    // 내부적으로 포인터처럼 연결해줍니다.
                    right.change(left);

                    // 나자신은 연결 값 그대로
                    hash.put(num, left);
                } else if (hash.containsKey(num - 1)) {
                    // 왼쪽으로 이미 연결된 값이 있으면 걔에 + 1
                    // 그리고 나도 왼쪽 녀석 값 넣기
                    Length left = hash.get(num - 1);
                    left.add(1);

                    hash.put(num, left);
                } else if (hash.containsKey(num + 1)) {
                    Length right = hash.get(num + 1);
                    right.add(1);

                    hash.put(num, right);
                } else {
                    // 아무것도 연결된 값이 없으면
                    hash.put(num, new Length(1));
                }
            }
            // 최대길이를 갱신
            max = Math.max(max, hash.get(num).value);
        }

        return max;
    }

    static class Length {
        int value;
        Length length;

        public Length(int value) {
            this.value = value;
        }

        public void add(int x) {
            if (length != null) {
                length.add(x);
                value = length.value;
            } else {
                value += x;
            }
        }
		
        public void change(Length length) {
            this.length = length;
        }        
    }
}