코테 문제들을 풀어보니 중요한 것은 문제에 어떻게 접근해야하는 지가 가장 중요한 것 같다.
예를 들면 ~중에 ~ 조건 값을 찾기, ~와 ~을 비교해서 ~ 조건에 맞는 값을 출력하기 등 풀이는 다양하지만 유형은 정해져있다.
문제는 원하는 접근법을 어떻게 코드로 작성하는지 알아야한다.
예시 문제
지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자 판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요.
격자의 가장자리는 0으로 초기화 되었다고 가정한다.
만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다.
▣ 입력설명
첫 줄에 자연수 N이 주어진다.(1<=N<=50)
두 번째 줄부터 N줄에 걸쳐 각 줄에 N개의 자연수가 주어진다. 각 자연수는 100을 넘지 않는다.
▣ 출력설명
봉우리의 개수를 출력하세요.
이 문제는 봉우리의 수를 반환하는 함수를 만드는 것이다.
그럼 봉우리의 조건을 정리해야한다.
요약하면 봉우리 -> 상하좌우 보다 큰 수-> 상: 앞 배열의 같은 index의 요소, 하: 뒤 배열의 같은 index의 요소, 좌: 같은 배열의 앞 index 요소, 우: 같은 배열의 뒤 index 요소
이 조건에 맞는 요소들을 비교해야 봉우리가 나온다는 것인데 어떻게 접근해야할까.
이중 for문 돌려서 각각의 index 값을 빼거나 더해서 앞뒤 배열이나 요소를 가져와서 찾는 방법이 떠오른다. 일단 해보자.
function solution(arr) {
let answer = 0;
const n = arr.length;
const outline = Array.from({ length: n }, () => 0);
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
const upperArr = arr[i - 1] || outline;
const underArr = arr[i + 1] || outline;
const upper = upperArr[j] || 0;
const under = underArr[j] || 0;
const left = arr[i][j - 1] || 0;
const right = arr[i][j + 1] || 0;
const currentVal = arr[i][j];
const max = Math.max(currentVal, upper, under, left, right);
if (max === currentVal) answer++;
}
}
return answer;
}
const arr = [
[5, 3, 7, 2, 3],
[3, 7, 1, 6, 1],
[7, 2, 5, 3, 4],
[4, 3, 6, 4, 1],
[8, 7, 3, 5, 2],
];
console.log(solution(arr));상하에 없는 배열을 검사할 수 없어서 outline이라는 크기 n에 0으로 이루어진 배열을 만들어서 사용했다.
정답인 10이 잘 나왔다.
다른 풀이를 보자
function solution(arr){
let answer=0;
let n=arr.length;
let dx=[-1, 0, 1, 0];
let dy=[0, 1, 0, -1];
for(let i=0; i<n; i++){
for(let j=0; j<n; j++){
let flag=1;
for(let k=0; k<4; k++){
let nx=i+dx[k];
let ny=j+dy[k];
if(nx>=0 && nx<n && ny>=0 && ny<n && arr[nx][ny]>=arr[i][j]){
flag=0;
break;
}
}
if(flag) answer++;
}
}
return answer;
}
let arr=[[5, 3, 7, 2, 3],
[3, 7, 1, 6, 1],
[7, 2, 5, 3, 4],
[4, 3, 6, 4, 1],
[8, 7, 3, 5, 2]];
console.log(solution(arr));중요한 부분은 이부분이다.
let dx=[-1, 0, 1, 0];
let dy=[0, 1, 0, -1];이 부분은 각 격자에 상하좌우 값을 가져오기 위한 좌표값을 배열로 초기화해 정리해 놓은 것이다.
이게 실무는 아니지만 이렇게 하면 원하는 좌표값이 변경되면 수정하기도 편해 유지보수성이나 보기에도 좋을 것 같다.
이 코드를 실행하기 위해서는 좌표배열을 비교할 수 있도록 3중 for문을 돌아야한다.
for(let i=0; i<n; i++){
for(let j=0; j<n; j++){
let flag=1; // 1 | 0 으로 하셨는데 boolean 타입처럼 쓸려고 그런듯 나는 boolean이 좋다
for(let k=0; k<4; k++){
let nx=i+dx[k]; // 타겟의 x값 가져오기
let ny=j+dy[k]; // 타겟의 y값 가져오기
if(nx>=0 && nx<n && ny>=0 && ny<n && arr[nx][ny]>=arr[i][j]){
// 봉우리가 아닌(false) 경우
// 1. 타겟 좌표(x,y)가 격자표안에 없을 경우: nx>=0 && nx<n && ny>=0 && ny<n
// 2. 타겟이 해당 요소보다 클 경우
flag=0;
break;
}
}
if(flag) answer++;
}정리해서 주석에 담아 봤다.
나는 각각의 조건들에게 계산하여 변수로 지정하여 비교하였고 다른 코드는 조건을 배열로 만들고 조건에 맞는 값을 계산해 비교하도록 구현되었다. 뭐가 정답인지는 모르겠다. 하지만 답안으로 나온 코드가 유연하고 깔끔하다고 생각된다.
마무리
여담으로 1차원 배열을 특정 값으로 초기화 또는 선언할 때
const newArr = Array.from({ length: n }, () => 0);위 방식보다
const newArr = Array(n).fill(0);이 방식으로 배열을 생성하는 방식이 속도가 더 빠르다고 한다.(코드부터 빨라 보인다.)
하지만 2차원 배열은 아래와 같이 Array.from을 이용해야 한다.
//깊은 복사
const deepCofy = Array.from(Array(n), ()=>Array(n).fill(0));
// 얕은 복사
const shallowCopy = Array(n).fill(Array(n).fill(0));위 두 변수는 똑같은 0으로 이루어진 2차원 배열이다.
function shallowCopy(n) {
let newArr = Array(n).fill(Array(n).fill(0));
newArr[0][0] = 1;
return newArr;
}
console.log(shallowCopy(5));
// 출력: [[1,0,0,0,0],[1,0,0,0,0],[1,0,0,0,0],[1,0,0,0,0],[1,0,0,0,0]]
function deepCopy(n) {
let newArr = Array.from(Array(n), () => Array(n).fill(0));
newArr[0][0] = 1;
return newArr;
}
console.log(deepCopy(5));
// 출력: [[1,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0]]하지만 초기화 이후 값을 변경할 때 출력값이 서로 다르다.
그 이유는
깊은 복사와얕은 복사
깊은 복사는 전체 데이터를 복사한다 -> 각각의 인스턴스는 모두 독립적이며 각자 메모리를 가진다.
얕은 복사는 인스턴스가 메모리에 새로 생성되지 않고 주소값을 복사하여 복사의 주체와 같은 메모리를 가리킨다.
그럼 위 상황과 관련하여 풀이하면
shallowCopy(): Array(n).fill(Array(n).fill(0))을 사용한 얕은 복사의 경우
Array(n)로 n 크기의 배열을 만들고 각 요소에 Array(n).fill(0)로 초기화 된 배열로 채운다.
중요한 점은 '채운다'(fill) 는 것으로 Array(n).fill(Array(n).fill(0))로 생성된 모든 배열들은 Array(n).fill(0)이라느 하나의 배열 주체를 참조 할당하게 되며 각 요소가 동일한 배열을 가리키게 된다.
deepCopy(): Array.from(Array(n), () => Array(n).fill(0))을 사용하면 두 번째 인자로 전달된 함수가 각 배열 요소마다 새로운 배열을 생성하며 각각의 인스턴스가 생성이 된다.
Array(n).fill(0)의 경우 0 같은 number 타입은 원시타입이기 때문이다.
원시타입(primitive type) 은 JavaScript에서, 원시 값(primitive, 또는 원시 자료형)이란 객체가 아니면서 메서드 또는 속성도 가지지 않는 데이터입니다. 원시 값에는 7가지의 종류가 있습니다.string, number, bigint, boolean, undefined, null, symbol(ES6+) - MDN
자바스크립트에서 원시 타입 (string, number, bigint, boolean, undefined, ES6 부터 추가된 symbol) 은 변수에 할당될 때, 메모리의 고정 크기로 원시 값을 저장하고 해당 저장된 값을 변수가 직접적으로 가리키는 형태를 띈다. 또한 값이 절때 변하지않는 불변성을 갖고있기때문에 때문에 재할당 시 기존 값이 변하는것 처럼 보일지 몰라도 사실 새로운 메모리에 재할당한 값이 저장되고 변수가 가리키는 메모리가 달라졌을 뿐이다. - @nomadhash
문제출처: 👉🏻인프런 강의
