알고리즘 문제 풀이시 자주 사용되는 테크닉

문제풀다가 자꾸 검색하게 되는 내용들을 정리

알고리즘 문제 풀이시 자주 사용되는 테크닉

문제를 풀면서 계속 업데이트 예정!

배열이나 문자열에서 유니크한 원소 뽑아내기

const arr = [1,1,4,1,1] 

arr.filter(a => { if ( arr.indexOf(a) === arr.lastIndexOf(a) ) return a }) // [4]

위와 같이 쓰면 배열에서 유니크한 값 4를 얻을 수 있다.

문자열에서도 마찬가지로 문자열을 split으로 쪼개 filter를 사용하면 같은 결과를 얻을 수 있다.

const str = '11411'
const arr = str.split('');

arr.filter(a => { if ( arr.indexOf(a) === arr.lastIndexOf(a) ) return a }) // ['4']

배열로 결과값을 리턴하기 때문에 문자열을 원하면 toString()을 뒤에 붙여주면 되고, 넘버타입을 원하면 Number()로 감싸주면 된다.

배열이나 문자열에서 i 번째 인덱스 내용을 삭제하고 싶을 때

원본을 보존하면서 잘라내는 방법

const arr = [1, 2, 3, 4, 5];
let result = [];

result = arr.slice(0,2).concat(arr.slice(3,arr.length)) // 2번 인덱스 삭제

console.log(result) // [1, 2 ,4, 5];
console.log(arr) // [1, 2, 3, 4, 5]

원본을 훼손하며 잘라내는 방법

let arr = [1, 2, 3, 4, 5];

arr.splice(2, 1) // 2번 인덱스부터 1개를 삭제하겠다는 의미

console.log(arr); // [1, 2, 4, 5]

true, false로 결과를 리턴 할 때

if ( 조건 ) {
    return true
} else {
    return false
}

대신에

return ( 조건 )

만 써줘도 된다

배열에서 같은 값을 가지는 원소의 개수가 주어졌을 때 해당 원소를 구하는 방법

원래는 항상 obj에 배열전체를 돌면서 카운팅을 해놓고 꺼내서 쓰는식으로 했는데 너무 안좋은 방법인걸 알고 찾아보니

