[Q. 11] 자신을 제외한 배열의 곱

2023. 3. 21. 13:59·코딩테스트/알고리즘
배열을 입력받아 output[i]가 자신을 제외한 나머지 모든 요소의 곱셈 결과가 되도록 출력하라.
- 주의 : 나눗셈을 하지 않고 O(n)에 풀이하라.

 

이 문제를 보고 맨처음 든 생각은 전체곱에서 나누는 것이다. 그런데 나눗셈을 하면 안된다고 적혀있으니 다음 방법은 본인을 제외한 모든 수를 곱하는 것인데 이 또한 n 제곱의 시간이 걸리므로 불가능 하다.

 보통 이러할 때 쓸 수 있는 방법은 시간 대신 메모리를 쓰는 것이다. 본인의 왼쪽까지의 순차적으로 누적 곱을 저장한 배열과 본인의 오른쪽 까지의 순차적으로 누적 곱을 저장한 값을 활용하여 문제를 풀이한다.

 

예를들어, [1,2,3,4] 라는 배열이 있다고 가정하자.

먼저 자신의 왼쪽 까지의 순차적 곱을 정리한 배열은 [1, 1, 2, 6]이 될 것이다. 그리고 자신의 오른쪽 까지의 순차적 곱을 정리한 배열은 [24, 12, 4, 1] 이 될 것이다. 이 두 배열을 곱하면 각 자리(i)에서 자신을 제외한 나머지 모든 요소의 곱셈의 결과인 [24, 12, 8, 6]이 될 것이다.

이를 구현해보자. 먼저 결과를 저장할 out 배열에 1을 추가해주고, 오른쪽 순차 곱을 저장할 p 변수를 1로 초기화해준다.

out = []   
p = 1
out.append(1)

 

그 다음 본인의 왼쪽까지의 곱셈결과를 out 배열에 저장한다.

for i in range(len(nums)-1):
    out.append(out[-1] * nums[i])​

 

그 다음 본인의 오른쪽까지의 곱셈결과를 변수 p에 저장하고, 그 결과를 활용하여 out 결과를 도출한다.

for i in range(len(nums)-1, -1, -1):
    out[i] *= p
    p *= nums[i]

 

전체 코드는 다음과 같다.

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        out = []
        
        p = 1
        out.append(1)

        for i in range(len(nums)-1):
            out.append(out[-1] * nums[i])

        for i in range(len(nums)-1, -1, -1):
            out[i] *= p
            p *= nums[i]

        return out
저작자표시 비영리 변경금지 (새창열림)

'코딩테스트 > 알고리즘' 카테고리의 다른 글

[Q. 13] 팰린드롬 연결 리스트  (0) 2023.03.21
[Q. 12] 주식을 사고팔기 가장 좋은 시점  (0) 2023.03.21
[Q. 10] 배열 파티션 1  (0) 2023.03.20
[Q. 09] 세 수의 합  (0) 2023.03.20
[Q. 08] 빗물 트래핑  (0) 2023.03.20
'코딩테스트/알고리즘' 카테고리의 다른 글
  • [Q. 13] 팰린드롬 연결 리스트
  • [Q. 12] 주식을 사고팔기 가장 좋은 시점
  • [Q. 10] 배열 파티션 1
  • [Q. 09] 세 수의 합
뚝딱뚝딱2
뚝딱뚝딱2
  • 뚝딱뚝딱2
    개발도상국
    뚝딱뚝딱2
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 공부
        • Java
        • Spring Boot
        • LORA
      • Web
        • 인스타 클론 코딩
        • GPT 응답 API 서버
        • Spring Boot 예외 처리
        • 코테 준비용 서비스 만들기
      • DevOps
        • 쿠버네티스
        • 서버 만들기
      • 코딩테스트
        • 알고리즘
      • 교육
        • 스파르타코딩클럽 - 내일배움단
        • 혼자 공부하는 컴퓨터 구조 운영체제
      • 잡다한것
  • 블로그 메뉴

    • 홈
  • 링크

    • GITHUB
  • 공지사항

  • 인기 글

  • 태그

    백준
    리액트
    MSA
    Entity
    쿠버네티스
    클러스터
    chat GPT
    spring boot
    오블완
    인스타그램
    스프링부트
    클론코딩
    스프링 부트
    react
    Java
    mapstruct
    티스토리챌린지
    OpenAI API
    예외
    REST API
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.1
뚝딱뚝딱2
[Q. 11] 자신을 제외한 배열의 곱
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.