Algorithm - Programmers & LeetCode Problems

Programmers Problem (lev. 2) : 최솟값 만들기

• 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다.
  배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. (단, 각 배열에서 k번째 숫자를 뽑았다면 다음에 k번째 숫자는 다시 뽑을 수 없습니다.)

  • 예를 들어 A = [1, 4, 2] , B = [5, 4, 4] 라면
    • A에서 첫번째 숫자인 1, B에서 첫번째 숫자인 5를 뽑아 곱하여 더합니다. (누적된 값 : 0 + 5(1x5) = 5)
    • A에서 두번째 숫자인 4, B에서 세번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 5 + 16(4x4) = 21)
    • A에서 세번째 숫자인 2, B에서 두번째 숫자인 4를 뽑아 곱하여 더합니다. (누적된 값 : 21 + 8(2x4) = 29)
  • 즉, 이 경우가 최소가 되므로 29를 return 합니다.

• 배열 A, B가 주어질 때 최종적으로 누적된 최솟값을 return 하는 solution 함수를 완성해 주세요.

제한사항

• 배열 A, B의 크기 : 1,000 이하의 자연수
• 배열 A, B의 원소의 크기 : 1,000 이하의 자연수

Solution

function solution(A,B){
    let answer = 0;

    A.sort((a,b) => a - b);
    B.sort((a,b) => b - a);
    
    for (let i = 0; i < A.length; i++) {
        answer += A[i] * B[i];
    }

    return answer;
}

Programmers Problem (lev. 1) : 크키가 작은 부분문자열

• 숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요.
  • 예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다.

제한사항

• 1 ≤ p의 길이 ≤ 18
• p의 길이 ≤ t의 길이 ≤ 10,000
• t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.

입출력 예

• 입력 : t = "3141592", p = "271"
• 출력 : 2
• 설명 :
  • p의 길이가 1이므로 t의 부분문자열은 "5", "0", 0", "2", "2", "0", "8", "3", "9", "8", "7", "8"이며, 이중 7보다 작거나 같은 숫자는 "5", "0", "0", "2", "2", "0", "3", "7" 이렇게 8개가 있습니다.

Solution

function solution(t, p) {
    const pLength = p.length;
    const pNum = Number(p);
    let answer = 0;
    let curNum;
    
    for (let i = 0; i < t.length - pLength + 1; i++) {
        curNum = Number(t.substring(i, i + pLength));
        if (curNum <= pNum) {
            answer++;
        }
    }
    return answer;
}

Programmers Problem (lev. 2) : 방금그곡

• 라디오를 자주 듣는 네오는 라디오에서 방금 나왔던 음악이 무슨 음악인지 궁금해질 때가 많다. 그럴 때 네오는 다음 포털의 '방금그곡' 서비스를 이용하곤 한다. 방금그곡에서는 TV, 라디오 등에서 나온 음악에 관해 제목 등의 정보를 제공하는 서비스이다.

• 네오는 자신이 기억한 멜로디를 가지고 방금그곡을 이용해 음악을 찾는다. 그런데 라디오 방송에서는 한 음악을 반복해서 재생할 때도 있어서 네오가 기억하고 있는 멜로디는 음악 끝부분과 처음 부분이 이어서 재생된 멜로디일 수도 있다. 반대로, 한 음악을 중간에 끊을 경우 원본 음악에는 네오가 기억한 멜로디가 들어있다 해도 그 곡이 네오가 들은 곡이 아닐 수도 있다. 그렇기 때문에 네오는 기억한 멜로디를 재생 시간과 제공된 악보를 직접 보면서 비교하려고 한다. 다음과 같은 가정을 할 때 네오가 찾으려는 음악의 제목을 구하여라.

  • 방금그곡 서비스에서는 음악 제목, 재생이 시작되고 끝난 시각, 악보를 제공한다.
  • 네오가 기억한 멜로디와 악보에 사용되는 음은 C, C#, D, D#, E, F, F#, G, G#, A, A#, B 12개이다.
  • 각 음은 1분에 1개씩 재생된다. 음악은 반드시 처음부터 재생되며 음악 길이보다 재생된 시간이 길 때는 음악이 끊김 없이 처음부터 반복해서 재생된다. 음악 길이보다 재생된 시간이 짧을 때는 처음부터 재생 시간만큼만 재생된다.
  • 음악이 00:00를 넘겨서까지 재생되는 일은 없다.
  • 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환한다. 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환한다.
  • 조건이 일치하는 음악이 없을 때에는 “(None)”을 반환한다.

입력 형식

• 입력으로 네오가 기억한 멜로디를 담은 문자열 m과 방송된 곡의 정보를 담고 있는 배열 musicinfos가 주어진다.
  • m은 음 1개 이상 1439개 이하로 구성되어 있다.
  • musicinfos는 100개 이하의 곡 정보를 담고 있는 배열로, 각각의 곡 정보는 음악이 시작한 시각, 끝난 시각, 음악 제목, 악보 정보가 ','로 구분된 문자열이다.
    • 음악의 시작 시각과 끝난 시각은 24시간 HH:MM 형식이다.
    • 음악 제목은 ',' 이외의 출력 가능한 문자로 표현된 길이 1 이상 64 이하의 문자열이다.
    • 악보 정보는 음 1개 이상 1439개 이하로 구성되어 있다.

출력 형식

• 조건과 일치하는 음악 제목을 출력한다.

