코테를 위한 기본 알고리즘: 배열 요소의 곱 구하기

안녕하세요! 개발자 여러분, 알고리즘을 공부하시는 여러분들을 환영합니다. 오늘은 "배열 요소의 곱 구하기"라는 주제로 알고리즘 풀이를 다루어보려고 합니다. 이번 포스트에서는 제공된 코드를 기반으로 문제를 이해하고, 해당 문제를 해결하기 위한 효율적인 알고리즘에 대해 알아보겠습니다.

 

바로 아래 정보에서 공부해봅시다!

기본 알고리즘 로고

문제 내용

주어진 문제는 정수로 이루어진 배열이 주어졌을 때, 각 요소를 제외한 나머지 요소들의 곱을 구하는 것입니다.

 

문제 이해하기

우리에게 주어진 문제는 정수로 이루어진 배열 **nums**가 주어진다고 합니다. 이 배열에서 각 요소를 제외한 나머지 요소들의 곱을 구해야 합니다. 예를 들어, **nums = [1, 2, 3, 4]**라면, 결과적으로 **[24, 12, 8, 6]**을 반환해야 합니다.

 

풀이 코드

이제 주어진 문제를 해결하기 위한 코드를 살펴보겠습니다. 제공된 코드를 통해 문제를 풀어보도록 하겠습니다.

pythonCopy code
from typing import List

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        out = []
        p = 1
        # 왼쪽 곱셈
        for i in range(0, len(nums)):
            out.append(p)
            p = p * nums[i]
        p = 1
        # 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈
        for i in range(len(nums) - 1, 0 - 1, -1):
            out[i] = out[i] * p
            p = p * nums[i]
        return out

풀이 방법

주어진 문제를 해결하기 위해 위의 코드는 두 단계로 나누어 진행합니다. 첫 번째 단계는 왼쪽 곱셈(L)을 수행하는 것이고, 두 번째 단계는 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱셈(R)하는 것입니다.

 

왼쪽 곱셈 (L)

첫 번째 단계에서는 왼쪽 곱셈을 수행하여 out 리스트에 값을 저장합니다. 이를 위해 out 리스트와 곱셈을 나타내는 변수 **p**를 초기화합니다. 그리고 주어진 배열 **nums**를 왼쪽부터 순회하면서 out 리스트에 **p**를 추가하고, **p**를 현재 요소 **nums[i]**와 곱하여 갱신합니다. 이 과정을 반복하면서 왼쪽 곱셈이 완료됩니다.

 

오른쪽 곱셈 (R)

두 번째 단계에서는 왼쪽 곱셈 결과에 오른쪽 값을 차례대로 곱하여 최종 결과를 얻습니다. 이를 위해 오른쪽 곱셈을 수행하는 변수 **p**를 초기화합니다. 그리고 주어진 배열 **nums**를 역순으로 순회하면서 out 리스트의 요소들과 **p**를 곱하여 out 리스트를 갱신합니다. 이 과정을 반복하면서 오른쪽 곱셈이 완료됩니다.

최종적으로 왼쪽 곱셈과 오른쪽 곱셈을 통해 얻은 out 리스트가 문제에서 요구하는 결과입니다.

시간 복잡도

해당 알고리즘의 시간 복잡도는 O(n)입니다. 왼쪽 곱셈과 오른쪽 곱셈을 각각 한 번씩 수행하므로, 배열의 길이에 비례하는 선형 시간이 소요됩니다.

이렇게 주어진 문제를 해결하기 위한 알고리즘 풀이를 소개해드렸습니다. 코딩 인터뷰나 코딩 테스트에서 배열 요소의 곱을 구하는 문제는 자주 출제되는 유형 중 하나이므로, 이번 포스트가 도움이 되었기를 바랍니다. 감사합니다!

 

혹시 문제가 잘 안풀리고 답답하신가요? 아래를 눌러 백준 알고리즘 트랜드와 기출문제를 알아보세요! 이것만 알아도 네카라뿌십니다~

 

👉 백준 알고리즘 모음

 

 

백준이 너무 어렵다면 아주 기본 코딩테스트 알고리즘을 먼저 도전해보세요~

 

👉 기본 코딩테스트 문제보기