8. Product of Array Except Self and Longest Consecutive Sequence

 

코딩테스트를 준비하는 과정에서 자주 마주치는 대표적인 배열 문제 두 가지를 다루고자 한다. 각각의 문제를 어떤 아이디어로 접근해야 하는지, 코드를 외우기보다는 어떤 흐름으로 이해하고 적용해야 하는지를 중심으로 정리했다.

---

🔹 문제 1: Product of Array Except Self

🧠 문제 설명

• 정수 배열 nums가 주어졌을 때,
• answer[i]는 nums[i]를 제외한 나머지 모든 값의 곱이 되도록 하라.
• 단, O(n) 시간 복잡도, 나눗셈 사용 금지 조건이 있다.

🔍 핵심 아이디어

• 현재 인덱스를 제외한 곱을 만들기 위해 좌측 곱 (prefix) 과 우측 곱 (suffix) 을 따로 계산한다.
• 최종적으로 answer[i] = left[i] * right[i]

✅ 코드

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        answer = [1] * n

        left = 1
        for i in range(n):
            answer[i] = left
            left *= nums[i]

        right = 1
        for i in reversed(range(n)):
            answer[i] *= right
            right *= nums[i]

        return answer

📌 설명

• left 루프는 왼쪽에서부터 곱을 누적하며 현재 인덱스를 제외한 왼쪽 누적곱 저장
• right 루프는 오른쪽에서부터 곱을 누적하여 오른쪽 누적곱을 곱해줌
• 최종적으로 모든 인덱스에 대해 자기 자신을 제외한 곱이 계산됨

💡 참고 키워드: Prefix product, Suffix product, O(n) without division

---

🔹 문제 2: Longest Consecutive Sequence

🧠 문제 설명

• 정수 배열 nums가 주어졌을 때,
• 연속된 숫자들의 가장 긴 수열 길이를 반환하라.
• 숫자는 정렬되지 않았고, 중복이 있을 수 있다.

📥 예시

Input: [100, 4, 200, 1, 3, 2]
Output: 4 (1, 2, 3, 4)

🔍 핵심 아이디어

• 모든 수를 set()에 넣고, 현재 숫자가 시퀀스의 시작점인지 확인
• num - 1이 존재하지 않는다면, num은 시퀀스의 시작
• 이후 연속된 수 (num+1, num+2, ...)가 있는지 확인하며 길이 증가

✅ 코드

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        num_set = set(nums)
        longest = 0

        for num in num_set:
            if num - 1 not in num_set:
                length = 1
                while num + length in num_set:
                    length += 1
                longest = max(longest, length)

        return longest

📌 설명

• set을 사용해 O(1) 시간 안에 존재 여부를 체크
• 연속된 숫자가 얼마나 이어지는지 while 문으로 확인
• 시퀀스의 시작점만 탐색하므로 전체 시간 복잡도는 O(n)

💡 참고 키워드: Set lookup, greedy start-point check, O(n) scan

---

🔁 외워도 될까? 아니면 이해가 우선일까?

• 외우는 건 처음엔 OK. 하지만 이해 없인 한계가 명확하다.
• 실제 코딩 테스트나 면접에서는 문제가 살짝만 바뀌어도 고전하게 된다.
• 따라서, 아래와 같은 루틴으로 학습하는 것이 좋다:

📘 추천 학습 루틴

1. 문제 풀기 → 틀리면 해설 보기
2. 코드 한 줄 한 줄 주석 달기 (이해 중심)
3. 내 말로 정리해서 블로그/노션 정리하기
4. 비슷한 문제 다시 풀어보기