[일일코딩 #35] String incrementer

Question

스트링에서 넘버만 따다가 +1 하는것. 자릿수 지키기.

https://www.codewars.com/kata/string-incrementer/javascript

Your job is to write a function which increments a string, to create a new string.

If the string already ends with a number, the number should be incremented by 1.
If the string does not end with a number. the number 1 should be appended to the new string.
Examples:

foo -> foo1

foobar23 -> foobar24

foo0042 -> foo0043

foo9 -> foo10

foo099 -> foo100

Attention: If the number has leading zeros the amount of digits should be considered.

My answer

정규식으로 number만 따다가 +1 해주고 원래 자릿수를 구해서 0을 그만큼 채워줬다.
마음에 안 듦.

function incrementString (str) {
    const numRegex = /[0-9]+/.exec(str);
    if (numRegex) {
        const numStr = numRegex.pop();

        const newNum = Number(numStr) + 1;
        const zeroNums = numStr.length - newNum.toString().length;
        const zeroStr = (zeroNums > 0) ? Array(zeroNums).fill("0").join("") : "";

        return str.replace(numStr, `${zeroStr}${newNum}`)
    }
    return `${str}1`;
}

Others' answer

Azuaron, Nakid..

function incrementString (input) {
    // 맨끝이 not a number면 그냥 + "1" 
    if(isNaN(parseInt(input[input.length - 1]))) return input + '1';

    // "001"을 넘겼다면 match는 001, p1은 00, p2는 1
    return input.replace(/(0*)([0-9]+$)/, function(match, p1, p2) {
        var up = parseInt(p2) + 1;

        // +1한 숫자 자릿수가 원본자릿수보다 크다면 0을 하나 뺀만큼 앞에 붙여주고 아니면 원본 0갯수만큼 붙여주기
        return (up.toString().length > p2.length) ? p1.slice(0, -1) + up : p1 + up;
    });
}
  • String.replace 첫번째 인자에 정규식을 넘길수 있고, 두 번째 인자에 함수를 넘길 수 있구나!
  • 정규식에 ()으로 그룹을 지어서 두번째 이후 인자로 받을 수 있구나
  • String.slice(0, -1)은 마지막 한글자를 떼는거구나

# [일일코딩 #34] Two sum

이건 쉬웠당 15분도 안걸린듯
몇년전에도 풀었던거같다 유명한 문제자너 이름도 익숙하구

Question

링크

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My answer

어제도 썼던 indexOf 써서 풀었당
for문을 돌리면서 target에서 el을 뺀 diff값이 나머지 array에 있는지 확인하면 됨.

var twoSum = function(nums, target) {
    for(let i=0; i<nums.length; i++) {
        const foundIdx = nums.indexOf(target - nums[i]);
        if (foundIdx >= 0 && foundIdx !== i) {
            return [i, foundIdx]
        }
    }
};

옛날에 푼걸 봐볼까

걍 똑같이 풀었네..

var twoSum = function(nums, target) {
  for (var i = 0; i <nums.length; i++) {
    var lastIdx = nums.lastIndexOf(target - nums[i]);
    if(lastIdx > 0) return new Array(i, lastIdx);
  }
};

[일일코딩 #33] Remove Duplicates from Sorted Array

일일코딩 #32가 2017년 6월이었고, 오늘의 일일코딩 #33은 2019년 11월이다. 2년이 넘었다.
2년만에 푼 알고리즘 문제는 아주 노답이었다고 할 수 있다.
Leetcode easy난이도 문제인데 한시간 걸렸거든.
와 정말 부끄럽다.

영어 설명을 제대로 읽지 않은 탓도 있다.
Array의 duplicated된 엘리먼트를 지우라기에 당연히 지워진 array를 반환하는줄 알았지.
그런데 반환값은 Array의 length뿐이었고 Params로 온 Array의 reference를 받아 원본 Array를 중복 없이 만드는거였다. 메모리 새로 안쓰고.

담엔 잘 읽어.

Question

Leetcode 링크
Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

즉 아래와 같다.

removeDuplicates([1,1,2]); // returns 2 (원본 Array는 [1, 2]로 modify됨)

removeDuplicates([0,0,1,1,1,2,2,3,3,4]); // returns 4 (원본 Array는 [0, 1, 2, 3]로 modify됨)

My answer

While문을 돌면서 해당 element가 Array의 맨 마지막에 있는지 확인했다.
맨 마지막이면 살려주고 아니면 splice로 제거.
정렬된 배열이라 다 뭉쳐있을테니 각 뭉치의 제일 오른쪽 애들만 남긴다는 아이디어였다.

var removeDuplicates = function(nums) {
    var count = nums.length - 1;
    while(count >= 0) {
        if(count == nums.lastIndexOf(nums[count])) {
            count--;
        } else {
            nums.splice(count, 1);
        }
    }

    return nums.length;
};

잘 되긴 한다.

성능은 후지다. 이 퍼센트가 뭔가 했더니 하위 5%, 18%더라.

Runtime: 224 ms, faster than 5.75% of JavaScript online submissions for Remove Duplicates from Sorted Array.
Memory Usage: 37.8 MB, less than 18.75% of JavaScript online submissions for Remove Duplicates from Sorted Array.

처음에 param으로 받은 Array를 reference로 고쳐야한단걸 몰랐을때는
Array.prototype.reduce로 접근했다. prev, next를 돌며 앞뒤가 다르면 새로운 Array에 push해줬음. 그건 그것나름대로 제일 앞 or 제일 뒤가 edge case라는 헛점은 있더라 – 무튼 안됨.

다른 사람들은 어케 했는지 보자

Others’ answer

Best practice

var removeDuplicates = function(nums) {
    if (nums.length == 0) return 0;
    var i = 0;
    for (var j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

첨엔 이해가 안갔다
이건 [0,0,1,1,1,2,2,3,3,4][ 0, 1, 2, 3, 4, 2, 2, 3, 3, 4 ]로 만들텐데 그럼 뒤에 더러운 숫자들이 남지 않는가?

근데 다시 Question을 읽어보니 뒤에 더러운 숫자가 있던 없던 반환한 lengthNum 길이만큼만 일치하면 되는거더라구.
문제가 여러모로 깔끔하지 못하네…

Answer by @Qfab

var removeDuplicates = function(nums) {
    nums.splice(0, nums.length, ...(new Set(nums)));
};

변태코드

[일일코딩 #32] Two Sum

[일일코딩 #32] Two Sum

Question

링크
Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

My Answer

var twoSum = function(nums, target) {
  for (var i = 0; i &lt;nums.length; i++) {
    var lastIdx = nums.lastIndexOf(target - nums[i]);
    if(lastIdx &gt; 0) return new Array(i, lastIdx);
  }
};

lastIndexOf로 풀었다. 처음엔 Array 초기화 할 때 var answerArr = []로 해서 answerArr.push(a, b)로 넣었는데 코드 줄인다고 위처럼 바꿨더니 성능이 조금 더 줄었다. 변수 할당보다 new Array 로 하는게 더 오래걸리나보다.

Other’s answer

3가지 방법을 제시함.
1. 브루트 포스: 포문 2번 돌면서 뺀 값이 있나 찾기
2. Two pass hash table: 잘 이해 안감 왜 굳이?
3. One-pass hash table: 내가 푼 방법. 뺀 값이 map에 있나 확인

[일일코딩 #31] 팩토리얼의 0꼬리 구하기

Daily Codewars #31 Factorial Tail

Question

자연수 a의 팩토리얼 수를 b진수로 고쳤을 때 뒤에 0이 얼마나 붙는지 구하는 질문이다. 4kyu짜리 문제.

codewars link

How many zeroes are at the end of the factorial of 10? 10! = 3628800, i.e. there are 2 zeroes. 16! in hexadecimal would be 0x130777758000, which has 3 zeroes.

Unfortunately, machine integer numbers has not enough precision for larger values. Floating point numbers drop the tail we need. We can fall back to arbitrary-precision ones – built-ins or from a library, but calculating the full product isn’t an efficient way to find just the tail of a factorial. Calculating 100’000! in compiled language takes around 10 seconds. 1’000’000! would be around 10 minutes, even using efficient Karatsuba algorithm

is to write a function, which will find the number of zeroes at the end of (number) factorial in arbitrary radix = base for larger numbers.

  • base is an integer from 2 to 256
  • number is an integer from 1 to 1’000’000

비하인드 스토리

점심 먹고 잠도 깰 겸 코드워즈를 틀었다. 처음엔 별 고민 없이 숫자.toString(몇진수)가 큰 수에서 overflow나길래 toString 없이 N진수로 고치는 코드를 짰다. 근데 그런 문제가 아니었음. 50 팩토리얼만 해도 콤퓨타에서 저장할 수 없으니… (팩토리얼로 변환가능해야 하는 범위는 100만까지다).
회사 옆자리 동료분께 “50!를 2진수로 바꿨을 때 뒤에 0이 얼마나 붙어요?” 여쭤보니 그건 수학 문제에 더 가깝고, ACM(대학생 프로그래밍 경시대회) 1번 문제 난이도라고 하였다(다른 분께선 그건 아니고 예선문제 정도 레베루라고…).

내가 계속 실마리를 못 잡으니 힌트를 주셨다.

h: 0의 의미를 생각해보세요
나: …
h: 50!를 10진수로 바꿨을 때 뒤에 0이 붙는 경우를 생각해보세요

My Answer

정말 실마리는 0의 의미에 있었다.
팩토리얼을 풀어해쳤을 때, 8!8*7*6*5*4*3*2*1 이다. 10진수가 0으로 끝나려면 2A * 5B10C가 저 안에 있으면 되지 않을까?
그럼 n진수 뒤의 0은 number(팩토리얼 당하는 수)를 풀어해친 수 속에 얼마나 base(진수)가 들어있는지 찾으면 되는구나.

처음엔 number를 무작정 base로 나눠갔다. 당연히 또 overflow가 났다. 나머지를 계속 곱하면서 저장하니 당연히…

function zeroes (base, number) {
  var answer = 0;
  var remain = 1;
  for (var i = number; i > 0; i--) {
    var newI = i;
    newI *= remain; // 나누고 난 나머지는 계속 곱해둠 -> overflow 원흉
    if(newI%base === 0) { // 나눠 떨어지면 answer를 증가시킴
      answer++;
      newI = Math.floor(newI/base);
    }
    remain = newI;
  }
  return answer;
}

그 다음은 basenumber 모두 소인수분해를 해서 이를 비교해보았다. 소인수분해 함수를 만들어서 돌려 썼다.

function zeroes (base, number) {
  function makePrime(num, obj) { // 소인수분해 하는 함수
    for (var i = 2; i <= num; i++) {
      var quantity = 0;
      while(num%i===0) {
        quantity++;
        num = Math.floor(num/i);
      }
      if(quantity>0){
        var originVal = obj[i];
        obj[i] = originVal? originVal + quantity : quantity;
      }
    }
    return obj;
  }

  var basePrime = makePrime(base, {});
  var numberPrime = {};
  for (var i = number; i >= 0; i--) { // 팩토리얼 for문 돌며 공용 object에 인수를 집어넣는다
    makePrime(i, numberPrime);
  }

  var answer = 0;
  var answerList = [];
  var baseLength = Object.keys(basePrime).length;
  for (var i = 0; i < baseLength; i++) { // 소인수분해한 두 object 비교
    var oName = Object.keys(basePrime)[i];
    if(!numberPrime[oName]) {
      answer = 0;
      break;
    }
    var result = Math.floor(numberPrime[oName] / basePrime[oName])
    answerList.push(result)
  }
  return Math.min.apply(null, answerList);
}

이 함수의 문제점은 zeroes(2, 524288)정도로 팩토리얼 할 수가 커지면 연산이 터지는 것이었다.
zeroes(2, 100000)크기의 연산도 4.8s나 걸린다.
자잘한 성능 최적화로는 안되고 연산 자체를 토막내야 되겠네…

더 생각해보니 number의 소인수를 굳이 모두 구할 필요 없이 base의 소인수로만 연산하면 되는거였다. base는 범위도 256까지밖에 안 된다. (e.g. base 소인수가 {2:2, 3:5}라면 number에서 2와 3의 갯수만 구하기)

function zeroes (base, number) {
  function makePrime(num, obj) { // base용 소인수분해
    for (var i = 2; i <= num; i++) {
      var quantity = 0;
      while(num%i===0) {
        quantity++;
        num = Math.floor(num/i);
      }
      if(quantity>0){
        var originVal = obj[i];
        obj[i] = quantity;
      }
    }
    return obj;
  }

  function makePrimeArray(num, obj, arr) { // number용 소인수분해: base의 키값만 돌며 인수를 구한다
    var length = arr.length;
    for (var i = 0; i < length; i++) {
      var arrKey = arr[i], quantity = 0;
      while(num>0 && num%arrKey===0) {
        quantity++;
        num = Math.floor(num/arrKey);
      }
      if(quantity>0){
        var originVal = obj[arrKey];
        obj[arrKey] = originVal? originVal + quantity : quantity;
      }
    }
    return obj;
  }

  var basePrime = makePrime(base, {}),
      numberPrime = {},
      basePrimeArr = Object.keys(basePrime),
      answer = Infinity,
      answerList = [],
      baseLength = Object.keys(basePrime).length;

  for (var i = number; i >= 0; i--) {
    makePrimeArray(i, numberPrime, basePrimeArr);
  }
  for (var prop in basePrime) {
    answer = Math.min(answer, Math.floor(numberPrime[prop] / basePrime[prop])) | 0;
  }
  return answer
}

그래서 base용, number용 소인수 구하는 함수를 나눴다.
굳이 하면 합칠 수 있겠는데… 이 때는 쫄보라서 최대한 속도 높이려고 함수 분리했음 흐훅

이렇게 바꿨더니 기존에 연산 죽던 524288이 0.2s만에 계산되더라. 오예!

pompeu2004’s Solution

이럴 줄 알았어… 남들은 엄청 짧은 코드로 풀 줄…

function zeroes (base, number) {
  var factors = {}, i = 1;
  while(++i <= base) while(base%i == 0) {
    base /= i; 
    factors[i] = (factors[i]||0) + 1;
  }
  return Math.min(...Object.keys(factors).map(factor => {
    var count = 0, i = 1;
    while((i *= factor) <= number) count += number/i>>0;
    return count/factors[factor]>>0;
  }));
}

결론

멍충 인증

[일일코딩 #30] javascript IP validation

Daily Codewars #30

Question

codewars link
Write an algorithm that will identify valid IPv4 addresses in dot-decimal format. Input to the function is guaranteed to be a single string.

Examples of valid inputs: 1.2.3.4 123.45.67.89

Examples of invalid inputs: 1.2.3 1.2.3.4.5 123.456.78.90 123.045.067.089

ip주소 validation을 하는 문제다. 참고로 0<=숫자 이게 왜 4kyu이지? 그리고 이제 honor가 113정도 되니 4큐 풀어봤자 2밖에 안오르네. 흑흑

my Solution

function isValidIP(str) {
  var arr = str.split('.');
  if(arr.length == 4) {
    return validLen = arr.filter(function(x) {
      return x !== (+x).toString() ? false : x>=0 && x<=255 ? true : false;
    }).length == arr.length;
  }
  return false;
}

split으로 나눠서 삼항연산자로 비교했다.
지금 보니 arr.length랑 filter로 나온 length를 비교할 필요 없이 그냥 4면 되는건데 바보바보 인증.

ryanzyy’s Solution

function isValidIP(str) {
  return /^(([1-9]?d|1dd|2[0-4]d|25[0-5])(.(?!$)|$)){4}$/.test(str);
}

으익 나도 정규식으로 풀걸. 그리 복잡하지 않았을텐데!

yaphi1’s Solution

function isValidIP(str) {
  return str.split('.').filter(function(v){return v==Number(v).toString() && Number(v)<256}).length==4;
}

앗 맞아(+x)라고 할필요 없었는데! 그리고 3항연산도 할필요 없었는데!
바보바보 인증

[일일코딩 #29] javascript 배열의 언덕 꼭대기 구하기

Daily Codewars #29

Question

codewars link
In this kata, you will create an object that returns the positions and the values of the “peaks” (or local maxima) of a numeric array.

For example, the array arr = [ 0 , 1 , 2 , 5 , 1 , 0 ] has a peak in position 3 with a value of 5 (arr[3] = 5)

The output will be returned as an object with two properties: pos and peaks. Both of these properties should be arrays. If there is no peak in the given array, then the output should be {pos: [], peaks: []}.

Example: pickPeaks([3,2,3,6,4,1,2,3,2,1,2,3]) returns {pos:[3,7],peaks:[6,3]}

All input arrays will be valid numeric arrays (although it could still be empty), so you won’t need to validate the input.

The first and last elements of the array will not be considered as peaks (in the context of a mathematical function, we don’t know what is after and before and therefore, we don’t know if it is a peak or not).

Also, beware of plateaus !!! [1,2,2,2,1] has a peak while [1, 2, 2, 2, 3] does not. In case of a plateau-peak, please only return the position and value of the beginning of the plateau. For example: pickPeaks([1,2,2,2,1]) returns {pos:[1],peaks:[2]}

have fun!

배열에서 언덕을 찾아 그 수와 index를 찾는 문제이다.
고원이면 고원이 생긴 처음 수와 index를 반환한다.

My Solution

function pickPeaks(arr){
  var pSlope = 0, pi = 0;
  var result = {pos:[],peaks:[]};
  if(arr.length==0) return result;

  arr.reduce(function(p, c, i) {
    if(pSlope>0 && c-p<0) {
      result.peaks.push(p);
      result.pos.push(pi);
    }
    if(c-p != 0){
      pi = i;
      pSlope = c-p;
    }
    return c;
  });
 return result;
}

Array.reduce로 current-prev 기울기를 저장했다.
기울기가 양수에서 음수로 바뀌면 그 때를 result에 저장한다.
0이 아닐때만 i와 previous Slope를 저장한다.

manvel7650’s Solution

function pickPeaks(arr){
  var result = {pos: [], peaks: []};
  if(arr.length > 2) {
    var pos = -1;
    for(var i=1; i<arr.length;i++){
      if(arr[i] > arr[i-1]) {
        pos = i;
      } else if(arr[i] < arr[i-1] && pos != -1) {
        result.pos.push(pos);
        result.peaks.push(arr[pos]);
        pos = -1;
      }
    }
  }
  return result;
}

for문을 돌려서 풀었구낭.