모의고사
두번 반복시키지말고 한번만해주지 끊어보기 불편하게..
뭔가 하드코딩을 유도하는?... 이상한 문제같다. 아니면 좋은 문제인데 내가 보는 눈이 없거나.
나의 풀이
아쉽게도 안된다.
function sol0(answers) {
const point = [0,0,0]
const length = answers.length
const person1 = [1, 2, 3, 4, 5]
const person2 = [2, 1, 2, 3, 2, 4, 2, 5]
const person3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
const picks = [person1, person2, person3]
const lengths = [person1.length,person2.length,person3.length]
let i = 0
let n = 0
while (n < 3) {
i = 0
while ( i < length){
if ( answers[i] === picks[n][i%lengths[n]] ) {
point[n]++
}
i++
}
n++
}
const bestPicker = []
let max = Math.max(...point)
i=0
while (i < point.length) {
if ( point[i] === max){
bestPicker.push(i+1)
}
i++
}
return bestPicker;
}처음에는 const bestPicker = [1] 로 넣고 i=1부터 루프를 돌앗는데 초기화에서 문제가 생겨서 방법을 바꾸었다.
다른 사람의 풀이
function sol1(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;
}나랑 같은 방법이지만 루프문을 쓰지 않은 차이점이 있따.
속도 비교
시간복잡도는 이다.
반복 횟수 100회 증가
별다른 특이사항은 없다.
입력 길이 10배 증가
입력 길이 100배 증가
갯수가 작고, 정해져있다면 루프문을 돌리지않는 것이 효율적인건가?
N개의 최소공배수
나의 풀이
function solution(arr) {
let answer = 1
let commonMultiples = []
let i = arr[arr.length-1]
while ( i > 0 ) {
let j = 0
while (j < arr.length) {
if (arr[j]%i === 0) {
commonMultiples.push(arr[j]/i)
}
j++
}
i--
}
console.log(commonMultiples)
commonMultiples = [...new Set(commonMultiples)]
console.log(commonMultiples)
i = 0
while ( i < commonMultiples.length ) {
answer *= commonMultiples[i]
i++
}
return answer;
}
뭔가 너무 잘 풀린다 싶었다. 오직 소수만이어야한다.
function solution(arr) {
let answer = 1
let nums = []
let commonMultiples = []
const length = 15
let i = 0
let j = 0
while (i < length) {
nums.push(i+1)
i++
}
i = 2
const I = parseInt(Math.sqrt(length))
while (i <= I) {
j = 2;
while (i * j <= length) {
const index = nums.indexOf(i * j);
if (index !== -1) {
nums.splice(index, 1);
}
j++;
}
i++;
}
i = arr.length -1
console.log(nums)
while ( i >= 0) {
j = 0
while (j < nums.length) {
if (arr[i]%nums[j] === 0) {
console.log(nums[j])
commonMultiples.push(nums[j])
}
j++
}
i--
}
console.log(commonMultiples)
commonMultiples = [...new Set(commonMultiples)]
console.log(commonMultiples)
i = 0
while ( i < commonMultiples.length ) {
answer *= commonMultiples[i]
i++
}
return answer;
}
소수만인것도 조건이 아닌것같다.
첫 코드의 결과값인 112896 에서 2를 제외한 arr의 값들을 나누니 정답인 168이 나왔다
그렇다... 소수를 제외한 숫자들의 약수에서는 자기자신을 빼야했던것이다.
function solution(arr) {
let answer = 1
let commonMultiples = []
const length = 100
const nums = []
let i = 0
let j = 0
while (i < length) {
nums.push(i+1)
i++
}
i = 2
const I = parseInt(Math.sqrt(length))
while (i <= I) {
j = 2;
while (i * j <= length) {
const index = nums.indexOf(i * j);
if (index !== -1) {
nums.splice(index, 1);
}
j++;
}
i++;
}
i = arr.length -1
i = arr[arr.length-1]
while ( i > 0 ) {
let j = 0
while (j < arr.length) {
if (arr[j]%i === 0) {
commonMultiples.push(arr[j]/i)
}
j++
}
i--
}
commonMultiples = [...new Set(commonMultiples)]
console.log(nums)
arr = arr.filter((item) => !nums.includes(item))
commonMultiples = commonMultiples.filter((item) => !arr.includes(item))
i = 0
while ( i < commonMultiples.length ) {
answer *= commonMultiples[i]
i++
}
return answer;
}100까지의 소수를 구하고 해도 안된다.
이쯤되면 그냥 근본적으로 뭔가 잘못된거다 다시 엎자 ㅠㅠ
function sol0(arr) {
let answer = arr[0]
const length = arr.length
// 호제법
// 두 정수 a와 b를 나누고(크기는 상관 없음), 그 나머지와 b의 나머지의...
// 나누어 떨어질때까지 (a/b =0) 반복하면 최소 공약수를 구할 수 있다는 것이다.
// 두 수의 곱 = 두 수의 최대공약수 * 최소공배수
let i = 1
let j = 0
while (i < length) {
let a = answer
let b = arr[i]
while (b !==0 ) {
let r = a%b
a = b
b = r
}
answer = answer * arr[i] / a
i++
}
return answer;
}대체 ab = a,b의 최대 공약수 최소 공배수 인지는 아직도 모르겠지만 그렇다니까 그런줄만 알고 있다.
다른 사람의 풀이
function sol1(num) {
return num.reduce((a,b) => a*b / gcd(a,b))
}
function gcd(a, b) {
return a % b ? gcd(b, a%b) : b
}원리 자체는 나랑 같은데 훨씬 깔끔하게 구현되었다.
a%b가 나머지를 남길 경우 자신을 재귀호출한다.
function sol21(num) {
var answer = 0;
function gcd(a, b) {
if ( ! b) {
return a;
}
return gcd(b, a % b);
}
function lcm(a,b){
return (a*b/gcd(a,b));
}
answer = num.reduce(function(a,b) {
var min = Math.min(a,b);
var max = Math.max(a,b);
return lcm(min,max);
})
return answer;
}크기를 비교할 필요가 없으니 이부분을 제거해보자
function sol22(num) {
function gcd(a, b) {
if (!b) {
return a;
}
return gcd(b, a % b);
}
function lcm(a, b) {
return (a * b) / gcd(a, b);
}
const answer = num.reduce((acc, cur) => lcm(acc, cur));
return answer;
}속도 비교
시간 복잡도
sol0 :
sol1, sol2 :
반복 횟수 증가
특이한 점은 없어보인다.
입력길이 100배 증가
시간복잡도상으로는 sol0이 가장 느려야하는데 그렇지는 않다.
그리고 sol21에 있던 무의미한 더 큰 수를 구하는 과정을 제거한 sol22는 충분히 좋은 성과를 보이는 것같다.
입력값 크기 증가
배열의 길이를 늘리는것이 아니라 배열의 요소들의 값을 10배 100배 했는데 딱히 차이가 없다.
공부하며 느낀 점
- 반복을 할 대상의 크기가 작고, 일정하다면 루프문을 짜지 않는것이 더 빠를 수 있다.
하지만 유지보수를 생각하면 루프로 짜는게 맞을지도? - 수학을 얼마나 잘 아느냐에 따라서 코드를 짜는 효율이 확 바뀐다.
- 또 다시 느꼈지만 시간 복잡도는 절대적이지않다
참조한 페이지
node 개발자