[무언가에 대한 리뷰][테크영상리뷰][쉬운코드] TwoSum 문제를 풀면서 배우는 내가 짠 코드의 성능을 개선하는 과정!! (feat. 코딩 테스트)

https://www.youtube.com/watch?v=cxhbgAbAiXI&list=PLcXyemr8ZeoTVBFTEB673TC8Ba4UBSTRz&index=6

 

 

리스트에 있는 서로 다른 두 정수의 합이 target number와 같다면 true를 반환하는 함수를 구현하시오.

 

리스트에 있는 서로 다른 두 정수의 합이 target number와 같다면 true를 반환하는 함수를 구현하시오.

 

입력값

num = {1, 2, 15, 6} target Number = 7 

num = {1, 2, 15, 6} target Number = 7 
 
public static boolean twoSum(){
 
	for(int i=0;i<nums.length;i++){
    	for(int j=0;j<nums.length;j++){
        	if( i == j ) continue;
            
            int sum = nums[i] + nums[j];
            if( sum == target )
            	return True;
        }
    }
    
    return false;
}

시간복잡도는 O(N^2) 이다.

 

 

위의 코드를 개선해보자.

num = {1, 2, 15, 6} target Number = 7 
 
public static boolean twoSum(){
 
	for(int i=0;i<nums.length;i++){
    	for(int j=i + 1;j<nums.length;j++){
            int sum = nums[i] + nums[j];
            if( sum == target )
            	return True;
        }
    }
    
    return false;
}

개선은 되었지만, 시간복잡도는 O(N^2) 이다.

성능자체는 개선되었다.

 

 

HashSet을 활용한다면 훨씬 빨라질것이다.

num = {1, 2, 15, 6} target Number = 7 
 
public static boolean twoSum(){
	
    for(int i=0;i<nums.length;i++){
    	hashset.add(nums[i]);
    }
    
	for(int i=0;i<nums.length;i++){
    	if( hashset.contains( targetNumber - nums[i] ) == true ){
        	return true;
        }
    }
    
    return false;
}

 

 

시간복잡도는 O(N) 이다.

HashSet 사용시 시간복잡도 조회는 O(1)이다.

 

 

문제가 있다. 코드에는 버그가 잇다.

만약 target Numbers = 4 이다.

1 2 15 6 .. 에서 만약 

만약 2 를 선택했을경우 똑같은 2 가 두번 계산되서 오류가 난다. 문제의 조건은 서로 다른 두 정수인것이다.

num = {1, 2, 15, 6} target Number = 4
 
public static boolean twoSum(){
	
    Hashset hashset = new HashSet<>();
    
	for(int i=0;i<nums.length;i++){
    	if( hashset.contains( targetNumber - nums[i] ) == true ){
        	return true;
        } else{
        	hashset.add(numbs[i]);
        }
    }
    
    return false;
}

 

이를 통해 중복된 값을 연산하지 않고, 이전까지의 숫자 값에서 targetNumber와 같은 값을 알아낼 수 있다.

 

시간복잡도는, Set만드는작업은 O(1), for문은 N번 반복되고 바디부분에서의 시간복잡도는 O(1)이다.

즉, O(1) + N * O(1)  이므로 O(N) 이다.