알고리즘
백준
- 1904 01타일
const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
let input = fs.readFileSync(filePath).toString().trim().split('\n');
const n = Number(input[0]);
function solution(n) {
if (n === 1) {
return 1;
}
const dp = new Array(n + 1).fill(0);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = (dp[i - 1] + dp[i - 2]) % 15746;
}
return dp[n];
}
const result = solution(n);
console.log(result);프로그래머스
- 두 개 뽑아서 더하기 (Level 1)
function solution(numbers) {
let result = new Set();
for (let i = 0; i < numbers.length - 1; i++) {
for (let j = i + 1; j < numbers.length; j++) {
result.add(numbers[i] + numbers[j]);
}
}
result = Array.from(result);
result.sort((a, b) => a - b);
return result;
}- 나머지가 1이 되는 수 찾기 (Level 1)
function solution(n) {
for (let i = 2; i < n; i++) {
if (n % i === 1) {
return i;
}
}
}- 짝지어 제거하기 (Level 2)
function solution(s) {
const stack = new Array();
for (let i = 0; i < s.length; i++) {
if ((stack.length > 0) && (stack[stack.length - 1] === s[i])) {
stack.pop();
} else {
stack.push(s[i]);
}
}
if (stack.length !== 0) {
return 0;
}
return 1;
}처음엔 재귀로 풀었는데, 런타임에러가 계속 발생했다. 1가지 간과한 점이 있었는데, 자바스크립트에서는 call stack에 쌓일 수 있는 함수의 갯수가 10,000개 정도로 제한되어 있다는 점이다.
이러한 점이 어떤 문제를 일으키냐면, 해당 프로그래머스 문제는 문자열의 길이가 1,000,000이니 1,000,000개의 재귀 함수가 call stack에 쌓일 수 있다. ('a'라는 문자열이 1,000,000개 정도 되는 경우처럼...) 이러면 최대 call stack 갯수를 초과했다고, 자바스크립트 엔진이 돌아가면서 뜨게 되는 런타임 에러가 발생하게 된다.
고민하다가 프로그래머스의 질문하기를 보고 스택을 이용해야 된다는 힌트를 얻었다. 그러니 위처럼 간단히 풀렸다... 근데 다음에 다시 풀 때 한 번에 풀 수 있을까...?
- 게임 맵 최단거리 (Level 2)
function solution(maps) {
const newMaps = [...maps];
const n = newMaps[0].length;
const m = newMaps.length;
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
const queue = new Array();
queue.push([0, 0, 1]);
while (queue.length > 0) {
const [cx, cy, count] = queue.shift();
for (let i = 0; i < 4; i++) {
const nx = cx + dx[i];
const ny = cy + dy[i];
if ((0 <= nx && nx < m) && (0 <= ny && ny < n) && (newMaps[nx][ny] === 1)) {
if ((nx === m - 1) && (ny === n - 1)) {
return count + 1;
}
newMaps[nx][ny] = 0;
queue.push([nx, ny, count + 1]);
}
}
}
return -1;
}- 프린터 (Level 2)
function solution(priorities, location) {
const newPriorities = [...priorities].map((value, index) => ({
value: value,
index: index
}));
let count = 0;
while (newPriorities.length > 0) {
const currentPriority = newPriorities.shift();
const hasHigherPriority = newPriorities.some((element) => element.value > currentPriority.value);
if (hasHigherPriority === true) {
newPriorities.push(currentPriority);
} else {
count += 1;
if (currentPriority.index === location) {
return count;
}
}
}
}풀긴 풀었는데 똥내나는 코드 같아서 다른 사람의 풀이를 참고해보니 애초에 priorities의 각 원소를 객체로 만들어버리고 있었다. 이는 index를 보관하면서 나중에 진짜 pop될 때 location과 비교해서 답을 도출해낼 때 비교하기 위함인 것이다. 난 마치 visited 처럼 비교를 위한 배열을 만들었다. priorities가 3개의 원소로 이루어진 배열이고, location이 2라면 visited를 [0, 0, 1]로 만들었다. 그리고 newPriorities를 따라가게 만들었는데(push, shift 될 때 똑같이) 이 방법도 나쁘진 않았던 것 같다. 단지 지금 현재 코드가 더 가독성이 높아보인다. 그리고 some이라는 메소드도 알 수 있게 되었다. 배열을 순회하면서 콜백의 함수에 따라 하나라도 true로 판정될 수 있는 원소가 있다면 곧바로 true를 내뱉어주는 친구이다. 직접 짤 수도 있겠지만 이렇게 해주면 함수형 프로그래밍으로(맞나?) 더 간결하게 나타내 줄 수 있을거라 본다.
- 네트워크 (Level 3)
function DFS(i, n, computers, visited) {
for (let j = 0; j < n; j++) {
if (computers[i][j] === 1 && visited[j] === 0) {
visited[j] = 1;
DFS(j, n, computers, visited);
}
}
}
function solution(n, computers) {
const visited = new Array(n).fill(0);
let count = 0;
for (let i = 0; i < n; i++) {
if (visited[i] === 0) {
count += 1;
visited[i] = 1;
DFS(i, n, computers, visited);
}
}
return count;
}입력값을 바탕으로 인접 행렬을 만들어야 하는 백준과 달리 인접 행렬을 줘버리니 편하긴 하다!
- 올바른 괄호 (Level 2)
function solution(s) {
if (s[0] === ')') {
return false;
}
const stack = new Array();
for (let bracket of s) {
if (bracket === '(') {
stack.push(bracket);
}
if (bracket === ')') {
if (stack.length === 0) {
return false;
}
if (stack[stack.length - 1] === '(') {
stack.pop();
}
if (stack[stack.length - 1] === ')') {
return false;
}
}
}
if (stack.length > 0) {
return false;
}
return true;
}