[PCCP] 시간복잡도 - 두 수의 합 | 자바 (java)

📜두 수의 합

PCCP(코딩전문역량인증)

 

비슷한 문제 - 리트코드 1번

https://leetcode.com/problems/two-sum/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

 

 

💡시간 복잡도와 공간 복잡도를 다르게 하여 문제 풀어보기

 

❗문제 설명

정수 수열 안에서 수열의 원소 두 개의 합이 target값이 되는 경우를 찾고 싶습니다.
매개변수 nums에 길이가 n인 수열이 주어지고, 매개변수 target에 자연수 값이 주어지면 이 수열안에서 두 개의 원소의 합이 정수 target값이 되는 두 원소를 구해 배열에 오름차순으로 담아 반환합니다.
두 개의 원소의 합이 target값이 되는 경우는 오직 한가지 뿐인 입력만 주어집니다. 한 원소를 두 번 더하는 것은 안됩니다. nums의 각 원소는 유일값입니다.
답이 없을 경우 [0, 0]을 반환합니다.

 

 

❗입출력 예

 

❗제한사항

• nums의 길이 3 <= n <= 100,000
• 배열 nums의 원소는 정수입니다. -10,000 <= nums[i] <= 10,000
•  -20,000 <= target <= 20,000

 

 

✍️ 베이스 코드

import java.util.*;
class Solution {
    public int[] solution(int[] nums, int target){
        int[] answer = new int[2];
        
        return answer;
    }
 
    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(Arrays.toString(T.solution(new int[]{3, 7, 2, 12, 9, 15, 8}, 12)));
        System.out.println(Arrays.toString(T.solution(new int[]{21, 12, 30, 15, 6, 2, 9, 19, 14}, 24)));
        System.out.println(Arrays.toString(T.solution(new int[]{12, 18, 5, 8, 21, 27, 22, 25, 16, 2}, 28)));
        System.out.println(Arrays.toString(T.solution(new int[]{11, 17, 6, 8, 21, 9, 19, 12, 25, 16, 2}, 26)));
        System.out.println(Arrays.toString(T.solution(new int[]{7, 5, 12, -9, -12, 22, -30, -35, -21}, -14)));
        System.out.println(Arrays.toString(T.solution(new int[]{7, 5, 12, 20}, 15)));
    }
}

 

 

---

🪄 풀이법 1 - 시간 복잡도 :  O(N^2)  공간 복잡도 : O(1)

 

이중 for문을 사용한 O(N^2) 풀이법

import java.util.*;
class Solution {
    public int[] solution(int[] nums, int target){
        int[] answer = new int[2];
        for (int i = 0; i < nums.length - 1; i++) {
            for (int y = i + 1; y < nums.length; y++) {
                if (nums[i] + nums[y] == target) {
                    if (nums[i] > nums[y]) {
                        answer[0] = nums[y];
                        answer[1] = nums[i];
                    } else {
                        answer[0] = nums[i];
                        answer[1] = nums[y];
                    }
                    break;
                }
            }
        }
        return answer;
    }
    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(Arrays.toString(T.solution(new int[]{3, 7, 2, 12, 9, 15, 8}, 12)));
        System.out.println(Arrays.toString(T.solution(new int[]{21, 12, 30, 15, 6, 2, 9, 19, 14}, 24)));
        System.out.println(Arrays.toString(T.solution(new int[]{12, 18, 5, 8, 21, 27, 22, 25, 16, 2}, 28)));
        System.out.println(Arrays.toString(T.solution(new int[]{11, 17, 6, 8, 21, 9, 19, 12, 25, 16, 2}, 26)));
        System.out.println(Arrays.toString(T.solution(new int[]{7, 5, 12, -9, -12, 22, -30, -35, -21}, -14)));
        System.out.println(Arrays.toString(T.solution(new int[]{7, 5, 12, 20}, 15)));
    }
}

 

 

 

🪄 풀이법 2 - 시간 복잡도 :  O(NlogN)  공간 복잡도 : O(1)

Arrays.sort()를 사용하여 (O(NlogN) ) 반복문을 한 번 사용하여 풀이

투포인터

import java.util.*;
class Solution {
    public int[] solution(int[] nums, int target){
        int[] answer = new int[2];
        Arrays.sort(nums);
        int smallIdx = 0;
        int bigIdx = nums.length - 1;
        while (smallIdx < bigIdx) {
            if (nums[smallIdx] + nums[bigIdx] == target) {
                answer[0] = nums[smallIdx];
                answer[1] = nums[bigIdx];
                break;
            } else if (nums[smallIdx] + nums[bigIdx] > target) {
                bigIdx--;
            } else {
                smallIdx++;
            }
        }
        return answer;    
    }
    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(Arrays.toString(T.solution(new int[]{3, 7, 2, 12, 9, 15, 8}, 12)));
        System.out.println(Arrays.toString(T.solution(new int[]{21, 12, 30, 15, 6, 2, 9, 19, 14}, 24)));
        System.out.println(Arrays.toString(T.solution(new int[]{12, 18, 5, 8, 21, 27, 22, 25, 16, 2}, 28)));
        System.out.println(Arrays.toString(T.solution(new int[]{11, 17, 6, 8, 21, 9, 19, 12, 25, 16, 2}, 26)));
        System.out.println(Arrays.toString(T.solution(new int[]{7, 5, 12, -9, -12, 22, -30, -35, -21}, -14)));
        System.out.println(Arrays.toString(T.solution(new int[]{7, 5, 12, 20}, 15)));
    }
}

 

 

🪄 풀이법 3 - 시간 복잡도 :  O(N)  공간 복잡도 : O(N)

공간 복잡도가 올라간 대신 반복문을 한번 사용하여 문제 풀기

HashMap 사용

import java.util.*;
class Solution {
    public int[] solution(int[] nums, int target){
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] answer = new int[2];
        for (int x : nums) {
            int y = target - x;
            if (map.containsKey(y)) {
                if (x > y) {
                    answer[0] = y;
                    answer[1] = x;
                } else {
                    answer[0] = x;
                    answer[1] = y;
                }
                break;
            } else {
                map.put(x, 1);
            }
        }
        return answer;
    }
    public static void main(String[] args){
        Solution T = new Solution();
        System.out.println(Arrays.toString(T.solution(new int[]{3, 7, 2, 12, 9, 15, 8}, 12)));
        System.out.println(Arrays.toString(T.solution(new int[]{21, 12, 30, 15, 6, 2, 9, 19, 14}, 24)));
        System.out.println(Arrays.toString(T.solution(new int[]{12, 18, 5, 8, 21, 27, 22, 25, 16, 2}, 28)));
        System.out.println(Arrays.toString(T.solution(new int[]{11, 17, 6, 8, 21, 9, 19, 12, 25, 16, 2}, 26)));
        System.out.println(Arrays.toString(T.solution(new int[]{7, 5, 12, -9, -12, 22, -30, -35, -21}, -14)));
        System.out.println(Arrays.toString(T.solution(new int[]{7, 5, 12, 20}, 15)));
    }
}