최고의 개발자 (목표)

문제

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 an array of asynchronous functions functions, return a new promise promise. Each function in the array accepts no arguments and returns a promise. All the promises should be executed in parallel.

promise resolves:

• When all the promises returned from functions were resolved successfully in parallel. The resolved value of promise should be an array of all the resolved values of promises in the same order as they were in the functions. The promise should resolve when all the asynchronous functions in the array have completed execution in parallel.

promise rejects:

• When any of the promises returned from functions were rejected. promise should also reject with the reason of the first rejection.

Please solve it without using the built-in Promise.all function.

https://leetcode.com/problems/execute-asynchronous-functions-in-parallel/

예시

틀린 코드

/**
	틀린 코드
**/
var promiseAll = function(functions) {
    return new Promise((resolve, reject) => {
        const arr = [];
        
        
        functions.forEach((promise)=>{
            promise()
            .then((value) => {
                arr.push(value);

                if(arr.length === functions.length){
                    resolve(arr);
                }
            })
            .catch((err) => {
                reject(err);
            });
        });
        
        
    });
};

처음에 시도했던 코드인데, 틀렸다. 해당 예시를 실행해보니, arr 배열에 들어가는 resolve된 값의 순서가 promise의 순서와 달랐다. 현재 코드대로라면, functions 배열에 있는 프로미스의 실행이 완료되면 arr에 값이 push 되는데, 어떤 프로미스가 먼저 실행이 완료되는지 알지 못하기 때문에 순서가 바뀔 수 있던 것이다. 따라서, arr에 push 하는 방법 대신, index를 직접 지정해서 순서가 바뀌지 않도록 해주었다. (아래 코드 참조)

정답 코드

/**
 * @param {Array<Function>} functions
 * @return {Promise<any>}
 */
var promiseAll = function(functions) {
    return new Promise((resolve, reject) => {
        const arr = Array(functions.length);
        
        let solveCnt = 0;
        
        functions.forEach((promise, idx)=>{
            promise()
            .then((value) => {
                arr[idx] = value;
                solveCnt++;

                if(solveCnt === functions.length){
                    resolve(arr);
                }
            })
            .catch((err) => {
                reject(err);
            });
        });
        
        
    });
};

/**
 * const promise = promiseAll([() => new Promise(res => res(42))])
 * promise.then(console.log); // [42]
 */

index를 이용해 arr에 값을 넣어주었고, 모든 promise가 다 실행 완료가 됐을 때 resolve 해야 하므로 solveCnt라는 변수로 실행 완료된 promise의 개수를 세었다.

문제

Write code that enhances all arrays such that you can call the snail(rowsCount, colsCount) method that transforms the 1D array into a 2D array organised in the pattern known as snail traversal order. Invalid input values should output an empty array. If rowsCount * colsCount !== nums.length, the input is considered invalid.

Snail traversal order starts at the top left cell with the first value of the current array. It then moves through the entire first column from top to bottom, followed by moving to the next column on the right and traversing it from bottom to top. This pattern continues, alternating the direction of traversal with each column, until the entire current array is covered. For example, when given the input array [19, 10, 3, 7, 9, 8, 5, 2, 1, 17, 16, 14, 12, 18, 6, 13, 11, 20, 4, 15] with rowsCount = 5 and colsCount = 4, the desired output matrix is shown below. Note that iterating the matrix following the arrows corresponds to the order of numbers in the original array.

https://leetcode.com/problems/snail-traversal/

예시

코드

/**
 * @param {number} rowsCount
 * @param {number} colsCount
 * @return {Array<Array<number>>}
 */
