[Q. 07] 두 수의 합

2023. 3. 20. 15:33·코딩테스트/알고리즘
덧셈하여 타겟을 만들 수 있는 배열의 두 숫자 인덱스를 리턴하라.

 

처음 이 문제를 접하게 되면, 모든 경우의 수에 대한 조사를 할 것이다. 나 또한 그렇게 해결하였지만 이는 n의 제곱의 경우의 수로 매우 비효율 적이다. 그래서 파이썬으로 이러한 최적화 문제를 풀 때 가장 유용한 것은 딕셔너리를 이용하는 것이다.

 예를들어 [2,3,7] 에서 3이라는 값이나 인덱스를 찾으려면 in이나 index 함수를 사용하여야 하는데 이는 O(n)이다. 하지만 이를 딕셔너리로 변환하여 'Dict[값] = 인덱스' 형태로 저장하면 해당 값의 인덱스를 찾거나, 해당 값이 있는지 확인하는데 걸리는 시간은 O(1)이 된다.

 이를 활용하여 이 문제를 해결해보자.

 

먼저, 딕셔너리 형태로 배열을 정리한다.

num_dict = {}

for i, n in enumerate(nums):
    num_dict[n] = i

 

보는 것과 같이 'Dict[값] = 인덱스' 형태로 딕셔너리를 생성하였다. 

그 다음, 'target - 값' 이 딕셔너리에 존재하는 지를 확인하면 덧셈하여 만들 수 있는 배열의 두 숫자가 될 것이다.

for i, n in enumerate(nums):
    if num_dict.get(target - n) != None and i != num_dict[target - n]:
        return i, num_dict[target-n]

 

여기서 i != num_dict[target-n]을 확인하는 이유는, 같은 인덱스에 있는 값을 2번 사용 할 수도 있기 때문에 그것에 대한 예외를 설정해 주는 것이다.

 

전체 코드는 다음과 같다.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        
        num_dict = {}

        for i, n in enumerate(nums):
            num_dict[n] = i

        for i, n in enumerate(nums):
            if num_dict.get(target - n) != None and i != num_dict[target - n]:
                return i, num_dict[target-n]
저작자표시 비영리 변경금지 (새창열림)

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

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

    • 홈
  • 링크

    • GITHUB
  • 공지사항

  • 인기 글

  • 태그

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

  • 최근 글

  • hELLO· Designed By정상우.v4.10.1
뚝딱뚝딱2
[Q. 07] 두 수의 합
상단으로

티스토리툴바