[구름/JavaScript] 알고리즘 먼데이 챌린지 1주차

챌린지 소개

구름LEVEL

 

문제 및 해설

알고리즘 {먼데이} 챌린지 해설 - 구름EDU

 

10월 3일부터 12월 4일까지 구름LEVEL에서 알고리즘 먼데이 챌린지를 진행하고 있습니다. 8주 동안 매주 월요일마다 새로운 문제가 출제되는데 문제를 풀거나 이전 주의 문제를 복습하면 스탬프를 모을 수 있습니다. 스탬프 개수에 따라 다양한 상품도 받을 수 있어서 알고리즘 공부에 대한 동기 부여도 되고 재밌게 도전해볼 수 있을 것 같아요!

 

개별 문제는 https://level.goorm.io/에서 문제명을 검색하면 풀어볼 수 있습니다.

 

 

---

 

 

챌린지 1주차(10월 3일 - 9일) 복습 후 풀이를 공유합니다. 더 자세한 풀이는 위 해설을 참고하시길 바랍니다.

백준처럼 readline으로 입력을 받아서 처리합니다. 문제 해결에 필요한 로직은 solution 함수로 분리했습니다.

 

문제 1. 경로의 개수

다리의 개수 배열(bridges)을 인자로 받습니다. 곱의 법칙에 따라 주어진 다리 개수를 모두 곱하는데, JavaScript의 경우 Number로 표현 가능한 범위가 -(2^53-1) ~ 2^53-1이므로 10개의 수가 모두 100인 경우 정확히 표현할 수 없습니다. 대신 BigInt를 이용하면 더 큰 범위까지 안정적으로 처리할 수 있습니다.

 

for문으로 bridges의 각 원소를 BigInt형으로 변환하여 answer에 누적해서 곱합니다. 또는 고차 함수인 reduce()로 배열 원소를 모두 곱합니다. 답을 리턴할 때는 toString()으로 BigInt 객체를 문자열로 변환합니다.

 

 

문제 2. 동명이인

주어진 문자열 name을 포함하는 배열 arr 원소의 개수를 구하는 문제입니다. 변수 name을 그대로 이용해서 new RegExp() 생성자로 정규 표현식을 만듭니다. test() 메서드(true/false 반환)로 배열의 각 원소가 name을 포함하면 answer를 증가시킵니다. 

 

 

문제 3. 최장 맨해튼 거리

주의! 채점 시 테스트케이스 3~10번에 에러가 발생할 수 있는데, 문자열 끝에 공백이 포함되어 있다고 합니다(Q&A 참고). trim()(양쪽 끝)또는 trimEnd()(오른쪽 끝)로 공백을 제거합니다.

 

주어진 거리 숫자 배열을 오름차순 정렬한 후 (가장 큰 값 - 가장 작은 값) + (두 번째로 큰 값 - 두 번째로 작은 값)을 계산하면 가장 큰 맨해튼 거리를 구할 수 있습니다. 이외에도 완전 탐색으로 접근할 수 있습니다.

 

정수 최댓값인 Number.MIN_SAFE_INTEGER로 답(max)을 초기화한 후 이중 for문에서 최댓값을 업데이트하는 방식입니다. i(0부터 4)와 j(i+1부터 4) 두 값을 선택한 후 |i - j| + |i와 j를 제외한 두 값의 차|를 구합니다(절댓값 | |은 Math.abs()로 계산). 구한 값과 max 간 비교해서 최댓값을 업데이트합니다. 

 

 

문제 4. 소수 찾기

대표적인 소수 판별 문제입니다. for문으로 1부터 n까지 i를 증가시키면서 i가 소수이면 i번째 수를 answer에 더합니다. isPrime() 함수에서 소수인지 확인하는데, 2 미만이거나 2~i 번째 숫자의 제곱근 중 i번째 숫자를 나눴을 때 나눠떨어지는 수가 있다면 false를 리턴합니다.

 

문제 해설에서는 에라토스테네스의 체 방식도 소개하고 있으니 참고하면 좋을 것 같습니다.

 

 

 

 

궁금한 점이나 잘못된 점은 댓글로 남겨주시면 감사하겠습니다 :)