[Level1] 4. 18 ~ 20

in 코딩테스트 on 프로그래머스




하루 세문제씩 꾸준히 풀기!


18. 없는 숫자 더하기

프로그래머스 

function solution(numbers) {
  let sum = 0
  for (let i = 0; i<numbers.length; i++){
    sum += numbers[i]
  }

  return 45-sum;
}


맨날 어려운 문제 풀다가 1단계에서 정말 1단계스러운 문제를 오랜만에 만났다.
예전이었으면 0~9까지 하나하나 찾아서 없는 수를 알아냈겠지만 그동안의 경험으로
정석보다 더 빠른 풀이를 찾는 법을 알아낼 수 있게 되었다.
내가 접근한 방식은 0~9를 다 더한 수에서 numbers 빼기!

바로 정답이었고, 사람들의 풀이도 대부분 이 방식이었다.

best 풀이

function solution(numbers) {
    return 45 - numbers.reduce((cur, acc) => cur + acc, 0);
}

배열에서 누적합을 구할 때는 reduce를 많이 쓴다는 것 잊지 말기!



19. 약수의 개수와 덧셈

programmers 

function solution(left, right) {
  let arr = []
  let temp = []
  let answer = 0
  while(left <= right){
    arr = [];
    temp = []
    for (let i = 0; i * i <= left; i++) {
      if (left % i === 0) arr.push(i);
    }
    for (let i = 0; i < arr.length; i++) {
      temp.push(parseInt(left / arr[i]));
    }
    let set = new Set(arr.concat(temp))
    if (set.size % 2) {
      answer -= left
    } else {
      answer += left
    }
    left++
  }
  return answer
}


풀긴 풀었는데 테스트케이스에서 어떤거는 5ms 가 나온정도로 시간복잡도가 최악인 경우가 있었다.ㅠ
16의 경우 4,4 로 나와서 중복 배제를 위해 어쩔 수 없이 set을 썼는데 여기서 시간복잡도가 크게 늘어나지 않았나 싶다.
약수의 갯수를 구하는 과정을 처음에는 정석으로 target % i === 0 인 것을 찾다가,
시간복잡도가 장난이 아니게 나올 것 같아서 검색한 결과 target의 제곱근 안에서만 구하고,
그 구한 수들로 target을 나눴을 때 몫까지 합하면 모든 약수라는 것을 배우고 다시 짰다!
확실히 코테는 문제를 많이 접하면 접할 수록 효율적인 접근 방법을 많이 배울 수 있는 것 같다.

best 풀이

function solution(left, right) {
    var answer = 0;
    for (let i = left; i <= right; i++) {
        if (Number.isInteger(Math.sqrt(i))) {
            answer -= i;
        } else {
            answer += i;
        }
    }
    return answer;
}


우와 정말 간단한 코드…!
제곱근이 정수면 약수의 갯수가 홀수라는 수학적 원리를 이용한 풀이법이다.
이건 정말 일반인이 알아낼 수 있는 공식인걸까?
나는 이걸 하려고 set도 쓰고 안간힘을 썼는데….
Math.sqrt() : 숫자의 제곱근 반환 기억하기

정석 풀이법

function solution(left, right) {
  let answer = 0;

  for (let i = left; i <= right; i++) {
    let count = 0;
    for (let j = 1; j <= i; j++) {
      if (i % j === 0) count++;
    }
    if (count % 2) answer -= i;
    else answer += i;
  }

  return answer;
}


어찌보면 이게 내 코드보다 더 단순한 것 같다…
비교 대상 수가 엄청 큰 수가 아니라면 이게 더 빠를 수도 있을 것 같다. (가시적으로는 이게 훨씬 좋아보이네..쩝)



20. 모의고사

programmers 

function solution(answers) {
  let num1 = [1, 2, 3, 4, 5];
  let num2 = [2, 1, 2, 3, 2, 4, 2, 5];
  let num3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5];

  let length = [5, 8, 10];

  let cnt = new Array(3).fill(0);

  for (let i = 0; i < answers.length; i++) {
    if (num1[i % length[0]] === answers[i]) {
      cnt[0]++;
    }
    if (num2[i % length[1]] === answers[i]) {
      cnt[1]++;
    }
    if (num3[i % length[2]] === answers[i]) {
      cnt[2]++;
    }
  }

  let max = Math.max(...cnt);
  let arr = [];
  cnt.forEach((item, index) => {
    if (item === max) {arr.push(index+1);}
  });
  return arr.sort((x, y) => x - y)
}


정답은 맞았는데 뭔가 별로다..
저번부터 조건에 만족하는 수를 배열에서 찾아 그것의 인덱스로 반환하는게 나한테 너무 힘들었다.ㅠㅠ
forEach를 쓰면 된다는 것을 오늘에서야 깨달았다…ㅋㅋㅋ 그동안 왜몰랐지? 바본가..?
그래도 잘 활용해서 풀었으니 된거다! 더 발전했으면 됐어!
다른 풀이를 보니까 접근방식이 모두 동일해서 엄청 못한 것 같지는 않으니 합격!

best 풀이

function solution(answers) {
    var answer = [];
    var a1 = [1, 2, 3, 4, 5];
    var a2 = [2, 1, 2, 3, 2, 4, 2, 5]
    var a3 = [ 3, 3, 1, 1, 2, 2, 4, 4, 5, 5];

    var a1c = answers.filter((a,i)=> a === a1[i%a1.length]).length;
    var a2c = answers.filter((a,i)=> a === a2[i%a2.length]).length;
    var a3c = answers.filter((a,i)=> a === a3[i%a3.length]).length;
    var max = Math.max(a1c,a2c,a3c);

    if (a1c === max) {answer.push(1)};
    if (a2c === max) {answer.push(2)};
    if (a3c === max) {answer.push(3)};


    return answer;
}


정답을 찾는 접근법은 나랑 똑같은데 훨씬 간결한 코드와 적합한 메소드를 사용해서 코드가 짧아진 것 같다.



오늘은 조금 쉬고 싶어서 자료구조가 들어간 문제를 풀지 않았는데 내가 약한건 자료구조가 녹여진 문제라는 걸 안다…내일부터는 피하지말고 부딪치자!!👑👑