Array.prototype.snail = function(rowsCount, colsCount) {
    if(rowsCount * colsCount !== this.length) return [];
    
    const arr = Array.from(new Array(rowsCount), () => new Array(colsCount).fill(0));
    
    // 하, 우, 상, 우
    const dx = [1, 0, -1, 0];
    const dy = [0, 1, 0, 1];
    
    let x = -1;
    let y = 0;
    let d = 0; 
    let idx = 0;
    
    while(idx !== this.length){
        
        let nx = x + dx[d % 4];
        let ny = y + dy[d % 4];
        
        if(nx >= rowsCount || nx < 0 ){
            d++;
        }
        else {
            x = nx;
            y = ny;
            arr[x][y] = this[idx++];
            
            // 방향이 오른쪽일 때는 바로 방향 바꿔주기
            if(d % 4 === 1 || d % 4 === 3){
                d++;
            }
        }
    };
    
    return arr;
    
    
}

/**
 * const arr = [1,2,3,4];
 * arr.snail(1,4); // [[1,2,3,4]]
 */

문제의 조건에 있듯이,

`rowsCount * colsCount !== nums.length` 일 때는 빈 배열을 리턴하였다. 그 후, `rowsCount`와 `colsCount`로 0으로 차있는 2차원 배열을 만들었다. `nums`에 있는 값들을 해당 2차원 배열에 채울 것인데, 순서가 아래 -> 오른쪽 -> 위 -> 오른쪽으로 채워진다. 따라서 `dx`와 `dy`를 하, 우, 상, 우 순으로 움질일 수 있도록 정의했고, arr의 인덱스를 의미하는 x와 y, dx와 dy의 인덱스를 의미하는 d(방향), nums의 인덱스를 의미하는 idx를 변수로 따로 정의했다.다음에 이동할 nx와 ny가 위 아래 범위를 넘어가면 방향을 바꾸어주었고, 범위 안에 있으면 arr에 값을 넣었다. 이때, 방향이 오른쪽이었을 경우 한 번만 값을 넣고 다시 방향을 바꾸어주어야 하기 때문에 방향을 확인해서 오른쪽이면 d를 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인지 여부를 판단하여 리턴해주었다.

문제

Design a Calculator class. The class should provide the mathematical operations of addition, subtraction, multiplication, division, and exponentiation. It should also allow consecutive operations to be performed using method chaining. The Calculator class constructor should accept a number which serves as the initial value of result.

• add - This method adds the given number value to the result and returns the updated Calculator.
• subtract - This method subtracts the given number value from the result and returns the updated Calculator.
• multiply - This method multiplies the result  by the given number value and returns the updated Calculator.
• divide - This method divides the result by the given number value and returns the updated Calculator. If the passed value is 0, an error "Division by zero is not allowed" should be thrown.
• power - This method raises the result to the power of the given number value and returns the updated Calculator.
• getResult - This method returns the result.

Solutions within 10-5 of the actual result are considered correct.

• Your Calculator class should have the following methods:

https://leetcode.com/problems/calculator-with-method-chaining/

예시

코드

const DIVISION_ZERO_ERROR = "Division by zero is not allowed";

class Calculator {
    
    /** 
     * @param {number} value
     */
    constructor(value) {
        this.value = value;
    }
    
    /** 
     * @param {number} value
     * @return {Calculator}
     */
    add(value){
        this.value += value;
        console.log(this);
        return this;
    }
    
    /** 
     * @param {number} value
     * @return {Calculator}
     */
    subtract(value){
        this.value -= value;
        return this;
    }
    
    /** 
     * @param {number} value
     * @return {Calculator}
     */  
    multiply(value) {
        this.value *= value;
        return this;
    }
    
    /** 
     * @param {number} value
     * @return {Calculator}
     */
    divide(value) {
        if(value === 0) throw new Error(DIVISION_ZERO_ERROR);
        this.value /= value;
        return this;
    }
    
    /** 
     * @param {number} value
     * @return {Calculator}
     */
    power(value) {
        this.value = this.value ** value;
        return this;
    }
    
    /** 
     * @return {number}
     */
    getResult() {
        return this.value;
    
    }
}

메소드 체이닝을 위해서는 각 메소드에서 this를 반환하여 Calculator 클래스 자체를 반환해주어야 한다. 따라서 생성자 함수인 constructor()와 연산 결과를 리턴할 getResult() 메소드를 제외한 나머지 메소드에서 this를 리턴해주었다.