최고의 개발자 (목표)

문제

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

https://leetcode.com/problems/merge-two-sorted-lists/

예시

코드

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    if(list1 === null){
        return list2;
    }
    
    if(list2 === null){
        return list1;
    }
    
    const newNode = new ListNode();
    let dummy = newNode;
    
    while(list1 && list2){
        if(list1.val < list2.val){
            dummy.next = list1;
            list1 = list1.next;
        }else{
            dummy.next = list2;
            list2 = list2.next;
        }
        dummy = dummy.next;
    }
    
    if(list1) {
        dummy.next = list1;
    }
    else if(list2){
        dummy.next = list2;
    }
    
    return newNode.next;
    
};

먼저 결과를 저장할 노드를 생성하고,  한 칸씩 이동하면서 노드에 값을 넣어주어야 하기 때문에 그런 역할을 할 dummy 노드를 만든다. list1과 list2의 value 값을 비교해 더 작은 값을 가진 노드를 dummy 노드의 next에 넣어준다. 그 후 작은 값을 가진 노드의 리스트를 다음 노드로 바꾸어준다. 그 후, dummy 노드도 next로 바꾸어준다. list1이나 list2 둘 중 하나라도 null이면 while문에서 빠져나오므로, 빠져나왔을 때 list1이나 list2에 남은 노드가 있을 수 있다. 따라서 list1과 list2를 확인해 확인하지 않은 노드가 있으면 dummy 노드의 next로 넣어준다. 

초기에 만든 노드는 인자로 아무 것도 넣어주지 않았기 때문에 value가 0인 노드가 들어가 있다. 따라서, newNode의 next를 리턴해준다.

문제

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type.

https://leetcode.com/problems/valid-parentheses/

예시

코드

function isValid(s: string): boolean {
    const stack:Array<string> = [];
    
    const matchBrackets:{[key:string]:string} = {
        ')' : '(',
        ']' : '[',
        '}' : '{'   
    };
    
    
    for(const bracket of s){
        if(bracket in matchBrackets){ // 닫힌 괄호
            if(stack.length === 0) return false;
            if(stack.pop() !== matchBrackets[bracket]) return false;
        }
        else{ // 열린 괄호
            stack.push(bracket);
        }
    }
    
    // 열린 괄호만 남아있을 수도 있음
    return stack.length === 0;
    
    
};

괄호가 올바르게 짝이 맞는지 확인하는 문제이다. 열린 괄호일 때는 스택에 추가하고, 닫힌 괄호일 때는 스택에 가장 상단에 있는 괄호를 뽑아서 닫힌 괄호와 짝이 맞는 열린 괄호인지 확인한다. 만약 짝이 맞지 않는다면 올바른 괄호가 아니기 때문에 `false`를 리턴해준다. 물론, 그 전에 스택이 비어 있다면 앞에 있던 열린 괄호가 다 뽑혔다는 의미이므로, 스택이 비어있을 때 바로 `false`를 리턴한다. 또한, 열린 괄호가 닫힌 괄호보다 많이 존재했다면 올바른 괄호가 될 수 없기 때문에 마짐가에 스택이 비어있지 않으면 `false`를 리턴하도록 한다.

문제

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, 2 is written as II in Roman numeral, just two ones added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given a roman numeral, convert it to an integer.

https://leetcode.com/problems/roman-to-integer/

예시

코드

function romanToInt(s: string): number {
    const ROMAN = {
        I: 1,
        V: 5,
        X: 10,
        L: 50,
        C: 100,
        D: 500,
        M: 1000
    };
    
    const result = s.split('').reduce((acc, cur, idx)=>{
        if(ROMAN[cur] < ROMAN[s[idx+1]]){
            acc -= ROMAN[cur]; 
        }else{
            acc += ROMAN[cur];
        }
        return acc
    }, 0);
  
    return result;
};

입력으로 로마자가 들어오면, 그걸 십진수로 변환해 출력하면 된다. 각 로마자에 맞는 수를 객체에 저장해주었고,  로마자에 매칭되는 수를 계속 더해주면 된다. 이때, `작은 숫자 + 큰 숫자`의 조합이 있다면 작은 숫자에 해당하는 값은 더하는 것이 아니라 빼주어야 한다. 즉, 현재 값의 바로 오른쪽에 나보다 큰 수가 온다면 현재 값은 더해주는 것이 아니라 빼주어야 한다.

