Maximum subarray sum ( 5 kyu )

문제

The maximum sum subarray problem consists in finding the maximum sum of a contiguous subsequence in an array or list of integers:

maxSequence([-2, 1, -3, 4, -1, 2, 1, -5, 4])
// should be 6: [4, -1, 2, 1]

Easy case is when the list is made up of only positive numbers and the maximum sum is the sum of the whole array. If the list is made up of only negative numbers, return 0 instead.

Empty list is considered to have zero greatest sum. Note that the empty list or array is also a valid sublist/subarray.

배열에서 연속된 원소의 합이 최대일 때를 구하는 문제

풀이

var maxSequence = function(arr){
  let max = 0, sum = 0, j;
  for ( let i = 0; i < arr.length; i++ ) {
    sum = 0;
    j = i;
    while ( sum <= max ) {
      sum += arr[j]
      if ( sum > max ) {
        max = sum;
      }
      j++;
    }
  }
  return max
}

for, while로 a에 b의 원소들이 없을때까지 반복해서 리턴

다른 사람의 풀이

var maxSequence = function(arr){
  var min = 0, ans = 0, i, sum = 0;
  for (i = 0; i < arr.length; ++i) {
    sum += arr[i];
    min = Math.min(sum, min);
    ans = Math.max(ans, sum - min);
  }
  return ans;
}

포문 하나로 해결.

이게 더 좋은 코드


Build Tower ( 6 kyu )

문제

Build Tower by the following given argument:
number of floors (integer and always greater than 0).

for example, a tower of 3 floors looks like below

[
  '  *  ', 
  ' *** ', 
  '*****'
]

주어진 숫자만큼의 별탑을 쌓는 문제

풀이

function towerBuilder(nFloors) {
  let result = [];
  for ( let i = 1; i <= nFloors; i++ ) {
    result.push(' '.repeat(nFloors-i) + '*'.repeat(i*2-1) + ' '.repeat(nFloors-i))
  }
  return result
}

repeat메소드로 쉽게 해결

다른 사람의 풀이

function towerBuilder(n) {
  return Array.from({length: n}, function(v, k) {
    const spaces = ' '.repeat(n - k - 1);
    return spaces + '*'.repeat(k + k + 1) + spaces;
  });
}

Array.from 대체 무엇


Delete occurrences of an element if it occurs more than n times( 6 kyu )

문제

Given a list lst and a number N, create a new list that contains each number of lst at most N times without reordering. For example if N = 2, and the input is [1,2,3,1,2,1,2,3], you take [1,2,3,1,2], drop the next [1,2] since this would lead to 1 and 2 being in the result 3 times, and then take 3, which leads to [1,2,3,1,2,3].

Example

deleteNth ([1,1,1,1],2) // return [1,1]
deleteNth ([20,37,20,21],1) // return [20,37,21]

주어진 배열에서 같은 원소가 최대 n번만 나오게 한뒤 리턴하는 문제

풀이

function deleteNth(arr,n){
  let obj = {}, result = [];
  for ( let i = 0; i < arr.length; i++ ) {
    if ( !obj[arr[i]] ) {
      obj[arr[i]] = 1;
      result.push(arr[i]);
    } else if ( obj[arr[i]] === n ) {
      continue;
    } else {
      obj[arr[i]]++;
      result.push(arr[i]);
    }
  }
  return result;
}

obj에 조건을 달아 새로운 배열 result에 담아 리턴하는 방법.

다른 사람의 풀이

function deleteNth(arr,x) {
  var cache = {};
  return arr.filter(function(n) {
    cache[n] = (cache[n]||0) + 1;
    return cache[n] <= x;
  });
}

필터로 이렇게 접근하는 방법 좋은것 같고,

if문 대신에 파이프 ||로 처리한 방법도 굿


'자료구조, 알고리즘 > Codewars 문제' 카테고리의 다른 글

Maximum subarray sum ( 5 kyu )  (0) 2017.12.04
Build Tower ( 6 kyu )  (0) 2017.12.03
Find the divisors! ( 6 kyu )  (0) 2017.11.30
Array.diff ( 6 kyu )  (0) 2017.11.30
Are they the "same"? ( 6 kyu )  (0) 2017.11.30

