Algorithm - Programmers & LeetCode Problems 3

이소라·2023년 6월 19일
0

Algorithm

목록 보기
49/77
post-custom-banner

LeetCode Problem (easy) : Count Negative Numbers in a Sorted Matrix

  • Given a m x n matrix grid which is sorted in non-increasing order both row-wise and column-wise, return the number of negative numbers in grid.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 100
  • -100 <= grid[i][j] <= 100

Example

  • Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
  • Output: 8
  • Example: There are 8 negatives number in the matrix.

Solution

/**
 * @param {number[][]} grid
 * @return {number}
 */
var countNegatives = function(grid) {
    const rowLength = grid.length;
    let result = 0;
    let rowArr, negativeIndex, negativeCount, colLength;
    for (let i = 0; i < rowLength; i++) {
        rowArr = grid[i];
        colLength = rowArr.length;
        negativeIndex = rowArr.findIndex(num => num < 0);
        negativeCount = negativeIndex !== -1 ? colLength - negativeIndex : 0;
        result += negativeCount;
    }
    return result;
};



LeetCode Problem (medium) : Top K Frequent Elements

  • Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Constraints

  • 1 <= nums.length <= 105
  • -10^4 <= nums[i] <= 10^4
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Examples

  • Example 1

    • Input : nums = [1,1,1,2,2,3], k = 2
    • Output : [1,2]

  • Example 2

    • Input : nums = [1], k = 1
    • Output : [1]

Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    const numMap = new Map();
    nums.forEach((number) => {
        numMap.set(number, (numMap.get(number) || 0) + 1);
    });
    const orderedNumArr = [...numMap.entries()].sort((a, b) => b[1] - a[1]).map(([number,_]) => number);
    return orderedNumArr.slice(0, k);
    
};



Programmers Problem (lev.2) : 이진 변환 반복하기

  • 0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.

    • x의 모든 0을 제거합니다.
    • x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.
    • 예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.

  • 0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

  • s의 길이는 1 이상 150,000 이하입니다.
  • s에는 '1'이 최소 하나 이상 포함되어 있습니다.

입출력 예

  • Example 1
    • Input : "110010101001"
    • Output : [3, 8]
회차이진 변환 이전제거할 0의 개수0 제거 후 길이이진 변환 결과
1"110010101001"66"110"
2"110"12"10"
3"10"11"1"
  • Example 2
    • Input : "01110"
    • Output : [3, 3]
회차이진 변환 이전제거할 0의 개수0 제거 후 길이이진 변환 결과
1"01110"23"11"
2"11"02"10"
3"10"11"1"
  • Example 3
    • Input : "1111111"
    • Output : [4, 1]
회차이진 변환 이전제거할 0의 개수0 제거 후 길이이진 변환 결과
1"1111111"07"111"
2"111"03"11"
3"11"02"10"
4"10"11"1"

Solution

function solution(s) {
    const convertToBinary = (numStr, zeroCount, operationCount) => {
        if (numStr === '1') {
            return [operationCount, zeroCount];
        }
        
        const naturalNumber = numStr.split('').filter((num) => {
            if (num === '0') {
                zeroCount += 1;
                return false;
            }
            return true;
        }).join('');
        
        const binaryNumber = naturalNumber.length.toString(2);
        operationCount += 1;
        
        return convertToBinary(binaryNumber, zeroCount, operationCount);
    };
    
    return convertToBinary(s, 0, 0);
}



Programmers Problem : 파일명 정렬

  • 무지는 단순한 문자 코드 순이 아닌, 파일명에 포함된 숫자를 반영한 정렬 기능을 저장소 관리 프로그램에 구현하기로 했다.

  • 소스 파일 저장소에 저장된 파일명은 100 글자 이내로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.

  • 파일명은 크게 HEAD, NUMBER, TAIL의 세 부분으로 구성된다.

    • HEAD는 숫자가 아닌 문자로 이루어져 있으며, 최소한 한 글자 이상이다.
    • NUMBER는 한 글자에서 최대 다섯 글자 사이의 연속된 숫자로 이루어져 있으며, 앞쪽에 0이 올 수 있다. 0부터 99999 사이의 숫자로, 00000이나 0101 등도 가능하다.
    • TAIL은 그 나머지 부분으로, 여기에는 숫자가 다시 나타날 수도 있으며, 아무 글자도 없을 수 있다.