문제

Given an integer x, return true if x is a palindrome, and false otherwise.

https://leetcode.com/problems/palindrome-number/

예시

코드

function isPalindrome(x: number): boolean {
   return x.toString().split('').reverse().join('') === x.toString() ? true : false;
};

 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열을 팰린드롬이라고 한다. 이 문제는 숫자가 주어지고, 해당 숫자가 팰린드롬 수인지 판단하면 된다.

따라서, x를 뒤집은 것과 x가 같은지 판단하였다. x를 먼저 문자열로 바꾼 뒤, `split()`과 `reverse()`를 이용해 거꾸로 뒤집힌 배열로 만들어주고, `join()`으로 다시 문자열로 합쳐서 기존 x와 같은지 비교하였다.

문제

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.

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

예시

코드

// O(n²)
function twoSum(nums: number[], target: number): number[] {
    
    for(let i = 0; i < nums.length; i++){
        const num = target - nums[i];
        const index = nums.indexOf(num);
        
        if(index !== -1 && index !== i){
            // 배열에 있으면서 자기 자신이 아닐 때
            return [i, index];
        }
    }
};

// O(n)
function twoSum(nums: number[], target: number): number[] {
    // key : num, value : index
    const map = new Map();
    
    for(let i = 0; i < nums.length; i++){
        const num = target - nums[i];
        
        if(map.get(num)!==undefined){
            return [i, map.get(num)]
        }
        
        map.set(nums[i], i);
    }
};

처음에는 `indexOf`를 활용해 풀었는데, 시간 복잡도를 줄이기 위해 `Map`을 활용하여 다시 풀었다.

map의 key는 nums의 요소들이고, value는 각 요소의 인덱스를 저장하였다. `nums 요소 + 다른 nums 요소 = target`을 다른 말로 쓰면, `nums 요소 = target - 다른 nums 요소` 가 된다. 따라서 map에 target에서 현재 nums 요소를 뺀 값이 있다면 더해서 target을 만들 수 있는 값이 있다는 의미이므로 각 인덱스를 리턴하였고, 없다면 map에 해당 nums 요소의 값과 인덱스를 추가해주었다.

`indexOf`의 경우, 인자로 위치를 찾고 싶은 요소를 넣어주는데 이때 앞에서부터 순차적으로 확인하기 때문에 `O(n)`의 시간복잡도를 가진다. 따라서 for문과 함께 써주게 되면 시간 복잡도가 `O(n²)`이 된다.

`Map`의 경우 (V8 엔진 기준) 해시 테이블로 구현되어 있다. 따라서 대부분 `Map`에서의 조회는 `O(1)`의 시간 복잡도를 가진다. 대부분이라고 한 이유는, 해시 테이블이 특정 기준에 따라 꽉 차있으면 재해싱 되는데, `set()` 이나 `delete()` 작업 중 재해싱이 일어난다. 재해싱은 해시 테이블의 크기를 늘리고, 기존 키의 해시 값을 재계산해서 새 테이블에 다시 삽입하는 과정을 거친다. 이때, 데이터를 재배치하는 과정에서 기존 테이블의 모든 요소에 대해서 처리하기 때문에 `O(n)`의 시간 복잡도를 가지게 된다. 그러나, 재해싱 되는 경우는 드물기 때문에 `O(1)`의 시간 복잡도를 보통 가진다고 설명한다.

문제

Given two arrays arr1 and arr2, return a new array joinedArray. All the objects in each of the two inputs arrays will contain an id field that has an integer value. 

joinedArray is an array formed by merging arr1 and arr2 based on their id key. The length of joinedArray should be the length of unique values of id. The returned array should be sorted in ascending order based on the id key.

If a given id exists in one array but not the other, the single object with that id should be included in the result array without modification.

If two objects share an id, their properties should be merged into a single object:

• If a key only exists in one object, that single key-value pair should be included in the object.
• If a key is included in both objects, the value in the object from arr2 should override the value from arr1.

