파이썬 코딩테스트 스터디 5주차 #1 추가 - 두 개의 수로 특정갑 만들기(몸풀기 문제)

 

 

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

이 중에서 합이 target인 두 수가 arr에 있는지 찾고, 있으면 True, 없으면 False 를 반환하는 solution() 함수를 작성하세요

 

제약 조건

n은 2 이상 10,000 이하의 자연수입니다.

arr의 각 원소는 1 이상 10,000이하의 자연수입니다.

arr의 원소 중 중복되는 원소는 없다.

target은 1 이상, 20,000 이하의 자연수

 

 

방법1. 무작정 더하며 찾기 : 시간복잡도 : O(N^2)

2중 for문으로 돌면서 찾는다

 

방법2. 해시 활용해서 찾기

 

개념은 이렇다

위 예시 arr=[1,2,3,4,8], target=6인경우를 보자

hashtable=[0] * (target+1)

이렇게 되면 아래와 같은 배열이 생성  

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

 

3) 이때 arr각 값에 해당하는 hastable의 Index 의 value는 1로 바꾼다.

     arr=[1,2,3,5,8] 단,  arr에서 2개를 더해 targe이 나오는지가 문제이므로

     여기서 8은 절대 해당이 안됨 즉, value <= target이어야한다. ( INDEX 7, 8은 의미없음)

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

 

 

여기까지를 코드로 구현해보면

def count_sort(arr,k):
	#해시테이블 생성 및 초기화
    hashtable = [0] * (k+1)
    
    
    for num in arr:
    	if num<=target:
        	hastable[num]=1
    return hashtable

 

4)  이때 다시 arr을 돌면서 두수를 합쳐서 target이 될수 있는 값 찾기

     complement = target - arr[i] 을 찾는다. 

                          1) 6 - 1   =  5  즉, 5가 hash에 있으면 hashtable[5]==1이면, 1은 해당됨

                          2) 6 - 2   =  4  즉, 4가 hash에 있으면 hashtable[4]==1이면, 2는 해당됨

                          3) 6 - 3   =  3  즉, 3이 hash에 있으면 hashtable[3]==1이면, 3은 해당됨  

                          4) 6 - 5   =  1  즉, 1이 hash에 있으면 hashtable[1]==1이면, 5는 해당됨  

 

   그래서 이걸 코드로 짜보면

 

def solution(arr,target):
	hashtable = count_sort(arr,target)
    
    for num in arr:
    	complement = target - num
        
        if(
        complement!= num	#똑같은 숫자 제외
        and complement >=0	#0보다 크거나 같아야함
        and complement <target #target보다 작거나 같아야함
        and hashtable[complement] == 1 #제일 중요 조건
        ):
        	return True
    return False