https://www.acmicpc.net/problem/28298
JS로 구현문제 준비 2일차가 됐습니다. 평소에 개발하면서 수많은 복붙을 하며 넘어가기 때문에, 막상 백지상태에서 알고리즘을 풀려고 하니.. 실력이 바로 보입니다. 단순한 3차원배열 초기화에도 애를 먹으니..
그래서 파이썬 풀이방법 포스팅과 다르게 JS 풀이는 내가 몰랐던, 기억해야할 문법들을 짚고 넘어가겠습니다.
문제는 UCPC 2023번 예선 D번으로 2차원배열을 서브 그리드로 나누어서 계산 가능하냐를 묻는 문제입니다.
NxM 배열에서 KxK의 정사각형으로 나누어 각 자리에 최대로 많이 등장한 알파벳을 찾을 수 있다면 해결할 수 있습니다.
const input = require("fs")
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./ex.txt")
.toString()
.split("\n") // 문자열 작은 따옴표 안됨. 큰 따옴표로 묶어야 함
.map(line => line.trim());
const [n, m, k] = input[0].split(' ').map(Number);
const [...g] = input.slice(1);
let alphaCount = new Array(k).fill(0).map(() => new Array(k).fill(0).map(()=>({})));
for (let i = 0; i < n; i+=k){
for (let j = 0; j < m; j+=k){
for (let x = 0; x < k; x++){
for (let y = 0; y < k; y++){
const char = g[i + x][j + y];
if (alphaCount[x][y][char]===undefined) {
alphaCount[x][y][char] = 1;
}
else {
alphaCount[x][y][char]++;
}
}
}
}
}
let res = 0;
let G = [];
for (let i = 0; i < k; i++){
let str = '';
for (let j = 0; j < k; j++){
let maxChar = Object.keys(alphaCount[i][j]).reduce((a, b) => alphaCount[i][j][a] > alphaCount[i][j][b] ? a : b);
str += maxChar;
let sum = Object.values(alphaCount[i][j]).reduce((a, c) => a + c);
let max = Math.max(...Object.values(alphaCount[i][j]));
res += sum - max;
}
G.push(str.repeat(m / k));
}
console.log(res);
for (let i = 0; i < n; i++){
console.log(G[i%k]);
}
첫 번째 JS 풀이이므로 한 문단 씩 보겠습니다.
const input = require("fs")
.readFileSync(process.platform === "linux" ? "/dev/stdin" : "./ex.txt")
.toString()
.split("\n") // 문자열 작은 따옴표 안됨. 큰 따옴표로 묶어야 함
.map(line => line.trim());
const [n, m, k] = input[0].split(' ').map(Number);
const [...g] = input.slice(1);
먼저 여기서, 아마 첫 번째 고비인데, JS에서는 백준 입력을 어떻게 받을 수 있지? 에 대한 물음입니다.
구글링 해본 결과 저 readFileSync부분에 나의 풀이과정 땐 txt 파일을 넣고 제출할 땐 "/dev/stdin"을 넣어 제출합니다. 그래서 제출할 때 은근 불편합니다.
그런데 node js 풀이를 많이 찾아보니 저 코드 하나로 백준 채점과 현재 내 로컬을 구분할 수 있는 코드를 발견해서 잘 쓰고 있습니다. 뒤에 toString은 모두 문자열로 받고, Split() 은 안에 구분자를 기준으로 나누어 저장해줍니다. 후에 map으로 각 line 마다 trim을 해줘서 공백을 제거했습니다. 이렇게 하면 아래 모습 처럼 저장이 됩니다.
[ '4 6 2', 'ABCBAB', 'BBACCA', 'BPAZBB', 'BBAABB' ] // input
이후에 input[0]을 구조분해할당해서 n,m,k로 나누어주고, 나머지 문자열은 slice로 따로 2차원배열 느낌으로 저장해줍니다.( 사실은 1차원배열에 여러개의 문자열)
이제 그 다음 부분인데, 아래와 같은 모양의 2차원 배열 각각에 빈 Object 를 넣고 싶었습니다. 파이썬에서는 dict() 를사용해서 딕셔너리를 넣으면 됐는데, JS에서는 Object 자체가 딕셔너리 역할을 합니다.
[ [ {}, {} ], [ {}, {} ] ]이 때 두 가지 방법이 있는데,
let alphaCount = Array.from({length: k}, () => Array.from({length: k}, () => ({})));
let alphaCount = new Array(k).fill(0).map(() => new Array(k).fill(0).map(() => ({})));Array from 과 fill을 사용한 방법입니다. 아직은 2일차라 뭐가 더 좋은 코드인지는 모르겠지만, 타이핑상 fill이 더 빠르고 직관적인 느낌이라 이 방법을 사용중입니다. from 은 length 옵션을 받고 콜백함수를 반복해서 생성해주는 것 같습니다. 따라서 콜백함수에서 다시 한번 Array from 으로 마지막엔 소괄호를 쳐준 객체 ( { } ) 를 반환하는 모습입니다. 소괄호를 쳐주지 않으면 { } 가 코드 블럭으로 인식돼서 undefined가 됩니다. fill 은 값을 채울 때 주로 사용하는 것 같은데, 우선 k길이의 Array를 0으로 채운 다음, 각각의 0 을 map함수로 다시 k길이의 Array로 바꾸고 또 그 안의 0을 다시한번 객체로 바꾸는 식입니다.
let alphaCount = new Array(k).fill(0).map(() => new Array(k).fill(0).map(()=>({})));
for (let i = 0; i < n; i+=k){
for (let j = 0; j < m; j+=k){
for (let x = 0; x < k; x++){
for (let y = 0; y < k; y++){
const char = g[i + x][j + y];
if (alphaCount[x][y][char]===undefined) {
alphaCount[x][y][char] = 1;
}
else {
alphaCount[x][y][char]++;
}
}
}
}
}후에 NxM배열을 돌면서 만약에 그 자리에 있는 알파벳이 나온적이 있다면 1을 증가시키고 없다면 추가해주는 식으로 구현합니다. 파이썬에서의 구현과 같은 결과를 가져옵니다.
#Python
a = {'a':2, 'b':3}
if 'a' in a: a['a'] += 1
if 'c' not in a: a['c'] = 1
저장을 다 했다면, 이제 alphaCount 2차원 배열을 돌면서 각 객체의 최대 등장 알파벳과 횟수를 찾습니다. 여기에선
Object.Keys() 안에 alphaCount 객체를 넣고 reduce를 통해 최대등장 알파벳을 찾았습니다. 아마 파이썬이었다면 for문으로 key value 튜플로 돌면서 찾았을겁니다. 그리고 str 빈 문자열에 붙여 저장한 후, 마지막에 repeat으로 원래 NxM크기의 배열을 만들기 위해 나눈 값만큼 반복해줍니다. 그 문자열은 G배열에 push 해서 저장해서 출력하면 됩니다.
let res = 0;
let G = [];
for (let i = 0; i < k; i++){
let str = '';
for (let j = 0; j < k; j++){
let maxChar = Object.keys(alphaCount[i][j]).reduce((a, b) => alphaCount[i][j][a] > alphaCount[i][j][b] ? a : b);
str += maxChar;
let sum = Object.values(alphaCount[i][j]).reduce((a, c) => a + c);
let max = Math.max(...Object.values(alphaCount[i][j]));
res += sum - max;
}
G.push(str.repeat(m / k));
}
console.log(res);
for (let i = 0; i < n; i++){
console.log(G[i%k]);
}
이 문제하나로 2차원배열 3차원배열 초기화하는 법을 제대로 알게 되었고, 각각에서 최대 최소를 구하여 저장하는 것을 알았습니다. 배열의 합은 reduce로, 최댓값은 spread연산으로 배열을 다 펴서 전달하고, 객체 자체를 반환할 때는 소괄호를 치는 것을 잊지 말도록 합니다.