https://leetcode.com/problems/join-two-arrays-by-id/

예시

코드

/**
 * @param {Array} arr1
 * @param {Array} arr2
 * @return {Array}
 */
var join = function(arr1, arr2) {
    const hashMap = {};
    
    for(obj of arr1.concat(arr2)){
        const id = obj["id"];
        
        if(hashMap[id]){
            // id exist
            hashMap[id] = {...hashMap[id], ...obj};
            
        }else{
            hashMap[id] = obj;
        }
        
    }
    
    
    return Object.values(hashMap);
};

hashMap이라는 새로운 객체를 만들고, id를 key로 갖고 객체를 value로 갖도록 hashMap 형태로 만들었다. hashMap에 해당 id가 없는 경우에는 hashMap에 새로 추가했다. 이미 key가 id인 객체가 있는 경우에는 스프레드 연산자를 활용해서 기존에 있던 객체와 새로운 객체를 합쳐서 같은 key인 경우에는 뒤에 있는 객체의 value로 덮어씌울 수 있도록 했다.

문제에서 정렬을 하라고 했는데, JS는 object를 key 값 기준으로 정렬해주기 때문에 따로 정렬해주지 않았다.

그 후 `Object.values()` 를 활용해 values로 이루어진 배열 형태를 반환한다.

문제

Given an object or an array, return if it is empty.

• An empty object contains no key-value pairs.
• An empty array contains no elements.

You may assume the object or array is the output of JSON.parse.

https://leetcode.com/problems/is-object-empty/

예시

코드

/**
 * @param {Object|Array} obj
 * @return {boolean}
 */
var isEmpty = function(obj) {
    return JSON.stringify(obj).length == 2;
};

인자로 들어오는 obj의 형식이 Object이거나 Array이기 때문에 이를 JSON.stringify를 이용해 JSON 문자열로 변환하였다. 그렇다면 비어있는 array의 경우 `'[]'` 로 변환이 되고, 비어있는 Object의 경우 `'{}'`로 변환이 되기 때문에 비어있을 경우 length가 2가 된다. 따라서 길이가 2인지 여부를 판단하여 리턴해주었다.

문제

Given a function fn, an array of arguments args, and an interval time t, return a cancel function cancelFn.

After a delay of cancelTimeMs, the returned cancel function cancelFn will be invoked.

setTimeout(cancelFn, cancelTimeMs)

The function fn should be called with args immediately and then called again every t milliseconds until cancelFn is called at cancelTimeMs ms.

https://leetcode.com/problems/interval-cancellation/

예시

코드

/**
 * @param {Function} fn
 * @param {Array} args
 * @param {number} t
 * @return {Function}
 */
var cancellable = function(fn, args, t) {
    fn(...args);
    const timerId = setInterval(() => {fn(...args)}, t);
    
    return function(){
       clearInterval(timerId);
    }
};

/**
 *  const result = [];
 *
 *  const fn = (x) => x * 2;
 *  const args = [4], t = 35, cancelTimeMs = 190;
 *
 *  const start = performance.now();
 *
 *  const log = (...argsArr) => {
 *      const diff = Math.floor(performance.now() - start);
 *      result.push({"time": diff, "returned": fn(...argsArr)});
 *  }
 *       
 *  const cancel = cancellable(log, args, t);
 *
 *  setTimeout(cancel, cancelTimeMs);
 *   
 *  setTimeout(() => {
 *      console.log(result); // [
 *                           //     {"time":0,"returned":8},
 *                           //     {"time":35,"returned":8},
 *                           //     {"time":70,"returned":8},
 *                           //     {"time":105,"returned":8},
 *                           //     {"time":140,"returned":8},
 *                           //     {"time":175,"returned":8}
 *                           // ]
 *  }, cancelTimeMs + t + 15)    
 */

