좌충우돌 anecdote

문제

https://leetcode.com/problems/spiral-matrix/description/

Given an m x n matrix, return all elements of the matrix in spiral order.

=> m x n 행렬이 주어지면 행렬의 모든 원소를 나선형 순서로 반환하라.

문제 풀이

2차열 배열을 나선형 순서로 순회하는 문제이다.

1. 위쪽 가로줄

2. 오른쪽 세로줄

3. 아래쪽 가로줄

4. 왼쪽 세로줄

1~4까지 순서대로 순회하면 되는데, 단 3, 4번에서 1, 2를 방문했는지 체크해야 한다. 

예를 들어보자.
3번을 순회하는데 top이 bottom을 넘으면 이미 위쪽 가로줄을 방문한 상태이므로 아래로 내려갈 필요가 없다.

또 4번을 순회하는데 left가 right을 넘으면 이미 오른쪽 세로줄을 방문한 상태이므로 왼쪽으로 이동할 필요가 없다.

해당 규칙만 알고 문제를 풀면 된다.

코드

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function(matrix) {
    if (!matrix || matrix.length === 0) {
        return [];
    }

    const result = [];
    let top = 0;
    let right = matrix[0].length - 1;
    let bottom = matrix.length - 1;
    let left = 0;

    while (top <=bottom && left <= right) {
        // 위쪽 가로줄
        for (let i=left; i<=right; i++) {
            result.push(matrix[top][i])
        }
        top++;

        // 오른쪽 세로줄
        for (let i=top; i<=bottom; i++) {
            result.push(matrix[i][right])
        }
        right--;

        // 아래 가로줄
        if (top <= bottom) {
            for (let i=right; i>=left; i--) {
                result.push(matrix[bottom][i])
            }
            bottom--;
        }

        // 왼쪽 세로줄
        if (left <= right) {
            for (let i=bottom; i>=top; i--) {
                result.push(matrix[i][left])
            }
            left ++;
        }
    }
    return result;
};

문제

이번 정보 올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 한다.
각 문제는 그것을 풀었을 때 얻는 점수와 푸는 데 걸리는 시간이 주어지게 된다.
제한 시간 M 안에 N개의 문제 중 최대점수를 얻을 수 있는 경우를 구하는 문제이다.
단, 해당 문제는 해당 시간이 걸리면 푸는 걸로 간주하고 한 유형당 한 개만 풀 수 있다.

문제 풀이

해당 문제는 "문제를 풀거냐, 말거냐"로 나눠지는 이진트리 방식인 DFS 로 해결할 수 있다.

문제를 풀었을 때 얻는 점수 = sum

문제를 푸는 데 걸리는 시간 = time

DFS(L, sum, time)이 들어가고, 

1. 문제를 풀것인가
2. 문제를 풀지 않을 것인가

L이 n번째까지 오지 않을 경우

1번의 경우 L + 1, sum + 이전 sum, time + 이전 time

2번의 경우 L만 +1되고 sum, time

L이 n번째까지 온 경우

합계 비교 후 최대값을 넣어준다.

const fs = require('fs');
const filePath =
	process.platform === 'linux'
		? '/dev/stdin'
		: 'Javascript/dfs/최대점수구하기.txt';
const input = fs.readFileSync(filePath).toString().split('\n');

solution(input);

function solution(input) {
	const [n, m] = input[0].split(' ').map((i) => +i);
	let answer = Number.MIN_SAFE_INTEGER;
	const ps = []; // 점수
	const pt = []; // 문제를 푸는데 걸리는 시간
	for (let i = 1; i < n; i++) {
		[ps[i], pt[i]] = input[i].split(' ').map((i) => +i);
	}

	function DFS(L, sum, time) {
		if (time > m) return;
		if (L === n) {
			if (time <= m) {
				answer = Math.max(answer, sum);
			}
		} else {
			DFS(L + 1, sum + ps[L], time + pt[L]); // 문제를 푼다
			DFS(L + 1, sum, time); // 문제를 안푼다
		}
	}

	DFS(0, 0, 0);
	console.log(answer);
}

4가지 모두 공통적으로 고차함수이다.
*고차 함수: 자신의 매개변수에 함수를 전달 받는 것

1. forEach

function forEach(predicate, thisArg) {
	for(let i=0; i<a.length; i++) {
    	predicate(a[i], i); // 반복해서 호출하는 것
    }
}

a = [10, 11, 12, 13, 14, 15];
a.forEach(function(v, i){ // 인자로 callback함수를 넘겨준다.
	console.log(v, i)
});

2. map

원본 배열을 하나하나 탐색하면서 새로운 배열을 생성한다.

function map(predicate, thisArg) {
	// 새로운 배열 생성
	let list=[];
    for(let i=0; i<a.length; i++) {
    	list.push(predicate(a[i], i));
    }
    return list;
}

a = [10, 11, 12, 13, 14, 15]
let answer = a.map(function(v, i) {
	return v*v;
});

console.log(answer); // [100, 121, 144, 169, 196, 225]

새로운 배열을 넘겨받을 수 있고, 중요한 것은 새로운 배열과 원본 배열의 길이는 같다. 

let answer = a.map(function(v, i){
	if (v%2 == 0) return v; // [10, undefined, 12, undefined, 14, undefined]
};

만약 위와 같이 11, 13, 15와 같이 홀수인 값은 return되지 못해 undefined 값을 푸시한다.

3. filter

map과 같이 새로운 배열을 생성하지만, 말그대로 filter 즉, 걸러준다고 생각하자!

filter는 원하는 원소만 배열을 생성해서 return 해준다.

let answer = a.map(function(v, i){
	if (v%2 == 0) return v; // [10, 12, 14]
};

따라서 map과는 다르게 원본과 생성된 배열의 길이가 같지 않다

 4. reduce

배열의 각 요소를 순회하며 callback 함수의 실행 값을 누적하여 하나의 결과 값을 반환한다.

function reduce(predicate, arg) {
	let result = arg; // 넘어온 값을 초기화한다.
    for(let i=0; i<a.length; i++) {
    	result = predicate(result, a[i]);
    }
    return result;
}

a = [10, 11, 12, 13, 14, 15]
answer = a.reduce(function(accumulate, v){
	return accumulate + v;
}, 0);

처음에 result에 0이 들어가고,

0 + 10 = 10

10 + 11 = 21

21 + 12 = 33 
...

결국 10 ~ 15를 더하게 된다!

*출처: 해당 코드들은 인프런 [자바스크립트 알고리즘 문제풀이 입문]을 들으며 수강한 내용입니다.