본문 바로가기
Web development/Algorithm

[LeetCode] Move Zeros, Two Sum

by 자몬다 2021. 1. 15.

Move Zeros

leetcode.com/explore/featured/card/top-interview-questions-easy/92/array/567/

배열에서 0을 모두 찾아 맨 뒤로 옮기면 된다.

// https://leetcode.com/explore/featured/card/top-interview-questions-easy/92/array/567/
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let count = 0;
  let len = nums.length;
  for (let i = 0; i < len; i++) {
    if (nums[i - count] === 0) {
      nums.splice(i - count, 1);
      count++;
      nums.push(0);
    }
  }
};

/**
 * 배열의 0을 모두 찾아 맨 뒤로 옮기는 문제다.
 *
 * 처음엔 sort해서 0부분만 잘라 뒤에 붙이려고 했는데,
 * 그러면 0이 아닌 숫자도 순서가 바뀌어서 안됨.
 *
 * 반복을 돌면서 0이면 잘라내 맨뒤에 붙이는 방법을 사용했으나,
 * arr = [0, 0, 1] 같은 경우
 * 0회차 반복 : arr[0]을 잘라 맨뒤에 붙임 => [0, 1, 0]
 * 1회차 반복 : arr[1]은 0이 아니므로 아무것도 하지 않음
 * 2회차 반복 : arr[2]를 잘라 맨뒤에 붙임 => [0, 1, 0]
 *
 * 이렇게 잘라내면서 순서가 바뀌어버려 지나간 요소에 대해 확인하지 못한다.
 * 그러므로 0을 잘라냈다면 다시 해당 순서부터 시작해야 한다.
 * 그래서 count라는 변수를 별도로 두고 0 갯수만큼 index를 빼주게 하였다.
 *
 * 다만 이렇게 하는 경우 0이 많을수록 필요 이상으로 반복을 돌게 되므로
 * 반복 횟수의 최적화가 필요할 것 같다.
 *
 */

 

 

Two Sum

배열에서 요소 2개의 합이 target과 같은 조합을 찾는 문제다.

leetcode.com/explore/featured/card/top-interview-questions-easy/92/array/546/

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

var twoSum = function (nums, target) {
  for (let i = 0; i < nums.length; i++) {
    const targetNum = target - nums[i];
    const index = nums.lastIndexOf(targetNum);
    if (i !== index && index !== -1) return [i, index];
  }
};

/**
 * 이중 for문을 피해보려다 결국 lastIndexOf를 써서 더 안좋은 풀이가 되었다.
 * 이렇게 풀면 이해하기도 어렵고, 놓친 부분도 찾기 어려울 것 같다.
 *
 * 추가로.. for..in으로 구현하려다 for(let index in arr)에서
 * index가 string으로 반환되는걸 처음 알았다.
 * 찾아보니 원래 객체의 반복을 위해 만들어진 메서드라, 배열 반복에서는 사용하지 말라고 한다.
 * 순차 반복도 보장되지 않는다고 하니 조심해서 사용해야겠다.
 *
 * 그래서 좀 더 정석적인 이중 for문으로 다시 풀었다.
 * 이해하기도 훨씬 쉽고, 조건문도 간단하다!
 *
 */

댓글