파일명HEADNUMBERTAIL
foo9.txtfoo9.txt
foo010bar020.zipfoo010bar020.zip
F-15F-15

  • 파일명을 세 부분으로 나눈 후, 다음 기준에 따라 파일명을 정렬한다.

    • 파일명은 우선 HEAD 부분을 기준으로 사전 순으로 정렬한다. 이때, 문자열 비교 시 대소문자 구분을 하지 않는다. MUZI와 muzi, MuZi는 정렬 시에 같은 순서로 취급된다.
    • 파일명의 HEAD 부분이 대소문자 차이 외에는 같을 경우, NUMBER의 숫자 순으로 정렬한다. 9 < 10 < 0011 < 012 < 13 < 014 순으로 정렬된다. 숫자 앞의 0은 무시되며, 012와 12는 정렬 시에 같은 같은 값으로 처리된다.
    • 두 파일의 HEAD 부분과, NUMBER의 숫자도 같을 경우, 원래 입력에 주어진 순서를 유지한다. MUZI01.zip과 muzi1.png가 입력으로 들어오면, 정렬 후에도 입력 시 주어진 두 파일의 순서가 바뀌어서는 안 된다.

  • 무지를 도와 파일명 정렬 프로그램을 구현하라.

입력 형식

  • 입력으로 배열 files가 주어진다.
    • files는 1000 개 이하의 파일명을 포함하는 문자열 배열이다.
    • 각 파일명은 100 글자 이하 길이로, 영문 대소문자, 숫자, 공백(" "), 마침표("."), 빼기 부호("-")만으로 이루어져 있다. 파일명은 영문자로 시작하며, 숫자를 하나 이상 포함하고 있다.
    • 중복된 파일명은 없으나, 대소문자나 숫자 앞부분의 0 차이가 있는 경우는 함께 주어질 수 있다. (muzi1.txt, MUZI1.txt, muzi001.txt, muzi1.TXT는 함께 입력으로 주어질 수 있다.)

Solution

  • NUMBER의 startIndex와 endIndex를 구한 후, slice 메서드로 잘라서 HEAD, NUMBER를 구하는 방법 (참고)
function solution(files) {
    files.sort((a, b) => {
        const firstFileNames = tokenizeFileName(a);
        const secondFileNames = tokenizeFileName(b);
        return compare(firstFileNames, secondFileNames);
    });
    return files;
}

function tokenizeFileName(fileName) {
    let startIndex = 0;
    let endIndex = 0;
    for (let index = 0; index < fileName.length; index++) {
        if (!startIndex && !isNaN(parseInt(fileName[index]))) {
            startIndex = index;
        }
        if (startIndex && isNaN(parseInt(fileName[index + 1]))) {
            endIndex = index;
            break;
        }
    }
    
    const HEAD = fileName.slice(0, startIndex);
    const NUMBER = fileName.slice(startIndex, endIndex + 1);
    return [HEAD.toUpperCase(), parseInt(NUMBER)];
}

function compare(firstFileNames, secondFileNames) {
    const [firstHead, firstNumber] = firstFileNames;
    const [secondHead, secondNumber] = secondFileNames;
    if (firstHead < secondHead) {
        return -1;
    } else if (firstHead > secondHead) {
        return 1;
    } else {
        return firstNumber - secondNumber;
    }
}
  • 정규표현식을 이용한 깔끔한 풀이 (참고)
function solution(files) {
    files.sort((a, b) => {
        const aHead = a.match(/^\D+/)[0].toLowerCase();
        const bHead = b.match(/^\D+/)[0].toLowerCase();
        
        if (aHead < bHead) {
            return -1;
        }
        if (aHead > bHead) {
            return 1;
        }
        
        const aNumber = Number(a.match(/\d+/)[0]);
        const bNumber = Number(b.match(/\d+/)[0]);
        return aNumber - bNumber;
    });
    return files;
}
profile
이소라
이전 포스트

Algorithm - Programmers Problems (week 12)

다음 포스트

Algorithm - Programmers & LeetCode Problems 4

post-custom-banner

0개의 댓글