최고의 개발자 (목표)

문제

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)`의 시간 복잡도를 보통 가진다고 설명한다.