cancellable 함수는 function을 리턴해야 하며, 호출하였을 때 특정 함수의 호출을 cancel 하는 역할을 한다. log 함수는 계속 t(ms) 마다 실행이 되어야 하고, cancelTimeMs(ms) 후에 cancel 이 호출되고, 그때 log 함수가 멈춰야 한다. 따라서 cancellable 함수 내부에서 setInterval 을 이용해서 t(ms) 마다 fn을 호출하였고, 원하는 output에서 0초부터 로그가 찍히는 것을 원했기 때문에 setInterval 호출 전 따로 fn을 호출해주었다. 그리고 setInterval에서 반환된 timerId를 이용해서 interval을 취소시키는 행동을 하는 함수를 리턴한다.

문제

Given an array arr and a function fn, return a sorted array sortedArr. You can assume fn only returns numbers and those numbers determine the sort order of sortedArr. sortedArray must be sorted in ascending order by fn output.

You may assume that fn will never duplicate numbers for a given array.

https://leetcode.com/problems/sort-by/

예시

arr을 fn의 기준에 따라 정렬시킨다.

코드

/**
 * @param {Array} arr
 * @param {Function} fn
 * @return {Array}
 */
var sortBy = function(arr, fn) {
    return arr.sort((a, b)=>fn(a)-fn(b));
};

각각 a와 b를 fn 함수를 통과시킨 뒤, 오름차순으로 정렬하였다.

문제

Given two promises promise1 and promise2, return a new promise. promise1 and promise2 will both resolve with a number. The returned promise should resolve with the sum of the two numbers.

https://leetcode.com/problems/add-two-promises/

예시

코드

/**
 * @param {Promise} promise1
 * @param {Promise} promise2
 * @return {Promise}
 */
var addTwoPromises = async function(promise1, promise2) {
    return new Promise((resolve, reject)=>{
        Promise.all([promise1, promise2]).then((values)=>{
            resolve(values[0]+values[1]);
        });
    });
};

/**
 * addTwoPromises(Promise.resolve(2), Promise.resolve(2))
 *   .then(console.log); // 4
 */

addTwoPromises는 Promise 객체를 반환해야 하며, 인자로 2개의 Promise를 받고, 두 개의 Promise의 resolve value를 합해주어야 한다. 두 Promise가 모두 이행되었을 때 더해주기 위해서 `Promise.all()`을 이용하였고, 두 promise에서 넘어온 value는 values에 배열 형식으로 저장되어있다. 따라서 values[0]과 values[1]을 더해서 resolve의 인자로 넣어주었다.

💡Promise

상태

• 대기 pending : 초기 상태.
• 이행 fulfilled : 연산이 성공적으로 완료됨
• 거부 rejected : 연산이 실패함

생성자

• Promise()
  • 새로운 Promise 객체 생성.

정적 메서드

• Promise.all(iterable)
  • 주어진 모든 프로미스가 이행 OR 한 프로미스가 거부될 때까지 대기하는 프로미스 객체
• Promise.allSettled(iterable
  • 주어진 모든 프로미스가 처리(이행 OR 거부) 될 때까지 대기하는 프로미스 객체
• Promise.any(iterable)
  • 주어진 모든 프로미스 중 하나라도 이행하면 그 값으로 이행하는 프로미스 객체
• Promise.race(iterable)
  • 주어진 모든 프로미스 중 하나라도 처리될 때까지 대기하는 프로미스 객체
• Promise.reject(reason)
  • 주어진 사유로 거부하는 프로미스 객체
• Promise.resolve()
  • 주어진 값으로 이행하는 프로미스 객체

사용 예시

// 새로운 Promise 객체 생성
let myFirstPromise = new Promise((resolve, reject) => {
  // exeucutor
	// executor는 Promise 생성 시 자동 실행됨.
  // 이 안에서 resolve나 reject 둘 중 하나는 호출해야함.
	// resolve(value) - 일이 성공적으로 완료되었을 때 결과 value와 함께 호출해야함.
	// reject(error) - 에러 발생 시 에러 객체를 나타내는 error와 함께 호출해야함.

	// EX)
	// 1초 뒤에 일이 성공적으로 끝났다는 신호가 전달되면서 result는 '완료'가 됨.
  setTimeout(() => resolve("완료"), 1000);
});

// 만든 Promise 객체 사용
myFirstPromise.then((result, error)=>{
		console.log(result); // 1초 후 완료가 출력됨.
});