파이썬 코딩테스트 스터디 5주차 #2 - 몸풀기 문제, 두 개의 수로 특정값 만들기

 

 

 

n개의 양의 정수로 이루어진 리스트 arr와 정수 target이 주어졌을 때

이 중에서 합이 target인 두 수가 arr에 있는지 찾고, 있으면 True

없으면 False 반환하는 solution()함수 작성

 

제약조건

• n은 2 이상 10,000 이하의 자연수
• arr의 각 원소는 1 이상 10,000 이하의 자연수
• arr의 원소 중 중복되는 원소는 없습니다.
• target은 1 이상, 20,000 이하의 자연수

입출력의 예

 

arr	target	return
[1,2,3,4,8]	6	True
[2,4,3,5,9]	10	False

 

 

문제 분석하기

 

1. target+1까지를 index로 하는 value:1,0으로 이루어진 배열 만들기

    (왜 target+1이냐면 0+target도 가능하니까)

    이때 해당 배열을 돌면서 arr의 값을 인덱스로하는 value=1, 나머지는 다 0

2. arr의 원소를 돌면서 target -  원소가 위에 배열의 인덱스로 

    value를 1로 가지고 있으면 해당 문제의 조건을 만족함

3. arr의 원소에서 target보다 큰 값은 무시.

 

 

 

아래 문제

소스코드 분석

 

arr = [1,2,3,4,8]

target = 6

 

hashtable=[0] *(6+1)     

(이렇게 하는 이유는 0+6이 있을수 있으니까)

 

hashtable = [0,0,0,0,0,0,0] 

0이 7개 

 

 

hashtable

Key	0	1	2	3	4	5	6
Value	0	0	0	0	0	0	0

 

hashtable[1] = 1

hashtable[2] = 1

hashtable[3] = 1

hashtable[4] = 1

 

count_sort 함수 실행 후

hashtable

Key	0	1	2	3	4	5	6
Value	0	1	1	1	1	0	0

 

def count_sort(arr,k):
     hashtable = [0] *(k+1)
     for num in arr:
             if num <= k :
                     hashtable[num] = 1
     return hashtable
     
def solution(arr,target):
	hashtable = count_sort(arr,target)
    
    for num in arr:
    	# arr =[1,2,3,4,8]
    	complement = target - num
        # num = 1, complement = 6 - 1 = 5
        # num = 2, complement = 6 - 2 = 4
        # num = 3, complement = 6 - 3 = 3
        # num = 4, complement = 6 - 4 = 2
        # num = 8, complement = 6 - 8 = -2
        if (
        complement != num
        and complement >=0
        and complement <=target
        and hashtable[complement] = 1
        ):
        
        return True
    return false

 

 

좀 헷갈리지만, 

얼추 이해는 감. 

 

근데 처음부터 작성하기가 좀 어려울듯..

 

♬ 자료 출처 - 책

코딩 테스트 합격자 되기 - 파이썬 편

 

 

 

이 포스팅의 모든 내용은 해당 책의 내용을 바탕으로 하고 있습니다. 

감사합니다.