[리트코드LeetCode][Easy][JAVA][JavaScript]1. Two Sum

코딩테스트/리트코드LeetCode

[리트코드LeetCode][Easy][JAVA][JavaScript]1. Two Sum

빔o0O 2024. 9. 7. 15:03

문제에 앞서 사설.

Easy부터 풀어야하나 그래도 내가 프로그래머스 1레벨은 마스터를 한 사람인데, 라고 잠시 고민했지만 건방떨지 말고 차근차근 풀어가기로 함. 쉬우면 문제를 여러 개 풀면 되는데, 그렇게 건실하게 할 수 있는지는 잘 모르겠다. 파이팅.

(아니 이번에 자바스크립트를 같이 풀면서 알았는데 한 글에서 코드블럭의 언어설정이 하나로만 지정되는구나 정말 신경쓰이는군)

문제

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Only one valid answer exists.

분석

주어진 integer 배열의 변수에서, 하나의 요소는 한 번 씩만 사용하여 2개의 요소를 더했을 때 target 으로 주어진 수를 만드는 경우의 인덱스를 반환한다.
오직 하나의 해만 존재한다고 제한하였으므로 답이 나오면 바로 리턴시키면 됨.

피드백

시간효율을... 더 생각해보자. 비교적 덜 복잡한 문제를 푸는 거니까 푸는 것에만 의의를 두지 말고 이젠 효율성까지 고려해볼 때인 듯.

답안

JAVA

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        int len = nums.length;
        outerLoop:
        for(int i = 0; i < len; i++) {
        	for(int j = i+1; j < len; j++) {
        		if(nums[i] + nums[j] == target) {
        			answer[0] = i;
        			answer[1] = j;
        		    break outerLoop;		// 바깥의 루프까지 종료시킨다.
        		}
        	}
        }
        return answer;
    }
}

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var len = nums.length;
    for(var i = 0; i < len; i++){
        for(var j = i+1; j < len; j++){
            if(nums[i] + nums[j] == target){
                return [i, j];
            }
        }
    }
};

다른 사람의 답안

JAVA

/*
	return할 변수 생성 없이 바로 return 에서 객체를 정의하여 보낸다. 
    내 코드는 이중 for문으로 모든 값의 합을 검증하고 값이 나오는 순간 return 하는데,
    이 코드는 하나의 for문을 이용하되 Map을 이용해 대상 요소가 target이 되기 위해
    더해야 하는 값을 구해놓고 검증하여 바로 확인한다. 
    => 굉장히 시간 효율성이 좋음!!!
*/

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;	// 루프조건용 변수
        HashMap<Integer, Integer> hmap = new HashMap<>();

        for(int i=0; i<n; i++) {
            int diff = target - nums[i];	// i번째 요소를 target으로 만들어주는 수를 구함
            if(hmap.containsKey(diff)) {	// 그 수가 이전에 있었다면 그 값으로 return
                return new int[] {i, hmap.get(diff)};
            } else {
                hmap.put(nums[i],i);	// 없으면 map에 값을 넣어주고 지나감.
            }
        }
        return new int[] {};
    }
}

/*
	이 코드의 시간효율이 엄청나게 좋게 나왔는데, 내 코드와 비교한 건 하기 참조
*/

class Solution {
    public int[] twoSum(int[] nums, int target) {
        
      int n = nums.length;
        for(int i = 1; i < n; i++){
            for(int j = i; j < n; j++){
                if(nums[j] + nums[j-i] == target){
                    return new int[] {j-i,j};
                }
            }
        }
        return new int[2];
    }
}

🤖 챗지가 분석해준 코드 비교

(*코드 A는 나의 코드, 코드 B는 위의 코드)

시간 복잡도: 여전히 O(n^2)입니다. 하지만 이 코드는 실제로는 코드 A보다 더 빠를 수 있습니다. 이유는 다음과 같습니다:
- 조건 검사: 코드 B는 nums[j-i]를 사용하여 두 수의 합이 target인지 비교합니다. 이 방식은 매번 인덱스를 계산해야 하므로, 추가적인 계산이 필요합니다. 그러나 j-i는 i와 j 사이의 간격을 미리 정해 놓기 때문에 조건을 확인하는 속도가 빠를 수 있습니다.
- 루프의 시작 위치: 코드 B는 i를 1부터 시작하고 j를 i부터 시작합니다. 이로 인해 j가 i보다 항상 크기 때문에, nums[j] + nums[j-i]는 항상 서로 다른 두 인덱스의 합을 검사합니다. 코드 A는 j를 i+1부터 시작하므로 각 인덱스 쌍을 검사할 때 보다 복잡한 조건문을 갖습니다.

요약

시간 복잡도: 두 코드 모두 O(n^2)입니다.
효율성 차이: 코드 B가 코드 A보다 빠를 수 있는 이유는 코드 B가 인덱스를 직접 계산하는 방식으로 조건을 비교하기 때문에 메모리 접근과 계산이 약간 더 최적화될 수 있습니다. 또한, 코드 B는 인덱스를 좀 더 간단하게 관리하므로, 루프 내에서 조건 검사가 약간 더 빠를 수 있습니다.

결과적으로, 코드 B가 더 효율적이라고 판단되는 이유는 내부 계산과 조건 비교가 코드 A보다 더 간단하고, 따라서 실제 실행 시 약간의 성능 개선이 있을 수 있기 때문입니다.

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */

var twoSum = function(nums, target) {
    const elementSum = {};

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (complement in elementSum) {
            return [elementSum[complement], i];
        }

        elementSum[nums[i]] = i;
    }

    return null;
};

티스토리