Find the divisors! ( 6 kyu )

문제

Create a function named divisors/Divisors that takes an integer and returns an array with all of the integer’s divisors(except for 1 and the number itself). If the number is prime return the string ‘(integer) is prime’ (null in C#) (use Either String a in Haskell and Result, String> in Rust).

Example:

divisors(12); // should return [2,3,4,6]
divisors(25); // should return [5]
divisors(13); // should return "13 is prime"

You can assume that you will only get positive integers as inputs.

약수 찾기

풀이

function divisors(integer) {
  let result = [];
  for ( let i = 2; i < integer; i++ ) {
    if ( Number.isInteger(integer/i) ) {
      result.push(i)
    }
  }
  return result.length !== 0 ? result : `${integer} is prime`;
};

설명할게 없다.

다른 좋은방법이 있을것 같은 문제

다른 사람의 풀이

없네..


Array.diff ( 6 kyu )

문제

Your goal in this kata is to implement an difference function, which subtracts one list from another.

It should remove all values from list a, which are present in list b.

array_diff([1,2],[1]) == [2]

If a value is present in b, all of its occurrences must be removed from the other:

array_diff([1,2,2,2,3],[2]) == [1,3]

b의 원소를 a에서 지워서 리턴하는 문제

풀이

function array_diff(a, b) {
  for ( let i = 0; i < b.length; i++ ) {
    while ( a.indexOf(b[i]) !== -1 ) {
      a = a.slice(0, a.indexOf(b[i])).concat(a.slice(a.indexOf(b[i])+1, a.length));
    }
  }
  return a;
}

for, while로 a에 b의 원소들이 없을때까지 반복해서 리턴

다른 사람의 풀이

function array_diff(a, b) {
  return a.filter(function(x) { return b.indexOf(x) == -1; });
}

고수..


Are they the "same"? ( 6 kyu )

문제

Given two arrays a and b write a function comp(a, b) (compSame(a, b) in Clojure) that checks whether the two arrays have the “same” elements, with the same multiplicities. “Same” means, here, that the elements in b are the elements in a squared, regardless of the order.

Examples

Valid arrays

a = [121, 144, 19, 161, 19, 144, 19, 11]  
b = [121, 14641, 20736, 361, 25921, 361, 20736, 361]

comp(a, b) returns true because in b 121 is the square of 11, 14641 is the square of 121, 20736 the square of 144, 361 the square of 19, 25921 the square of 161, and so on. It gets obvious if we write b’s elements in terms of squares:

a = [121, 144, 19, 161, 19, 144, 19, 11] 
b = [11*11, 121*121, 144*144, 19*19, 161*161, 19*19, 144*144, 19*19]

array1 배열의 인자들을 제곱한 값이 array2에 있는지 비교하는 문제

풀이

function comp(array1, array2){
  if ( !array1 || !array2 ) return false;
  array1 = array1.map(a => { return a*a }).sort((a,b) => { return b-a });
  array2 = array2.sort((a,b) => { return b-a });
  for ( let i = 0; i < array1.length; i++ ) {
    if ( array1[i] !== array2[i] ) {
      return false;
    }
  }
  return true;
}

완전 별로인 풀이같다.

예외처리를 두개나 걸고 소트로 그냥 비교하는 방법

[1,2,3] === [1,2,3] 은 false인걸 처음알았다.. 역시난 허접

다른 사람의 풀이

function comp(array1, array2) {
  if(array1 == null || array2 == null) return false;
  array1.sort((a, b) => a - b); array2.sort((a, b) => a - b);
  return array1.map(v => v * v).every((v, i) => v == array2[i]);
}

예외처리 하나 걸고 소트로 비교


'자료구조, 알고리즘 > Codewars 문제' 카테고리의 다른 글

Find the divisors! ( 6 kyu )  (0) 2017.11.30
Array.diff ( 6 kyu )  (0) 2017.11.30
Your order, please ( 6 kyu )  (0) 2017.11.30
Greed is Good ( 5 kyu )  (0) 2017.11.30
Two Joggers ( 5 kyu )  (0) 2017.11.30

Your order, please ( 6 kyu )

문제

Your task is to sort a given string. Each word in the String will contain a single number. This number is the position the word should have in the result.

Note: Numbers can be from 1 to 9. So 1 will be the first word (not 0).

If the input String is empty, return an empty String. The words in the input String will only contain valid consecutive numbers.

For an input: “is2 Thi1s T4est 3a” the function should return “Thi1s is2 3a T4est”

your_order("is2 Thi1s T4est 3a")
[1] "Thi1s is2 3a T4est"

문자열에서 단어마다 숫자가 있는데 숫자 순서대로 나열하는 문제

풀이

function order(words){
  let arr = words.split(' ');
  let num = [];
  for ( let i = 0; i < arr.length; i++ ) {
    num[arr[i].match(/[1-9]/)] = arr[i]
  }
  num.shift();
  return num.join(' ');
}

단어마다 쪼개서 배열로 arr에 담고, num이라는 배열에 숫자 순서대로 담아 join으로 합쳐 리턴

다른 사람의 풀이

function order(words){

  return words.split(' ').sort(function(a, b){
      return a.match(/\d/) - b.match(/\d/);
   }).join(' ');
}

생각한 방법보다 훨씬 간단하게 접근

신박하군


'자료구조, 알고리즘 > Codewars 문제' 카테고리의 다른 글

Array.diff ( 6 kyu )  (0) 2017.11.30
Are they the "same"? ( 6 kyu )  (0) 2017.11.30
Greed is Good ( 5 kyu )  (0) 2017.11.30
Two Joggers ( 5 kyu )  (0) 2017.11.30
First non-repeating character ( 5 kyu )  (0) 2017.11.30

Greed is Good ( 5 kyu )

문제

Greed is a dice game played with five six-sided dice. Your mission, should you choose to accept it, is to score a throw according to these rules. You will always be given an array with five six-sided dice values.

 Three 1's => 1000 points
 Three 6's =>  600 points
 Three 5's =>  500 points
 Three 4's =>  400 points
 Three 3's =>  300 points
 Three 2's =>  200 points
 One   1   =>  100 points
 One   5   =>   50 point

A single die can only be counted once in each roll. For example, a “5” can only count as part of a triplet (contributing to the 500 points) or as a single 50 points, but not both in the same roll.

 Throw       Score
 ---------   ------------------
 5 1 3 4 1   50 + 2 * 100 = 250
 1 1 1 3 1   1000 + 100 = 1100
 2 4 4 5 4   400 + 50 = 450

다섯개의 주사위를 던져서 위에 있는 스코어판 대로 점수를 매겨 리턴

풀이

function score( dice ) {
  let result = 0;
  let three = { 1: 1000, 2: 200, 3: 300, 4: 400, 5: 500,6: 600 }
  let one = { 1: 100, 5: 50 };
  let obj = {};
  for ( let i = 0; i < 5; i++ ) {
    if ( obj[dice[i]] ) {
      obj[dice[i]]++;
    } else {
      obj[dice[i]] = 1;
    }
  }
  for ( let i in obj ) {
    if ( obj[i] >= 3 ) {
      result += three[i];
      obj[i] -= 3
    }
    if ( one[i] ) {
      result += one[i]*obj[i]
    }
  }
  return result;
}

three, one에 각각 점수를 객체로 담아놓고,

첫번째 포문에서 주사위의 값들을 obj에 담아 obj로 다시 포문을 돌려 one과 three를 사용해 점수를 추가 후 리턴

다른 사람의 풀이

function score( dice ) {
  var dc = [0,0,0,0,0,0];
  var tdr = [1000,200,300,400,500,600];
  var sdr = [100,0,0,0,50,0];
  dice.forEach(function(x){ dc[x-1]++; });
  return dc.reduce(function(s,x,i){ 
    return s + (x >= 3? tdr[i] : 0) + sdr[i]*(x % 3);
  },0);
}

배열로만 인덱스를 구성해 이중포문으로 구성

코드는 별로 좋은것 같지는 않지만 모양이 예뻐서 가져옴.


+ Recent posts