1. Two Sum 문제 해결 방법

1. Two Sum 문제 해결 방법

 

 

Two Sum 문제는 주어진 숫자 배열(nums)에서 두 개의 숫자를 선택하여 그 합이 특정 타겟(target)이 되도록 하는 문제입니다. 이 문제를 해결하는 것은 프로그래밍 능력을 평가하는 데 자주 사용되며, 특히 배열과 반복문을 다루는 기본적인 알고리즘 능력을 테스트하는데 적합합니다.

 

 

소제목5

 

 

문제 설명

 

1.Two Sum 문제 바로가기

 

주어진 배열 nums에서 두 숫자의 합이 target이 되는 두 숫자의 인덱스를 찾아야 합니다.

각 입력에는 정확히 하나의 해결책이 존재하며, 같은 요소를 두 번 사용할 수 없습니다.

답은 어떤 순서로 반환해도 됩니다.

 

 

해결 방법

이 문제를 해결하기 위한 접근 방법 중 하나는 이중 반복문을 사용하는 것입니다. 아래는 TypeScript로 구현한 코드입니다.

 

function twoSum(nums: number[], target: number): number[] {

    let result = [0,0];

    nums.forEach((x,i) =>{

        nums.forEach((y,j)=>{

            if(i>j && (x+y)===target) result=[j,i];

        });
        
    });

    return result;

    
};

 

 

코드 설명

• result 배열을 [0, 0]으로 초기화합니다. 이 배열은 조건에 맞는 두 숫자의 인덱스를 저장할 용도입니다.
• 바깥쪽 forEach 반복문에서는 nums 배열을 순회하며 현재 요소의 값(x)과 인덱스(i)를 얻습니다.
• 안쪽 forEach 반복문에서도 nums 배열을 순회하며 또 다른 요소의 값(y)과 인덱스(j)를 얻습니다.
• 이때, i > j 조건은 같은 요소를 두 번 사용하지 않도록 합니다. 두 숫자의 합이 target과 일치하는지 확인하고, 조건에 맞으면 result 배열을 현재 인덱스 쌍으로 업데이트합니다.

 

 

코드 리팩토링

 

Two Sum 문제의 코드 개선 방법

Two Sum 문제를 해결하기 위한 효율적인 방법 중 하나는 해시 테이블을 사용하는 것입니다. 해시 테이블을 사용하면 이미 확인한 숫자들을 저장하고, 각 숫자가 목표값(target)에 도달하기 위해 필요한 "상대값"을 빠르게 찾을 수 있습니다. 이 방법은 시간 복잡도를 O(n)으로 줄여, 배열의 크기가 커질 때 성능 저하를 크게 줄일 수 있습니다.

 

해시 테이블을 사용한 개선된 코드 

function twoSum(nums: number[], target: number): number[] {
    let numMap = new Map<number, number>(); // 숫자와 해당 숫자의 인덱스를 저장할 해시 테이블

    for(let i = 0; i < nums.length; i++) {
        let complement = target - nums[i]; // 상대값 계산
        if(numMap.has(complement)) {
            return [numMap.get(complement), i]; // 상대값이 이미 해시 테이블에 있다면, 해당 인덱스와 현재 인덱스 반환
        }
        numMap.set(nums[i], i); // 현재 숫자와 인덱스를 해시 테이블에 저장
    }

    return []; // 조건에 맞는 숫자 쌍이 없는 경우 빈 배열 반환
}

 

 

코드 설명

1. numMap이라는 이름의 Map 객체를 생성하여, 각 숫자와 해당 숫자의 인덱스를 저장합니다. Map 객체는 자바스크립트에서 해시 테이블을 구현하는 데 사용됩니다.
2. 입력 배열 nums를 순회하며 각 숫자에 대해 다음을 수행합니다.
3. complement라는 변수를 사용하여, 현재 숫자와 더했을 때 target이 되는 상대값을 계산합니다.
4. numMap에 complement가 이미 존재하는지 확인합니다. 존재한다면, target을 만드는 두 숫자를 찾은 것이므로, numMap에서 complement에 해당하는 인덱스와 현재 인덱스(i)를 배열로 반환합니다.
5. 현재 숫자를 numMap에 추가합니다. 이때, 숫자를 키로, 인덱스를 값으로 저장합니다.
6. 반복문이 끝난 후 조건에 맞는 숫자 쌍을 찾지 못했다면, 빈 배열을 반환합니다.

 

 

개선 사항의 장점

시간 효율성: 이전의 이중 반복문 방식은 O(n^2)의 시간 복잡도를 가졌지만, 해시 테이블을 사용하는 방식은 O(n)으로 크게 개선됩니다. 큰 데이터셋에서 성능 차이가 현저하게 나타납니다.

 

공간 효율성: 추가적인 공간을 사용하는 것은 사실이지만, 대규모 데이터셋에 대해 훨씬 빠른 실행 시간을 보장합니다.

 

---

 

이와 같은 방법은 Two Sum 문제 뿐만 아니라, 다른 많은 알고리즘 문제에서도 유용하게 활용될 수 있는 기법입니다. 데이터를 효율적으로 관리하고, 필요한 정보를 빠르게 접근할 수 있도록 하는 해시 테이블의 사용은 매우 중요한 개념 중 하나입니다.

 

▼ 다른 문제도 풀어보세요! ▼

 

1974. Minimum Time to Type Word Using Special Typewriter

 

2619. Array Prototype Last 문제 소개, 풀이 과정 및 코드 리팩토링