Find The Parity Outlier ( 6 kyu )

문제

You are given an array (which will have a length of at least 3, but could be very large) containing integers. The array is either entirely comprised of odd integers or entirely comprised of even integers except for a single integer N. Write a method that takes the array as an argument and returns this “outlier” N.

For example:

[2, 4, 0, 100, 4, 11, 2602, 36]
Should return: 11 (the only odd number)

[160, 3, 1719, 19, 11, 13, -21]
Should return: 160 (the only even number)

해당 배열에 홀수 값이 1개만 있으면 그 값을 리턴, 짝수 값이 1개만 있으면 그 값을 리턴하는 문제

풀이

function findOutlier(integers){
  let arr = [];
  for ( let i = 0; i < integers.length; i++ ) {
    arr.push(Math.abs(integers[i]%2));
  }
  return arr.indexOf(1) === arr.lastIndexOf(1) ? integers[arr.indexOf(1)] : integers[arr.indexOf(0)]
}

새로운 배열에 2로나눈 절댓값을 넣어서

만약 홀수가 한개면 배열 안에 1이 한개가 있을 것이고,

짝수가 한개면 배열 안에 0이 한개 있을 것이다.

여기서 indexOf와 lastIndexOf가 같으면 그 값이 한개만 존재한다는 뜻이 삼항연산자로 해당 값을 리턴.

쓰레기같은 발상이였다..

다른 사람의 풀이

function findOutlier(int){
  var even = int.filter(a=>a%2==0);
  var odd = int.filter(a=>a%2!==0);
  return even.length==1? even[0] : odd[0];
}

필터쓰면 간단하게 풀 수 있는 문젠데, 생각조차 못했음..

filter.. 메모..


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

Take a Ten Minute Walk ( 6 kyu )  (0) 2017.11.24
IQ Test ( 6 kyu )  (0) 2017.11.24
Duplicate Encoder ( 6 kyu )  (0) 2017.11.23
Stop gninnipS My sdroW! ( 6 kyu )  (0) 2017.11.22
Persistent Bugger. ( 6 kyu )  (0) 2017.11.22

Persistent Bugger. ( 6 kyu )

문제

Write a function, persistence, that takes in a positive parameter num and returns its multiplicative persistence, which is the number of times you must multiply the digits in num until you reach a single digit.

For example:

 persistence(39) === 3 // because 3*9 = 27, 2*7 = 14, 1*4=4
                       // and 4 has only one digit

 persistence(999) === 4 // because 9*9*9 = 729, 7*2*9 = 126,
                        // 1*2*6 = 12, and finally 1*2 = 2

 persistence(4) === 0 // because 4 is already a one-digit number

한자리수가 될 때까지 각 자릿수를 곱하는 문제

풀이

let count = 0;
function persistence(num) {
  if ( num.toString().length === 1 ) {
    let result = count;
    count = 0;
    return result;
  } else {
    count++;
    return persistence(num.toString().split('').reduce((a,b) => { return parseInt(a)*parseInt(b) }))
  }
}

재귀로 한번 돌때마다 카운트를 1씩 올려주다가 길이가 한글자가 되면 결과값을 리턴해주는 방법.

마지막에 굳이 result 변수로 값을 복사해서 count를 초기화 한 이유는 count 변수 선언을 함수 밖에해서 테스트코드가 돌아갈 때 계속 count가 누적되는 문제가 있어 해결한 것.

다른 사람의 풀이

const persistence = num => {
  return `${num}`.length > 1 
    ? 1 + persistence(`${num}`.split('').reduce((a, b) => a * +b)) 
    : 0;
}

가장 좋아요를 많이 받은 코드는 아니지만 딱봐도 간단하고 명료해 맘에든 코드!


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

Take a Ten Minute Walk ( 6 kyu )  (0) 2017.11.24
IQ Test ( 6 kyu )  (0) 2017.11.24
Duplicate Encoder ( 6 kyu )  (0) 2017.11.23
Stop gninnipS My sdroW! ( 6 kyu )  (0) 2017.11.22
Find The Parity Outlier ( 6 kyu )  (0) 2017.11.22

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

2. 스택 ( Stack )  (0) 2017.11.15
1. 연결 리스트 ( Linked List )  (0) 2017.11.10
0. 자료구조  (0) 2017.10.31

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

3. 큐 ( Queue )  (0) 2017.11.17
1. 연결 리스트 ( Linked List )  (0) 2017.11.10
0. 자료구조  (0) 2017.10.31

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

3. 큐 ( Queue )  (0) 2017.11.17
2. 스택 ( Stack )  (0) 2017.11.15
0. 자료구조  (0) 2017.10.31

Search Insert Position

문제

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

정렬된 배열에서(중복된 값은 없다 가정) 타겟이 들어가야할 자리의 인덱스를 리턴해야하는 문제

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 4:

Input: [1,3,5,6], 0
Output: 0

풀이

나의 코드

const searchInsert = (nums, target) => {
    if ( nums.indexOf(target) !== -1 ) {
        return nums.indexOf(target);
    } else {
        if ( nums.length === 1 ) return nums[0] > target ? 0 : 1;
        if ( nums[0] > target ) return 0;
        for ( let i = 0; i < nums.length; i++ ) {
            if ( nums[i] < target && nums[i+1] > target) return i+1
        }
        return nums.length;
    }
};

문제자체가 간단하기 때문에 그냥 포문으로 돌아서 코드를 작성했는데
통과는 했지만 예외처리를 몇가지나 해야하는 부분에서 코드를 쓰면서도 맘에 안들었고, 좋은 방법이 있을 것이라 생각이 들었는데 Discuss 탭을 보니 이진 탐색(Binary Search)을 쓸 수 있는 문제였다.

이진 탐색 ( Binary Search ) 이란?

정렬된 배열에서 특정 값을 찾을 때 사용할 수 있는 알고리즘.

처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식.

처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최고값이 되며, 작으면 그 값은 새로운 최하값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

시간 복잡도는 O(logN)으로 빠르다.

문제를 이진탐색으로 풀면?

const searchInsert = (nums, target) => {
    let low = 0;
    let high = nums.length-1;
    while ( low <= high ) {
        let mid = parseInt((low + high)/2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] > target) {
            high = mid-1;
        } else {
            low = mid+1;
        }
    }
    return low;
}

위와같이 풀리며 매우 간단


Jump Game

문제

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

0번 인덱스를 시작점으로, 각 인덱스의 값만큼 점프해서 마지막 인덱스까지 갈 수 있는지 판별하는 문제

풀이

먼저 접근한 방법은 길이가 nums와 같은 새로운 배열에 0을 할당한 뒤에,
nums와 같은 인덱스에서부터 인덱스의 값만큼 다음 인덱스에 1씩 더해주는 방법으로 생각했음.( 이해안돼도 상관X, 쓰레기같은 방법이였음.. )

const canJump = nums => {
    let arr = [];
    for ( let i = 0; i < nums.length; i++ ) {
        arr.push(0);
    }
    for ( let i = 0; i < nums.length-1; i++ ) {
        for ( let j = i+1; j <= i+nums[i]; j++ ) {
            arr[j]++;
        }
    }
    return arr.lastIndexOf(0) === 0 ? true :false;
};

하다가 말아서 정확히는 아니고 대충 위와같이 코드를 작성했고, 시간복잡도는 n^2이 나오는데 테스트케이스에 n^2으로는 통과할 수 없을 정도로 긴 케이스가 있어서, 고민하다가 검색해보니 Greedy Algorithm이라는 방법이 있어 코드를 보고 아래와 같이 작성하니 시간복잡도 n으로 통과.

const canJump = nums => {
    let lastPos = nums.length-1;
    for ( let i = nums.length-1; i >= 0; i-- ) {
        if ( i + nums[i] >= lastPos ) {
            lastPos = i;
        }
    }
    return lastPos === 0;
};

Greedy Algorithm이란 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

매트로이드라는 구조를 가진 문제에서는 그리디 알고리즘으로 항상 최적해를 찾을 수 있다.

위의 코드를 설명해보면

nums의 마지막 인덱스 값을 lastPos에 할당해놓고, 그 값부터 시작해서 lastPos를 0까지 도달하게 하는 것. 반복문 전체를 도는것이 아닌, 최적의 판단으로 횟수를 최대한 줄여준다.


Valid Parentheses

문제

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

괄호들이 개수와 순서가 맞게 적혀 있는지 판별

풀이

const isValid = s => {
    while ( s.indexOf("()") !== -1 || s.indexOf("{}") !== -1 || s.indexOf("[]") !== -1 ) {
        if ( s.indexOf("()") !== -1 ) {
            s = s.replace(s[s.indexOf("()")]+s[s.indexOf("()")+1], '')
        }
        if ( s.indexOf("{}") !== -1 ) {
            s = s.replace(s[s.indexOf("{}")]+s[s.indexOf("{}")+1], '')
        }
        if ( s.indexOf("[]") !== -1 ) {
            s = s.replace(s[s.indexOf("[]")]+s[s.indexOf("[]")+1], '')
        }
    }
    return s === '' ? true: false
};

반복문으로 쌍이 없을때까지 s의 길이를 줄여나가고, 빈문자열이 된다면 true, 아니라면 false 리턴

너무 쉬운문제만 골라서 풀고 있는 것 같다.

쉬운거 아무리 풀어봐야 소용 없으니, 내일부터 medium단계에 도전해야겠다.

+ Recent posts