```
arr.find( a => arr.filter( b => a === b))

  1. 주니어개발자 2019.11.08 23:55

    자바스크립트로 알고리즘을 공부하는 학생인데요, 주소를 찾을 수 없다고 뜨는데 바뀐 주소로 수정해주실 수 있을까요? ㅠㅠ

가장 긴 팰린드롬 ( Level 2, JavaScript )

문제

앞뒤를 뒤집어도 똑같은 문자열을 palindrome이라고 합니다.
longest_palindrom함수는 문자열 s를 매개변수로 입력받습니다.
s의 부분문자열중 가장 긴 palindrom의 길이를 리턴하는 함수를 완성하세요.
예를들어 s가 토마토맛토마토이면 7을 리턴하고 토마토맛있어이면 3을 리턴합니다.

풀이

function longest_palindrom(s){
  let res = 1, j
  for ( let i = 1; i < s.length - 1; i++ ) {
    j = 1;
    while ( i >= j && i+j <= s.length && s[i+j] === s[i-j] ) {
      j++
    }
    if ( j*2 -1 > res ) res = j*2 - 1
  }
  return res
}

문자열에서 앞뒤로 하나하나 비교하면서 최대길이의 팰린드롬을 찾는 방법

안좋은코드지만 별다른 방법이 생각나지 않았음

다른 사람의 풀이

function longest_palindrom(s){
  if (s === s.split("").reverse().join("")) {
    return s.length;
  } else {
    var A = longest_palindrom(s.substring(0, s.length-1));
    var B = longest_palindrom(s.substring(1, s.length));
    return Math.max(A, B);
  }
}

재귀로 풀었는데 개모싯다

  1. 2018.03.16 12:14

    비밀댓글입니다

  2. BlogIcon takeu takeU 2018.03.16 12:50 신고

    ㅋㅋㅋ모래~

    • 쿄쿄 2018.05.05 02:50

      진짜 개머싯네요.

Coding 3min: Symmetric Sort ( 6 kyu )

문제

This is the simple version of Shortest Code series. If you need some challenges, please try the challenge version

Task:

Give you a number array(element range:1-99, array length range: 6-40), please do a "Symmetric Sort" with it.

rule: sort the number, the first smallest number at the left side, the second smaller number at the right side, and so on...

Example:

example1:                        example2:

array=[1,2,3,4,5,6,7,8,9]        array=[1,1,2,2,3,3,4,4,5]

after sort, should return:       after sort, should return:

      [1,3,5,7,9,8,6,4,2]              [1,2,3,4,5,4,3,2,1]

See more example at the testcases.

배열을 앞뒤로 한개씩 넣으면서 정렬

풀이

function sc(array){
  let result = [];
  array.sort((a,b) => { return b-a });
  while ( array.length > 0 ) {
    result.unshift(array.shift());
    if ( array.length === 0 ) break;
    result.push(array.shift());
  }
  return result.length % 2 ? result : result.reverse();
}

큰수부터 차례로 언시프트, 푸시하고 배열의 길이가 짝수라면 뒤집어서 리턴

다른 사람의 풀이

function sc(a) {
  a = a.slice().sort((x,y) => x - y);
  var left = a.filter((v,i) => i % 2 == 0);
  var right = a.filter((v,i) => i % 2 == 1).reverse();
  return left.concat(right);
}

개고슈다


Max Collatz Sequence Length ( 5 kyu )

문제

In this kata we will take a look at the length of collatz sequences. And how they evolve. Write a function that take a positive integer n and return the number between 1 and n that has the maximum Collatz sequence length and the maximum length. The output has to take the form of an array [number, maxLength] For exemple the Collatz sequence of 4 is [4,2,1], 3 is [3,10,5,16,8,4,2,1], 2 is [2,1], 1 is [1], so MaxCollatzLength(4) should return [3,8]. If n is not a positive integer, the function have to return [].

n 이하의 숫자중 콜라츠 순서를 적용해 가장 긴 길이를 리턴하는 문제

풀이

function MaxCollatzLength(n) {
  if ( n <= 0 || typeof n !== 'number' ) return [];
  let max = [1,1], temp, count;
  for ( let i = 2; i <= n; i++ ) {
    temp = i;
    count = 0;
    while ( temp > 1 ) {
      if ( temp % 2 === 0 ) temp = temp/2;
      else temp = temp*3 + 1;
      count++;
    }
    if ( count > max[1] ) max = [i, count+1]
  }
  return max;
}

temp에 n으로 시작해서 몇개의 콜라츠 순열이 나오는지 담고 연산 횟수를 count로 해서 최댓값을 리턴하는 방법

다른 사람의 풀이

별로임


Find the unique string ( 5 kyu )

문제

There is an array of strings. All strings contains similar letters except one. Try to find it!

findUniq([ 'Aa', 'aaa', 'aaaaa', 'BbBb', 'Aaaa', 'AaAaAa', 'a' ]) === 'BbBb'
findUniq([ 'abc', 'acb', 'bac', 'foo', 'bca', 'cab', 'cba' ]) === 'foo'

Strings may contain spaces. Spaces is not significant, only non-spaces symbols matters. E.g. string that contains only spaces is like empty string.

It’s guaranteed that array contains more than 3 strings.

배열중 다른 알파벳으로 구성된 단어를 찾는 문제

풀이

function findUniq(arr) {
  let newArr = arr.map(a => { return [...new Set(a.toLowerCase())].sort().join('') });
  for ( let i = 0; i < newArr.length; i++ ) {
    if ( newArr.indexOf(newArr[i]) === newArr.lastIndexOf(newArr[i]) ) return arr[i]
  }
}

Set으로 중복을 제거 후에, indexOf로 유일한 값을 찾아 리턴

다른 사람의 풀이

별로임


Extract the domain name from a URL ( 5 kyu )

문제

Write a function that when given a URL as a string, parses out just the domain name and returns it as a string. For example:

domainName("http://github.com/carbonfive/raygun") == "github" 
domainName("http://www.zombie-bites.com") == "zombie-bites"
domainName("https://www.cnet.com") == "cnet"

도메인의 이름만 뽑아 리턴하는 문제

풀이

function domainName(url){
  let arr = url.split('.');
  if ( arr[0].includes('www') ) return arr[1];
  if ( !arr[0].includes('http') ) return arr[0];
  return arr[0].slice(arr[0].indexOf('//')+2, arr[0].length);
}

.을 기준으로 배열로 잘라 www가 있으면 1번 인덱스 리턴

http가 없으면 0번 인덱스 리턴

나머지는 //를 기준으로 잘라 리턴

다른 사람의 풀이

function domainName(url){
  return url.match(/(?:http(?:s)?:\/\/)?(?:w{3}\.)?([^\.]+)/i)[1];
}

정규식이 있을 것 같았는데 따라는 못하겠다


Throwing Darts ( 6 kyu )

문제

You’ve just recently been hired to calculate scores for a Dart Board game!

Scoring specifications:

0 points - radius above 10
5 points - radius between 5 and 10 inclusive
10 points - radius less than 5
If all radiuses are less than 5, award 100 BONUS POINTS!

Write a function that accepts an array of radiuses (can be integers and/or floats), and returns a total score using the above specification.

An empty array should return 0.

Examples:

scoreThrows( [1, 5, 11] )    =>  15
scoreThrows( [15, 20, 30] )  =>  0
scoreThrows( [1, 2, 3, 4] )  =>  140

다트 점수내기, 4발 던져서 1,2,3,4에 넣으면 100점추가

풀이

function scoreThrows(radiuses){
  let point = [], result = 0;
  for ( let i of radiuses ) {
    if ( i < 5 ) {
      result += 10;
      point.push(i)
    } else if ( i >=5 && i <= 10 ) {
      result += 5;
    }
  }
  if ( [...new Set(point)].length === 4 && radiuses.length === 4 ) result += 100
  return result;
}

케이스를 많이 나눠 생각했는데 테스트케이스가 얼마 없어서 의미가 없어짐

다른 사람의 풀이

function scoreThrows(a){
 var result = a.reduce(function(p,c){
   return p + (c <5 ? 10 : c > 10 ? 0 : 5);
 },0) ;
 return result/a.length===10?result+100:result;
}

간단하게 푼 풀이


Sorting on planet Twisted-3-7 ( 6 kyu )

문제

There is a planet… in a galaxy far far away. It is exactly like our planet, but it has one difference:

The values of the digits 3 and 7 are twisted. Our 3 means 7 on the planet Twisted-3-7. And 7 means 3.

Your task is to create a method, that can sort an array the way it would be sorted on Twisted-3-7.

7 Examples from a friend from Twisted-3-7:

[1,2,3,4,5,6,7,8,9] -> [1,2,7,4,5,6,3,8,9]
[12,13,14] -> [12,14,13]
[9,2,4,7,3] -> [2,7,4,3,9]

3과 7이 바뀌었다 가정하고 정렬하는 문제

풀이

function sortTwisted37(array) {
  function change(val) {
    let result = val.toString().split('');
    for ( let i = 0; i < result.length; i++ ) {
      if ( result[i] === '3' ) result[i] = '7';
      else if ( result[i] === '7' ) result[i] = '3';
    }
    return Number(result.join(''));
  }
  let arr = array.slice().map( a => change(a) );
  arr.sort((a,b) => a-b);
  return arr.map( a => change(a) )
}

3,7을 바꿔 정렬 후 다시 바꿔줌

다른 사람의 풀이

function sortTwisted37(array) {
  const MAPPING = {7:3,3:7};

  return array.slice().sort((a,b) => twist(a) - twist(b));

  function twist(number) {
    return parseInt(number.toString().replace(/[37]/g,a=>MAPPING[a]));
  }
}

replace로 동시에 처리하려는 방법을 생각했는데 이렇게 하는 방법이 있었다.

왕꿀팁


+ Recent posts