내용이 안 보인다면 쿠키/캐시를 지우고 새로고침 하세요!
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

게시글

강좌24 - Algorithm - 4달 전 등록

프로그래머스 문제 풀이 Level 1

11번~20번
조회수:
0
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ
이 블로그는 광고 클릭 수익으로 운영됩니다!
괜찮으시다면 광고 차단을 풀어주세요 ㅠㅠ

안녕하세요. 이번 시간에는 11번부터 20번까지 풀어보겠습니다. 모든 문제는 제가 직접 푼 풀이이며, 더 나은 풀이가 있다면 알려주세요~ 못 푼 문제는 끙끙대며 풀어볼테니 스포 금지!

Level 1 11번~20번

소수 찾기 

1~n 사이의 소수의 개수를 반환해야 합니다.

소수를 찾으려면 제가 알기로는 반복문 돌면서 나누는 수밖에 없는 것으로 알고 있습니다. 단, 캐싱을 좀 해두면 자원 절약은 되겠죠.

function solution(n) {
  const primes = [];
  for (let j = 2; j <= n; j++) {
    let isPrime = true;
    const sqrt = Math.sqrt(j);
    for (let i = 0; primes[i] <= sqrt; i++) {
      if (j % primes[i] === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) {
      primes.push(j);
    };
  }
  return primes.length;
}

일단 가장 간단하게 떠오르는 반복문 사용해서 푸는 방법입니다. 근데 반복문을 사용하고 싶지 않다면요? 저처럼 for을 사용하지 않는 사람은 어떻게 해야 할까요?? 바로 재귀를 사용합니다.

function solution(n, start = 2, primes = [], count = 0) {
    if (start > n) return count;
    const sqrt = Math.sqrt(start);
    const isPrime = primes.every(v => start % v);
    if (isPrime) primes.push(start);
    return solution(n, start + 1, primes, count + (isPrime ? 1 : 0));
}

현재 Maximum call stack size exceeded 에러가 뜨네요. 꼬리재귀가 안 돼서 그런 것 같습니다. ㅠㅠ 그럴 때 쓰는 방법이 있긴 한데(setTimeout같은 것 사용) 효율성 측면에서 좋은 방법은 아닙니다.

근데 재귀가 항상 좋은 것만은 아닙니다. 재귀는 함수를 반복적으로 호출해서 컴퓨터에 더 무리를 줄 수 있습니다. 알고리즘 문제를 풀 때 반복문이 재귀보다 효율성 점수를 높게 받을 가능성이 큽니다.

위의 코드보다 더 효율적인 방법이 있다는 조언을 들었습니다. 에라토스테네스의 체를 사용하는 것인데요. 위 코드는 하나의 숫자가 소수인지 아닌지 판단할 때 더 효율적이고, 아래 코드는 여러 개의 숫자 중에 소수를 걸러낼 때 더 효과적이라고 하네요.

function solution(n) {
    let range = Array(n - 1).fill().map((v, i) => i + 2);
    for (let i = 0; i < range.length; i++) {
        range = range.filter(v => v === range[i] || v % range[i]);
    }
    return range.length;
}

근데 코드를 돌려보면 시간 초과가 떠서 이 부분 개선 조언을 받습니다. 혹시나 filter 대신에 다시 반복문으로 해야하는 것일까요. ㅠㅠ

수박수박수박수박수 

3이면 수박수, 4면 수박수박, 5면 수박수박수를 리턴하면 됩니다.

수박을 원하는만큼 반복시켜서 개수만큼 자르면 될 것 같습니다.

function solution(n) {
  return '수박'.repeat(n).substr(0, n);
}

repeat 메서드로 문자열을 반복할 수 있습니다. 코드 길이는 늘어나지만 repeat(n) 대신 repeat(Math.ceil(n / 2))하면 더 효율적일 것 같기도 하네요.

문자열을 정수로 바꾸기 

function solution(s) {
  return parseInt(s);
}

더 이상 설명이 필요한지...? 근데 또다른 팁으로 문자열을 숫자로 바꾸는 방법 몇 개를 더 설명드리겠습니다. 단, 자바스크립트 원리를 잘 모르면 가독성을 해치기 때문에 저는 잘 쓰지 않습니다. +s, s * 1, s / 1, Number(s) 등이 있습니다.

시저 암호 

AB는 1만큼 밀면 BC가 되고, AB를 3만큼 밀면 DE가 됩니다. z는 1만큼 밀면 a가 됩니다. 공백은 그대로 공백이고요.

즉 문자를 다른 문자로 치환하는 건데요. 이렇게 1대1 변환을 하는 문제는 map으로 다 커버 가능합니다. map 안에서 공백인 경우, 소문자인 경우, 대문자인 경우를 나눠서 하면 되겠습니다. 또는 대소문자 상관 없이 Z에서 다시 A로 돌아오는 것과 같은 경우만 찾아도 되겠고요. 저는 다시 돌아오는 것들을 찾는 식으로 했습니다.

function solution(s, n) {
  return s.split('').map((l) => {
    return l === ' '
      ? l
      : l.charCodeAt() + n > 122 || (l.charCodeAt() <= 90 && l.charCodeAt() + n > 90)
        ? String.fromCharCode((l.charCodeAt() + n) - 26)
        : String.fromCharCode(l.charCodeAt() + n);
  }).join('');
}

일단 l이 공백이면 그대로 공백을 리턴하고요. A의 charCodeAt이 65, Z가 90, a가 97, z가 122는 것을 이용해서, 혹시나 Z에서 A로 넘어가거나, z에서 a로 넘어가는 게 있지는 않은지 검사합니다. 넘어가는 게 있다면 -26을 해주고(알파벳이 26개입니다) 없다면 그냥 n을 더해서 리턴합니다. String.fromCharCode가 charCodeAt의 반대 메서드입니다.

약수의 합  

약수의 합을 리턴합니다. 12의 약수는 1,2,3,4,6,12라서 모두 더하면 28입니다.

약수를 구할 때 1부터 n 까지 나눠보고 나누어 떨어지면 약수라고 여기면 되겠습니다.

function solution(n) {
  return Array(n).fill().map((v, i) => i + 1).reduce((a, c) => n % c ? a : a + c, 0)
}

후후... 한 줄로 끝낼 수 있습니다. Array fill map 조합은 [1,2,3,...,n]까지 숫자를 만드는 메서드입니다. 보통 range라는 함수로 다른 라이브러리에 많이 들어 있습니다. n % c ? a : a + c이 부분은 나눠지면 나눈 값을 더하고, 안 나눠지면 이전 값을 그대로 사용한다는 의미입니다.

사실 Array(Math.floor(n/2))로 배열을 만들고 마지막에 + n을 해주는 게 더 효율적일 것 같습니다.

이상한 문자 만들기 

단어의 짝수번째 문자는 대문자로, 홀수번째 문자는 소문자로 바꿉니다. try hello world는 TrY HeLlO WoRlD가 되네요.

대문자로는 toUpperCase() 소문자로는 toLowerCase()를 씁니다. 이것도 단어 하나씩을 치환하는 거니까 map이 어울립니다.

function solution(s) {
  return s.split(' ').map(w => (
    w.split('').map((v, i) => (i % 2 ? v.toLowerCase() : v.toUpperCase())).join('')
  )).join(' ');
}

split map join 삼단콤보(split-apply-combine 기법)로 쉽게 해결할 수 있습니다.

자릿수 더하기 

123이면 1+2+3을 해서 6을 리턴하면 됩니다.

function solution(n) {
  return String(n).split('').reduce((acc, cur) => acc + +cur, 0);
}

사람처럼 생각해서 자릿수를 다 분리한 후 더해나가면 됩니다. +cur로 문자열을 숫자로 바꾸는 기능을 써보았습니다. 근데 좀 지저분하고 가독성도 떨어지죠? 실무에서는 저런 건 그냥 안 쓰시는 게 좋습니다.

자연수 뒤집어 배열로 만들기

12345를 뒤집어 [5,4,3,2,1]로 만들면 됩니다. 

function solution(n) {
  return String(n).split('').reverse().map(v => +v);
}

배열로 만드는 건 split, 뒤집는 건 reverse, 문자열을 숫자로 바꾸는 건 map을 쓰면 됩니다.

정수 내림차순으로 배치하기

118372면 내림차순으로 873211을 리턴하면 됩니다.

이것도 숫자를 한 자리씩 쪼개서 내림차순 정렬을 하고 다시 합치면 되겠죠. 

function solution(n) {
  return +String(n).split('').sort((p, c) => c - p).join('');
}

앞에 +는 나머지 부분의 결과물로 나오는 문자열을 숫자로 바꾸는 것입니다. 제 입으로 쓰지 말랬는데 자꾸 써서 죄송합니다. 묘하게 중독성이 있네요...

정수 제곱근 판별

n이 정수 x의 제곱이라면 x+1의 제곱을 리턴하고, 아니라면 -1을 리턴합니다.

function solution(n) {
  return Math.sqrt(n) === parseInt(Math.sqrt(n)) ? (Math.sqrt(n) + 1) ** 2 : -1
}

곧이곧대로 만들면 되겠습니다. 삼항연산자로 if문을 짧게 줄일 수 있습니다. Math.pow 대신에 ** 연산자 쓸 수 있는 거 아시죠? 효율적인 코드를 만들려면 Math.sqrt(n)처럼 반복되는 것은 캐싱하시는 게 좋습니다.

이상으로 20번까지 풀어보았습니다. 바로 30번까지 달려봅시다!

투표로 게시글에 관해 피드백을 해주시면 많은 도움이 됩니다. 오류가 있다면 어떤 부분에 오류가 있는지도 알려주세요! 잘못된 정보가 퍼져나가지 않도록 도와주세요.
Copyright © 2016- 무단 전재 및 재배포 금지

댓글

1개의 댓글이 있습니다.
3달 전
'수박수박수' 문제에서 repeat(Math.ceil(n / 2)) 로 하면 왜 효율성이 올라가는지 궁금합니다. repeat()메서드가 연산량이 줄어서인가요?
3달 전
사실 Math.ceil의 연산량이 클지 repeat에서 n -> n / 2의 연산량이 클지를 잘 모르겠습니다.
3달 전
성능 체크해보니 둘이 거의 차이 없네요.
3달 전
고맙습니다!!