감공사

😢 11650문제를 풀었다면, 보너스 문제

😊 11650문제에서 정렬의 주체만 변경해주면 된다.
y증가를 기준으로 정렬해주는데, y가 같으면 x증가 순으로 정렬해주면 된다.

😢 시간 초과 때문에 고생한 문제

😊 이 문제 덕분에 sort()의 새로운 방법을 알게 되었다.

시간 초과를 해결하기 위해 가장 중요한 2가지

1. sort() 1번만 사용하기
처음에는 단순하게 x기준 정렬 후 y기준 정렬했기 때문에 sort()가 2번 사용되었다.
하지만, sort( (a, b) => if( a[0] !== b[0] ) { return a[0] - b[0] } return a[1] - b[1] ); 덕분에 sort() 1번만 진행할 수 있었다.

2. console.log() 1번만 사용하기
또한, 시간 초과에서 중요했던 다른 하나는 console.log()출력을 줄이는 것이었다.
forEach를 이용해, results변수에 모든 출력값을 저장한 후 console.log() 단 한 번 출력해주었더니 시간 초과를 해결할 수 있었다.

😢 시간 초과 문제가 걸릴 줄 알았지만, 간단했던 문제

😊
1. sort() 내림차순 정렬
2. sort() 오름차순 정렬 + reverse()
3. Selection Sort(선택 정렬)
4. Bubble Sort(버블 정렬)
5. Merge Sort(병합 정렬)

위 5가지 방법으로 모두 풀어보았다.
모두 해결 가능했지만, 당연히 시간 차이가 있다.
버블 > 선택 > 병합 === sort() === sort() + reverse() 순으로 시간이 걸렸다.
(버블이 가장 오래걸렸다는 뜻)

😢 알고리즘을 단계별로 풀었다면, 앞의 지식들을 이용해서 풀어주면 쉽게 가능하다.
코드가 조금 긴 것 같아서, 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이되면 증가를 중단하고 출력해준다.

Code

😢 조건문을 이용해 풀려다가 시간을 조금 보낸 문제

😊 일단, 다른 풀이를 참고하여 단순하게 풀어봤다.
맨 왼쪽 위칸이 'W'일 때 또는 'B'일 때, 8*8체스판을 미리 작성해두었다.
그리고 입력받은 체스판 크기만큼 8*8씩 잘라서 반복적으로 비교하여 모든 경우의 수를 저장했다.
최종적으로 Math.min()을 이용해 최솟값을 출력해주었다.

이런 저런 방법으로 다시 풀어봐야겠다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

Code

😢 '백준 4673번: 셀프넘버'를 풀었다면 쉽게 풀 수 있는 문제

😊 브루트 포스로 1부터 생성자가 있는 숫자들을 구해주고( d(n) ), N의 생성자가 여러 개라면 배열에 넣어준다.
최종적으로 생성자가 있다면 Math.min을 이용해 최솟값을 출력해주고, 없다면 0을 출력해주면 된다.
각 자릿수를 합하는 것은 위의 셀프넘버를 참고하면 된다.

참고로, 속도는 while로 자릿수를 나누는 게 더 빠르다(Full Code의 2nd Solution code 참고)

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

Code

😢 배열에 건물 크기만큼 방 번호를 저장하고 인덱스는 찾아내는 반복문도 가능했지만, 패턴과 집단을 찾는게 핵심

😊 Solution 1)

일단, 입력 받은 W는 이용하지 않아도 되는 방법으로 풀었다.
N(번째 방문자)을 H(층 높이)로 계속 빼주고, N이 H보다 작거나 같을 때 반복을 끝내보자.
그러면 N번째 방문자의 호수와 층수를 동시에 구할 수 있다.

예를 들어 N=10, H=6이라고 할 때, N = N - H;를 반복해주면  한 번만 빼줘도 10 - 6 = 4가 된다.
첫 호수 집단의 6층은 꽉 찼고, 다음 호수 집단의 4층이라는 것을 알 수 있다. (6+4=10)
동시에 roomCnt++를 진행해주면 엘리베이터에서 얼마나 떨어져 있는 호수 집단인지 알 수 있다.
위의 뺄셈은 1번 진행되며, 호수 집단은 1부터 시작한다고 선언했을 때, roomCnt++;도 역시 1번 진행되므로
2값을 얻을 수 있고, 2는 엘리베이터 기준 2번째 호수 집단이라는 것을 알 수 있다.

결과적으로 6층 각 층 객실12개 기준 10번째 손님은 402호라는 정답을 도출해낼 수 있다.

Solution 2)

N/H를 해주면 몇 번째 호수 집단인지 알아낼 수 있으며,
N%H를 해주면 몇 층인지 알아낼 수 있다.

예를 들어, N=72, H=30이라고 할 때,

N/H=2.4
1번째, 2번째도 아니고 2번째를 넘어가는 집단이라는 뜻인데 즉, 그말은 3번째 호수 집단이라는 것이다.
즉, 정수가 나오지 않는 다면 Math.ceil()을 이용해 올림을 해주면 된다.

N%H=12
즉, 30층을 2번 지난 후 12번째 층이라는 뜻이다.

층이 증가되는 패턴 그리고 호수가 증가되는 패턴을 파악하면 이렇게 N과 H만으로도 문제를 해결할 수 있다.

Solution 3)

방 배정 우선순위로 배열에 방 번호를 저장하면 된다.
중첩 for loop을 사용하며, 외부 for loop에서는 호수를 내부 for loop에서는 층수를 뽑아내면 된다.
배열에 모든 경우의 수를 저장한 후 N(or N-1)번째 배열을 출력해주면 된다.

추가적으로, 정확한 정답을 위해서 호수가 10이하면 호수 앞에 '0'을 꼭 붙여줘야 한다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

Code

😢 이해하고 식을 만들어 내는 것이 조금 힘들었다. 미끄러지는 부분을 정확히 이해해야 한다.

😊 높이 V를 A-B로 나눠주는 방법이 가장 효율적이다.
하지만, 정상에 도착하면 미끄러지지 않기 때문에 B가 결국 한 번 더 계산식에 들어가는 셈이다.
따라서, 높이에V에 B를 빼주면 위 문제를 해결할 수 있다.
딱 떨어지지 않는 수가 나올 때는, 하루가 더 필요하다는 뜻이기 때문에 Math.ceil로 올림을 해주면 같은 효과를 볼 수 있다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)

Code

😢 어떻게 빠르게 해당 집단을 찾아낼 것인지, 해당 집안에서 정답을 어떻게 도출할 것인지가 핵심

😊 2번째 제출코드를 먼저 보면 이해하기 편하다.

다음 표는 지그재그 순서로 진행하는 분수를 더 보기 편하게 정리한 것이다.

분모는 짝수일 때, 오름차순으로(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번째 수다.

Full Code (https://github.com/DasolPark/Dasol_JS_Algorithm/tree/master/Baekjoon)