⭐ intro : 문제를 생각해나간 방식
챌린지 마지막 문제라 쉬운문제를 내주었구만? 땡큐~ㅋ 하다가 큰코다쳤다. 아주그냥 시멘트바닥에 질질 끌렸다. 그동안 한눈팔면서 잘 보지 않았던 '이분탐색'을 그나마 맛보게 된 매운 케이스로 인지했다. 어쩐지 이중 for문을 이용해서 풀면 금방 풀텐데 왜 정답률이 처참한지 다시금 깨달았었다. 이 문제는 이중 for문을 사용하면 '절대' 풀 수 없다.
평소처럼 주어진 input을 내 입맛에 맞게끔 쪼개고 맛있는 객체로 만드는 요리과정도 이번에는 많은 절차를 바꿔야 했다. 왜 조건의 마지막 값에 '0 0'값을 주어지게 하는지 그 의도를 그냥 넘기지 말고 '왜' 넣었을지 파악했어야 했다. 전체 index 값을 알아야 했기에 생 날것의 input을 그대로 이용해서 작업하는 방식을 썼다.
그리고 깊은복사가 아닌 얕은복사를 이용할 수 있다는 점 또한 자바스크립트 배열메서드의 소중한점인것을 다시금 깨달았다.
⭐ 풀이과정
이 문제를 풀기위해서 알아야할 오늘의 키 포인트가 있다. 바로 '다중 포인터'이다. 포인터는 간단히 말해 C언어의 개념으로 설명하면 '메모리를 참조하는 주소'이다. 자바스크립트에서는 쉽게 생각하여 해당 배열에 배정된 값을 가리키는 '표면적인' 주소인 인덱스번호를 가리킨다고 보면 된다.
이 개념을 장착한 상태에서 문제를 풀어나가 보자. 먼저 기본 셋팅대로 input값을 다져놓은 뒤, 따로 구조분해 할당을 시작하지 않고 현 상태에서, string으로 만들어놓고 양 끝 공백을 제거하고 개행문자를 제거한 기준으로 배열 재료를 썰어놓은 상태로 작업을 시작한다. 그리고 포인터 주소값을 저장해둘 idx값을 전역변수로 빼둔다. 마지막으로 전체를 무한반복하게끔 하는 while(1) 반복문을 지정해둔다.
const fs = require("fs");
let input = fs
.readFileSync(0, "utf-8")
.toString()
.trim()
.split("\n");
let idx = 0;
while (1) {}
다음으로 현재 생 날것의 input값 기준으로 최상단 상근이와 선영이가 가지고 있는 CD 갯수 N, M값을 index의 [idx] 포인터 기준으로 구조분해할당한다. 참고로 현재 input값에서 최상단 값을 따로 제거하지 않고 그대로 만들기 때문에 이후 splice를 쓰던 slice를 쓰든 기준 포인터는 1이 증가한 상태여야 한다. 따라서 idx에 후순위 연산자 ++를 넣어두거나, 아래 상근이와 선영이가 사용할 idx번호값에 1을 추가해둔다. 여기서는 원할한 가독성을 위해 전자인 후순위 연산자를 넣기로 한다. 그리고 전체 while문을 돌면서 포인터를 차례대로 아래로 이동하면서 N과 M이 각각 0 0을 만나게 되면 해당 반복문을 빠져나가도록 작업해둔다. 이후 1이 추가된 idx에 N, M값을 순서대로 넣어서 slice의 미만 기준점을 잡아 상근이와 선영이가 해당 배열 값들만 소지하도록 만들어 둔다.
let idx = 0;
while (1) {
const [N, M] = input[idx++].split(" ").map(Number);
if (N === 0 && M === 0) break;
const sangCd = input.slice(idx, idx + N).map(Number);
idx += N;
const sunCd = input.slice(idx, idx + M).map(Number);
idx += M;
}
다음으로는 이번 문제의 하이라이트, 이중포인터 이다. 막상 포인터라고 하면 어렵게 느껴질 수 있으나 자바스크립트로 구현되는 포인터는 그저 배열 index 조작이다. 단 반복문을 돌면서 처음부터 끝까지 몇번이고 순회하지 않고, 담백하게 처음부터 혹은 끝에서부터 반대점까지 한번씩만 서로 확인하는 절차이다. 상근이와 선영이의 인덱스 값을 i, j로 칭하고 중복인 경우가 발생할때마다 result에 1씩 더하도록 한다. 이후 상근이 값과 선영이의 값을 비교하면서 적은 값쪽의 인덱스값을 1씩 증가시켜서 두명이 가지고 있는 배열들을 이중포인터로 전체를 한번만 순회할 수 있도록 작업해둔다.
while (1) {
...
let i = 0;
let j = 0;
let result = 0;
while (i < N && j < M) {
if (sangCd[i] === sunCd[j]) {
result++;
i++;
j++;
} else if (sangCd[i] > sunCd[j]) {
j++;
} else if (sangCd[i] < sunCd[j]) {
i++;
}
}
console.log(result);
}이후 result에 증가된 값을 호출하면 문제 해결 완!
⭐ 제출답안
const fs = require("fs");
let input = fs
.readFileSync(0, "utf-8")
.toString()
.trim()
.split("\n");
let idx = 0;
while (1) {
const [N, M] = input[idx++].split(" ").map(Number);
if (N === 0 && M === 0) break;
const sangCd = input.slice(idx, idx + N).map(Number);
idx += N;
const sunCd = input.slice(idx, idx + M).map(Number);
idx += M;
let i = 0;
let j = 0;
let result = 0;
while (i < N && j < M) {
if (sangCd[i] === sunCd[j]) {
result++;
i++;
j++;
} else if (sangCd[i] > sunCd[j]) {
j++;
} else if (sangCd[i] < sunCd[j]) {
i++;
}
}
console.log(result);
}
⭐ 공부했던 개념들
- MDN 문서의 foreach() 루프의 break 사용 불가 문구... 앞으로 반복문을 쓸때는 콜백함수가 필요하지 않는 이상은 for of를 이용해서 인덱스와 value 값을 순회하는게 맞겠다.
- 투포인터 기법... C언어의 포인터 개념을 그대로 가지고 온 개념. 이중 for문을 실행할 경우 시간복잡도는 O(n * m)이 되기에 중간에 break로 포인트를 나누어도 상당한 수의 케이스들을 발생시키게 된다. 이를 위해 단순하게 문제에서 주어진 조건만큼만 값을 바라보도록 만든다.
