정수 숫자와 정수 대상의 배열이 주어지면 두 숫자의 인덱스를 반환하여 대상에 합산합니다.
각 입력에는 솔루션이 하나만 있고 동일한 요소를 두 번 사용할 수 없다고 가정할 수 있습니다.
답변은 어떤 순서로든 반환할 수 있습니다.
https://leetcode.com/problems/two-sum/
실제 코딩테스트 시험을 보는거라면 안되겠지만 공부하는 중이라
처음에는 우선 문제해결에 집중하여 시간복잡도는 뒤로 두고 쉽게 풀어봤다.
우선 테스트 코드를 작성해주자.
요즘엔 테스트코드의 필요성과 공부 및 실제 개발환경에서 사용하고싶어 여러가지 이유로 테스트케이스도 작성했다.
const { twoSum } = require("./twoSum");
describe("twoSum", () => {
it("입력에 대한 인덱스를 반환합니다", () => {
const nums = [
2, 7, 11, 15, 20, 25, 3, 4, 5, 6, 8, 9, 10, 12, 13, 14, 30, 31, 32, 33,
34, 35, 36, 37, 38, 39, 40,
];
const target = 9;
const expected = [0, 1];
const result = twoSum(nums, target);
expect(result).toEqual(expected);
});
it("일치하는 인덱스가 없는 경우 빈 배열을 반환합니다", () => {
const nums = [2, 7, 11, 15];
const target = 5;
const expected = [];
const result = twoSum(nums, target);
expect(result).toEqual(expected);
});
it("입력 배열이 중복된 숫자인 경우에도 유효한지 확인합니다.", () => {
const nums = [3, 3];
const target = 6;
const expected = [0, 1];
const result = twoSum(nums, target);
expect(result).toEqual(expected);
});
});
const twoSum = function (nums, target) {
const result = [];
nums.forEach((num1, index1) => {
nums.forEach((num2, index2) => {
if (index1 !== index2 && num1 + num2 === target && result.length < 2) {
result.push(index1, index2);
}
});
});
return result;
};
우선 테스트코드도 잘 통과했고 문제해결 자체로는 상관없었으나 위 코드는 문제가 있다.
nums 의 길이가 최대 10^4 인게 문제다.
시간 복잡도가 O(n^2)이므로 nums 배열이 커지면 성능이 크게 저하가 될거고 당연히 테스트도 실패할거다.
그렇다면 중첩반복문이 절대 들어가서는 안된다.
그럼 해쉬테이블을 이용하여 접근해보자.
const twoSum = function (nums, target) {
let result = [];
const keyValue = {};
nums.forEach((num, index) => {
const findNum = target - num;
if (keyValue[findNum] !== undefined && result.length < 2) {
result = [keyValue[findNum], index];
} else {
keyValue[num] = index;
}
});
return result;
};
위 코드는 객체의 키값에 바로 접근하는 해쉬테이블을 이용했다.
반복문은 하나로 줄었으며 원하는 값도 한번에 찾을 수 있으므로 시간복잡도는 O(n) 이다.
'알고리즘 > 문제풀이' 카테고리의 다른 글
다음에 올 숫자 - 프로그래머스 feat: javascript (0) | 2023.04.19 |
---|