최고의 개발자 (목표)

문제

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 함수를 통과시킨 뒤, 오름차순으로 정렬하였다.

문제

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

아래 <그림 1>과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다.

전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다.

전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 <그림 2>의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의 네 개의 색종이로 나눈다. 이와 같은 과정을 잘라진 종이가 모두 하얀색 또는 모두 파란색으로 칠해져 있거나, 하나의 정사각형 칸이 되어 더 이상 자를 수 없을 때까지 반복한다.

위와 같은 규칙에 따라 잘랐을 때 <그림 3>은 <그림 1>의 종이를 처음 나눈 후의 상태를, <그림 4>는 두 번째 나눈 후의 상태를, <그림 5>는 최종적으로 만들어진 다양한 크기의 9장의 하얀색 색종이와 7장의 파란색 색종이를 보여주고 있다.

입력으로 주어진 종이의 한 변의 길이 N과 각 정사각형칸의 색(하얀색 또는 파란색)이 주어질 때 잘라진 하얀색 색종이와 파란색 색종이의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다.

출력

첫째 줄에는 잘라진 햐얀색 색종이의 개수를 출력하고, 둘째 줄에는 파란색 색종이의 개수를 출력한다.

코드

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

public class Main {
    static int N;
    static int[][] paper;
    static int white;
    static int blue;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        paper = new int[N][N];

        StringTokenizer st = null;

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());

            for(int j = 0; j < N; j++){
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        cut(0,0,N);

        System.out.println(white);
        System.out.println(blue);
    }

    /**
     *
     * @param x
     * @param y
     * @param size
     * 전부 같으려면 size*size 거나 0
     */
    static void cut(int x, int y, int size){
        int sum = 0;
        for(int i = 0; i < size; i++){
            for(int j = 0; j < size; j++){
                sum += paper[i+x][j+y];
            }
        }

        if(sum == 0){
            white++;
        }else if(sum == size*size){
            blue++;
        }else{
            cut(x, y, size/2);
            cut(x, y + size/2, size/2);
            cut(x + size/2, y, size/2);
            cut(x + size/2, y + size/2, size/2);
        }

    }
}

cut() 함수를 이용해 색종이를 잘랐다. 인자로는 현재 보고있는 색종이의 왼쪽 위의 x좌표와 y좌표, 그리고 size를 받았다. 먼저, 현재 색종이가 모두 같은 색으로 칠해져 있는지 확인해야 한다. 여러 방식이 있으나, 필자는 색종이의 적혀있는 수를 더했을 때 0이면 전부 흰색, size * size 면 전부 파란색이라고 판단하였다. 만약 0도 아니고, size*size도 아니라면, 다시 색종이를 cut() 해야 한다. 이때, 하나의 색종이의 가로와 세로의 중간 부분을 자르면 다음에 봐야하는 색종이는 4개가 되기 때문에 cut()을 4번 수행해야 한다. 

문제

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초 후 완료가 출력됨.
});

문제

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

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. 즉, 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최댓값을, 둘째 줄에는 최솟값을 출력한다. 연산자를 어떻게 끼워넣어도 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;

// 0 -> + 기호
// 1 -> - 기호
// 2 -> x 기호
// 3 -> ÷ 기호
public class Main {
    static int[] numbers;
    static int[] picked;
    static LinkedList<Integer> operators; // 연산자 모음
    static boolean[] visited; // 연산자 방문 여부 저장
    static int N; 

    static int min = Integer.MAX_VALUE;
    static int max = Integer.MIN_VALUE;

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

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

        numbers = new int[N];
        visited = new boolean[N-1];
        picked = new int[N-1];
        operators = new LinkedList<>();

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

        for(int i = 0; i < N; i++){
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < 4; i++){
            int cnt = Integer.parseInt(st.nextToken());

            for(int j = 0; j < cnt; j++){
                operators.push(i);
            }
        }

        permutation(0);

        System.out.println(max);
        System.out.println(min);
    }

    /**
     * 
     * @param cnt : 현재까지 선택한 요소의 개수
     */
    static void permutation(int cnt){
        if(cnt == N-1){
            getMinMaxValue();
            return;
        }

        for(int i = 0; i < N-1; i++){
            if(visited[i]) continue;

            visited[i] = true;
            picked[cnt] = operators.get(i);

            permutation(cnt+1);

            visited[i] = false;
        }

    }

    static void getMinMaxValue(){
        int value = numbers[0];

        for(int i = 0; i < N-1; i++){
            value = calculate(value, numbers[i+1], picked[i]);
        }

        if(value < min) min = value;
        if(value > max) max = value;
    }

    static int calculate(int num1, int num2, int operator){
        int result = 0;

        switch (operator){
            case 0:
                result = num1 + num2;
                break;
            case 1:
                result = num1 - num2;
                break;
            case 2:
                result = num1 * num2;
                break;
            case 3:
                result = num1 / num2;
                break;
        }

        return result;
    }

}

순열로 문제를 풀었다. 각 연산자를 0, 1, 2, 3으로 맵핑하였고, caculate 함수에서 num1과 num2를 계산해주었다. 또한 getMinMaxValue() 함수에서 value 값을 누적해가며 최종 값을 계산하였고, min과 max 값을 갱신하였다.

문제

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

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

public class baek_10816_숫자카드2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        Map<Integer, Integer> numbers = new HashMap<>();

        int N = Integer.parseInt(br.readLine());
        String[] strs = br.readLine().split(" ");

        for(int i = 0; i < strs.length; i++){
            int number = Integer.parseInt(strs[i]);
            numbers.put(number, numbers.getOrDefault(number, 0) + 1);
        }

        int M = Integer.parseInt(br.readLine());
        String[] targets = br.readLine().split(" ");

        for(int i = 0; i < targets.length; i++){
            int target = Integer.parseInt(targets[i]);
            sb.append(numbers.getOrDefault(target, 0)).append(" ");
        }
        System.out.print(sb.toString());
    }
}

시간 제한이 1초인 것을 보고 절대 이중포문으로 풀면 안된다고 생각했다. 자료구조 중 Map이 떠올랐고 key에는 숫자 카드의 정수를 저장했고, value에는 해당 key가 등장한 횟수를 저장했다. 상근이가 갖고 있는 개수를 알고 싶은 숫자카드가 상근이가 갖고 있지 않을 수도 있기 때문에 map에서 가져올 때 getOrDefault를 이용해서 처리를 해주었다.

처음에는 StringBuilder를 사용하지 않았는데, 시간초과가 나서 사용하는 것으로 변경하였다.