😢 알고리즘을 단계별로 풀었다면, 앞의 지식들을 이용해서 풀어주면 쉽게 가능하다. 코드가 조금 긴 것 같아서, Code Refactoring이 가능할지 고민해 봐야겠다.
😊 산술 평균: arr.reduce함수로 값을 더하고, 2로 나눈 후 Math.round()로 반올림 해주면 된다. 중앙 값: 입력받은 값은 sort()해준 후, Math.floor(arr.length / 2) 해준 것을 index로 넣어주면 된다. 최빈 값: 빈도 별로 Map 생성 - arr.push(최빈 값) - 여러개라면 sort 후(Map을 생성하면서 순서가 바뀌기 때문) index 1(2번 째니까) 아니라면 index 0(1개니까) 범위: sort된 입력값의 마지막 인덱스(arr.length-1) - 입력값의 첫 번째 인덱스(0) 해주면 된다.
😢 666, 1666, ..., 9666의 모습만 보면 안되고, 그 이상의 숫자를 예측해봐야 한다.
😊 다음과 같은 로직으로 문제를 해결했다. 1. 첫 번째 종말의 숫자는 666 이므로 665부터 숫자를 계속 증가시킨다. 2. 만약 증가시킨 숫자에 연속된 666이 포함된다? 그러면 input으로 받은 숫자를 1개만큼 줄인다. 3. input이 0이되면 증가를 중단하고 출력해준다.
😊 브루트 포스로 1부터 생성자가 있는 숫자들을 구해주고( d(n) ), N의 생성자가 여러 개라면 배열에 넣어준다. 최종적으로 생성자가 있다면 Math.min을 이용해 최솟값을 출력해주고, 없다면 0을 출력해주면 된다. 각 자릿수를 합하는 것은 위의 셀프넘버를 참고하면 된다.
참고로, 속도는 while로 자릿수를 나누는 게 더 빠르다(Full Code의 2nd Solution code 참고)
😊 JavaScript built-in method인 sort()를 사용해주면 된다. 문자를 정렬할 때는 sort()를 그냥 써줘도 되지만, 숫자를 정렬할 때는 sort((a, b) => a-b); 로 써줘야 한다. 난 for ... of를 사용하고 좋아하지만, 속도(?)와 참고하는 사람들 때문에 정석 버전으로 캡쳐했다.
😊 x, y는 현재 나의 위치이며 w, h는 직사각형의 오른쪽 위 꼭짓점, 0,0은 왼쪽 아래 꼭짓점이다.
10,3 (w, h)
6,2 (x, y)
0,0
위 표을 좌표계라고 생각해보자. 그리고 벗어날 수 있는 모든 경우의 수를 배열에 저장해보자. 좌표 0,0 기준으로 직사각형을 벗어나려면 x, y값 그 자체로 움직여야 벗어날 수 있으므로[x, y]를 배열에 우선 넣는다.(x-0, y-0) 좌표 w, h 기준으로 직사각형을 벗어나려면 w-x, h-y만큼 움직여야 벗어날 수 있다. 따라서, [w-x, h-y]를 추가적으로 배열에 넣는다.
결과적으로 [ x, y, w-x, h-y ] 총 4개의 경우의 수를 구할 수 있다(직사각형을 벗어날 수 있는 이동 값) 최종적으로 Math.min.apply(null, 배열)넣어서 최소값을 구하고 출력해주면 된다.
😊 문제의 의도는 a-1층의 1호부터 b호까지 모두 더하라는 것이 아닐 것이다. 물론 더해도 된다. 하지만 시간이 오래 걸린다.
1
6
21
56
126
1
5
15
35
70
1
4
10
20
35
1
3
6
10
15
1
2
3
4
5
예를 들기 위해, 4층, 1-5호까지 있는 아파트를 표로 작성해봤다(참고로 층은 0부터 시작한다) 어떤 패턴이 있는지 잘 살펴보면, [a행, b열]에 있는 값은 [a행, b-1열] + [a-1행, b열]의 값으로 이루어져 있다.
또한, 가장 아래 행의 각 열은 1부터 b까지 1씩 순차적으로 증가하는 값을 가지며, 왼쪽의 첫 번째 열은 항상 1 값만 갖는다.
입력으로 a=2, b=3을 받았다고 가정해보자 [2, 2] == 4, [1, 3] == 6이라는 것을 알 수 있고, 이 값을 더하면 4+6=10. 곧, [2, 3]의 값이다. 이 패턴을 가지고 코드를 작성해보면 위의 코드가 나온다.
외부 for loop에서 배열을 항상 [1]부터 시작하도록 초기화해준다. 내부 for loop에서는 가장 아래 행이면 1씩 증가하도록 if 조건문을 걸어주고, 그 외경우는 위의 [a행, b-1열] + [a-1행, b열] 패턴에 맞도록 값을 저장해준다. 그리고 마지막에 알고 싶은 층과 호수를 배열의 인덱스에 넣고 찾아주면 된다.
😢 어떻게 빠르게 해당 집단을 찾아낼 것인지, 해당 집안에서 정답을 어떻게 도출할 것인지가 핵심
😊 2번째 제출코드를 먼저 보면 이해하기 편하다.
다음 표는 지그재그 순서로 진행하는 분수를 더 보기 편하게 정리한 것이다.
1/1
1/2
2/1
3/1
2/2
1/3
1/4
2/3
3/2
4/1
5/1
4/2
3/3
2/4
1/5
...
...
...
...
...
...
분모는 짝수일 때, 오름차순으로(1 2 3 4 5...) 숫자가 진행되는 것을 알 수 있고, 분자는 짝수일 때, 내림차순으로(5 4 3 2 ...) 숫자가 진행되는 것을 알 수 있다. 홀수는 그 반대다.
패턴을 파악했으니, 어떻게 답을 찾아낼 지 생각해보자.
먼저, 최대로 입력받을 수 있는 수의 크기는 10,000,000이므로 배열이나 테이블로 만드는 건 시간 초과가 날 것이다. 따라서, 찾고자하는 X번을 포함하고 있는 그룹을 찾고, 그 그룹 안에서 X번째 분모/분자 값을 찾아내야 한다.
1/1부터 시작한다고 생각할 때, 해당 그룹의 분수 개수는 1부터 1씩 증가한다. 그룹 개수가 증가할 때마다 입력 받은 X에서 그룹을 빼주면 해당 그룹에 도달했을 때, X는 0 또는 음수가 된다. 위 과정을 while문에서 진행해주면 된다.
여기서 중요한 것은 groupCounter가 곧 해당 그룹의 분수 개수라는 것이다. 이 것을 기억하고 다음 단계로 넘어가보자.
이제 if (group % 2 === 0)을 이용해서 짝수일때, 분모 출력을 groupCounter + X 로 해주면 해당 그룹의 끝 기준으로 자신의 순번을 찾는다.(12345 처럼 오름차순 기준이기 때문) 그리고 분자는 1 + (-X) 를 해주면 역시 그룹의 끝 기준으로 자신의 순번을 찾는다.( 54321처럼 내림차순이기 때문)
예를 들어 11번째 분수를 찾아보자.
while(X > 0){} 코드를 통해 groupCounter는 5, X는 -4라는 것을 알아낼 수 있다. 그룹은 5번째이므로 홀수이기 때문에, 분모는 내림차순, 분자는 오름차순이다. 분모 그룹은 54321 분자 그룹은 12345 이며 분모는 1+ -(-4) = 5이므로, 5번째 그룹의 1번째 수이며, 분자는 5 + (-4) = 1이므로, 역시 5번째 그룹의 1번째 수다.
