최고의 개발자 (목표)

문제

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

문제

https://www.acmicpc.net/problem/2493

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

코드

package barkingDog.stack;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static class Node{
        int idx;
        int value;

        public Node(int idx, int value){
            this.idx = idx;
            this.value = value;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        Stack<Node> stack = new Stack<>();

        StringBuilder sb = new StringBuilder();

        for(int i = 1; i <= N; i++){
            int v = Integer.parseInt(st.nextToken());

            while(true){
                // 스택에 아무 것도 없으면
                if(stack.isEmpty()){
                    // 현재 값을 스택에 넣기
                    // 내 앞에 값이 없으니(큰 값이 없으니) 0 넣기
                    stack.push(new Node(i, v));
                    sb.append("0 ");
                    break;
                }

                // 스택에 값이 있으면
                Node node = stack.peek();

                // 스택에 있는 값보다 현재 값이 작으면
                if(node.value < v){
                    // 스택에 있는 값 뽑기
                    // 나보다 큰 값이 있거나 스택이 빌 때까지
                    // 계속 뽑게 됨
                    stack.pop();
                }
                // 스택에 있는 값보다 현재 값이 크거나 같으면
                // 스택에 있는 값이 신호를 받을 것임!
                else{
                    // 스택에 있는 값의 인덱스를 정답에 추가
                    // 스택에 현재 값 추가하기
                    sb.append(node.idx).append(" ");
                    stack.push(new Node(i, v));
                    break;
                }


            }
        }

        System.out.println(sb.toString());
    }
}

현재 탑보다 높은 탑 중 가장 왼쪽으로 현재 탑과 가까운 탑이 신호를 수신한다. 방향도 한 방향이며, 나랑 가장 가까운 값을 확인하는 것이기 때문에 스택을 사용해 문제를 풀었다. 결과는 stringbuilder에 중간 중간 추가하였다.

주석에 자세하게 작성해놓았지만, 스택이 비어있을 때는 현재 탑의 높이를 스택에 넣고, 내 앞에 값이 없다는 것은 나보다 큰 값이 없다는 얘기이므로 0도 같이 sb에 추가해주었다. 스택에 값이 있을 때는 스택의 가장 상단에 있는 값과 현재 값을 비교해 현재 값보다 큰 값이 나올 때까지 계속 스택에서 뽑는다. 현재 값보다 큰 값이 스택에 최상단에 있게 되면 그 값을 stringbuilder에 추가하고 스택에 현재 값을 넣는다.

이때, 현재 탑의 높이보다 큰 값이 나올 때까지 계속 뽑아도 되는 이유가 궁금할 수 있는데, 현재 값의 오른쪽에 있는 탑들 중 현재 값보다 낮은 높이인 탑의 입장에서는 현재 탑의 왼쪽 탑 중 현재 탑보다 높은 탑이 없다면 어차피 현재 탑이 신호를 수신할 것이고, 현재 탑의 높이는  나중에 스택에 넣기 때문에 상관없다. 또한, 현재 탑의 오른쪽에 있는 탑들 중 현재 값보다 높은 높이인 탑의 입장에서는 어차피 현재 탑의 높이가 자신의 높이보다 낮기 때문에 적어도 현재 탑의 높이보다 낮은 탑들은 일단 수신을 받을 수 없음이 확실하므로 스택에서 제거되어도 상관없다.

++ 추가로 원래 입력을 적게 받는다고 생각해 Scanner를 사용하였는데, 메모리 초과가 나서 BufferedReader로 변경하여 해결했다. 문제를 읽어보니 N이 500,000까지 돼 탑을 500,000개 입력 받을 수도 있었다... Scanner와 BufferedReader의 메모리 효율이 다른 이유는 아래에 따로 정리하겠다.

(수정 예정! Scanner vs BufferedReader 의 메모리 효율)

문제

https://www.acmicpc.net/problem/1021

지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다.

지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다.

1. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다.
2. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다.
3. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다.

큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때, 그 원소를 주어진 순서대로 뽑아내는데 드는 2번, 3번 연산의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

코드

package barkingDog.deque;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int minCnt = 0;

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());


        Deque<Integer> deque = new ArrayDeque<>();

        for(int i = 1; i <= N; i++){
            deque.add(i);
        }

        for(int i = 0; i < M; i++){
            String target = st.nextToken();
            int targetIdx = 0;

            Iterator iterator = deque.iterator();

            while(iterator.hasNext()){
                if(iterator.next().toString().equals(target)){
                    break;
                }
                targetIdx++;
            }

            if(targetIdx < deque.size() - targetIdx){
                // 왼쪽으로 회전시키기
                while(deque.peekFirst() != Integer.parseInt(target)){
                    deque.add(deque.poll());
                    minCnt++;
                }

            }else{
                // 오른쪽으로 회전시키기
                while(deque.peekFirst() != Integer.parseInt(target)){
                    deque.addFirst(deque.pollLast());
                    minCnt++;
                }
            }

            // 맨 앞에 있는 target 뽑기
            deque.pollFirst();
        }

        System.out.println(minCnt);
    }
}

문제에서 뽑고 싶은 수를 제일 앞으로 위치 시켜야 1번 연산을 통해 원하는 수를 뽑을 수 있다. 또한, 최소로 2번과 3번 연산을 사용하기 위해서는 ① 현재 뽑고 싶은 target 원소의 위치를 알아내고 ②왼쪽과 오른쪽 중에서 최소로 회전할 수 있는 방향을 고른다.

① 현재 뽑고 싶은 target 원소의 인덱스를 알아내기

Iterator를 활용하였고, target 값과 같은 원소를 발견하면 break 해서 target의 인덱스를 알아냈다.

② 왼쪽 회전 vs 오른쪽 회전

왼쪽 회전을 해서 특정 원소를 맨 앞으로 이동시키는 데 걸리는 횟수는 target의 index와 같고, 오른쪽 회전을 해서 특정 원소를 맨 앞으로 이동시키는 데 걸리는 횟수는 전체 원소 개수 - target의 index와 같다.

둘 중에 더 적은 횟수인 방식을 고르고, 실제로 회전을 시켜주면서 개수도 세고 원소를 빼고 넣는 연산도 같이 해주었다. 물론 회전 횟수는 이미 구해놨으나, 원소를 빼고 넣는 연산은 필수적이기 때문에 하는 김에 같이 횟수도 정석으로 구해주었다.

문제

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로 이루어진 배열 형태를 반환한다.