입출력 예시

• 예시 1

  • 입력 : m = "ABCDEFG", musicinfos = ["12:00,12:14,HELLO,CDEFGAB", "13:00,13:05,WORLD,ABCDEF"]
  • 출력 : "HELLO"
  • 설명 : HELLO는 길이가 7분이지만 12:00부터 12:14까지 재생되었으므로 실제로 CDEFGABCDEFGAB로 재생되었고, 이 중에 기억한 멜로디인 ABCDEFG가 들어있다.

• 예시 2

  • 입력 : m = "ABC", musicinfos = ["12:00,12:14,HELLO,C#DEFGAB", "13:00,13:05,WORLD,ABCDEF"]
  • 출력 : "FOO"
  • 설명 : HELLO는 C#DEFGABC#DEFGAB로, WORLD는 ABCDE로 재생되었다. HELLO 안에 있는 ABC#은 기억한 멜로디인 ABC와 일치하지 않고, WORLD 안에 있는 ABC가 기억한 멜로디와 일치한다.

Solution

• #이 들어간 음을 어떻게 구분해야 할지 몰랐는데, 다른 사람 풀이를 참고하여 replace와 정규표현식을 사용하여 풀었다. 그리고 정해진 길이만큼 문자열을 더해주는 padEnd 메서드에 대해서 알게 되었다.

function solution(m, musicinfos) {
    const music = m.replace(/(C|D|F|G|A)#/g, (_, a) => a.toLowerCase());
    const musicLength = m.length;
    
    const calculatePlayTime = (start, end) => {
        const [startHour, startMinute] = start.split(':').map(Number);
        const [endHour, endMinute] = end.split(':').map(Number);
        const startTime = startHour * 60 + startMinute;
        const endTime = endHour * 60 + endMinute;
        return endTime - startTime;
    };
    
    const playedMusicInfos = musicinfos.map((infos, index) => {
        let [start, end, name, melody] = infos.split(',');
        const playTime = calculatePlayTime(start, end);
        melody = melody.replace(/(C|D|F|G|A)#/g, (_, a) => a.toLowerCase());
        const playedMelody = melody.padEnd(playTime, melody).slice(0, playTime);
        return playedMelody.includes(music) ? [playTime, index, name] : false;
    }).filter(v => v);
    
    if (!playedMusicInfos.length) {
        return '(None)';
    }
    
    playedMusicInfos.sort((a, b) => b[0] - a[0] || a[1] - b[1]);
    return playedMusicInfos[0][2];
}

Leetcode Problem (easy) : Flipping an Image

• Given an n x n binary matrix image, flip the image horizontally, then invert it, and return the resulting image.
• To flip an image horizontally means that each row of the image is reversed.
  • For example, flipping [1,1,0] horizontally results in [0,1,1].
• To invert an image means that each 0 is replaced by 1, and each 1 is replaced by 0.
  • For example, inverting [0,1,1] results in [1,0,0].

Examples

• Example 1:

  • Input: image = [[1,1,0],[1,0,1],[0,0,0]]
  • Output: [[1,0,0],[0,1,0],[1,1,1]]
  • Explanation:
    • First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
    • Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

• Example 2:

  • Input: image = [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
  • Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
  • Explanation:
    • First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
    • Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Constraints

• n == image.length
• n == image[i].length
• 1 <= n <= 20
• mages[i][j]is either 0 or 1.

Solution

/**
 * @param {number[][]} image
 * @return {number[][]}
 */
var flipAndInvertImage = function(image) {
    const answer = [];

    for (let i = 0; i < image.length; i++) {
        const element = image[i].reverse().map((value) => value === 1 ? 0 : 1);
        answer[i] = element;
    }

    return answer;
};

Programmers Problem (lev. 2) : 땅따먹기

• 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다.

  • 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

• 마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요.

• 예를 들면,

1	2	3	5
5	6	7	8
4	3	2	1

• 로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
  • 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

Solution

• DFS를 사용하여 각 행의 최대값을 더하는 방법으로 시도했다가 틀렸다.
• 다른 사람 풀이를 참고하여 DP를 사용해서 풀었다.

function solution(land) {
    const rowLength = land.length;

    for (let rowIndex = 1; rowIndex < rowLength; rowIndex++) {
        land[rowIndex][0] += Math.max(land[rowIndex - 1][1], land[rowIndex - 1][2], land[rowIndex - 1][3]);
        land[rowIndex][1] += Math.max(land[rowIndex - 1][0], land[rowIndex - 1][2], land[rowIndex - 1][3]);
        land[rowIndex][2] += Math.max(land[rowIndex - 1][0], land[rowIndex - 1][1], land[rowIndex - 1][3]);
        land[rowIndex][3] += Math.max(land[rowIndex - 1][0], land[rowIndex - 1][1], land[rowIndex - 1][2]);
    }
    return Math.max(...land[rowLength -1]);
}

• 가독성과 효율성이 좋은 다른 사람 풀이

function solution(land) {
    var answer = 0;

    return Math.max(...land.reduce((a, c) => {
        return [
            c[0] + Math.max(a[1], a[2], a[3]),  
            c[1] + Math.max(a[0], a[2], a[3]),
            c[2] + Math.max(a[0], a[1], a[3]),
            c[3] + Math.max(a[0], a[1], a[2]),
        ];
    }, [0, 0, 0, 0]));
}