문제
풀이
요구사항
n명의 회사 직원이 있고, 이들에겐 1번부터 n번까지 번호가 부여되어 있다.
이 회사는 특정 직원에게 칭찬을 하면 해당 직원의 직속 부하직원을 칭찬하고 칭찬을 받은 직속 부하직원은 또다시 자신의 직속 부하 직원에게 칭찬을 해야하는 '내리칭찬' 문화가 있다.
입력값으로 직원별로 직속 상사의 번호가 주어진다.
그리고 어떤 직원이 몇점 만큼의 칭찬을 받았는지도 주어진다.
이때 n명의 직원이 받은 칭찬의 점수를 각각 출력해야 한다.
(1번 직원은 사장이므로, 직속 상사가 없다.)
해결방안
이 문제는 그래프 탐색과 DP 두가지 유형으로 풀 수 있다.
우선 그래프 탐색으로 푸는 방법부터 알아보자.
우선 상사와 부하직원을 트리 형태로 연결한다.
나는 이 트리를 graph라는 이름의 변수에 저장했다.
graph[i]에는 i번 직원의 직속 부하 직원들의 번호를 저장한다.
이렇게 트리형태로 만들었으면 DFS나 BFS를 사용해서 풀 수 있다.
하지만 구현에서 주의할 점이 있다. 우선 아래의 시간초과가 난 코드를 보자.
BFS (시간초과)
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [n, m] = input[0].split(' ').map(Number);
const superior = input[1].split(' ').map(Number);
const employee = input.slice(2, 2 + m).map((e) => e.split(' ').map(Number));
const graph = Array.from({ length: n + 1 }, () => []);
const compliment = Array(n + 1).fill(0);
class Queue {
constructor() {
this.queue = {};
this.front = 0;
this.rear = 0;
}
enqueue(value) {
this.queue[this.rear] = value;
this.rear++;
}
dequeue() {
const temp = this.queue[this.front];
delete this.queue[this.front];
this.front++;
if (this.front === this.rear) {
this.front = this.rear = 0;
}
return temp;
}
size() {
return this.rear - this.front;
}
}
function bfs(start) {
const queue = new Queue();
queue.enqueue(start);
while (queue.size() > 0) {
// i=직원 번호, w=칭찬 받은 점수
const [i, w] = queue.dequeue();
for (const next of graph[i]) {
compliment[next] += w;
queue.enqueue([next, w]);
}
}
}
for (let i = 1; i < n; i++) {
graph[superior[i]].push(i + 1); // graph[i] = i의 직속 부하
}
// 시간 초과를 유발하는 부분
for (const [i, w] of employee) {
compliment[i] += w;
bfs([i, w]);
}
compliment.shift();
console.log(compliment.join(' '));위 코드처럼 각각의 i,w 마다 bfs를 수행하면 한 번의 bfs당 N번의 연산이 수행되고, 이를 M번 반복하기 때문에 총 N*M(100,000 * 100,000)번의 연산을 수행해서 시간초과가 발생한다.
BFS (통과)
시간초과를 받지 않으려면 칭찬 점수를 저장하는 compliment 배열에 먼저 칭찬 점수를 전부 입력해놓고, bfs를 한 번만 수행해주면 통과할 수 있다. 이때 bfs는 root노드 즉, 1번 직원(사장)부터 출발하여, 만약 compliment[i]에 점수가 있다면 직속 부하 직원들에게도 compliment[i]만큼의 칭찬 점수를 누적해주면 된다.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [n, m] = input[0].split(' ').map(Number);
const superior = input[1].split(' ').map(Number);
const employee = input.slice(2, 2 + m).map((e) => e.split(' ').map(Number));
const graph = Array.from({ length: n + 1 }, () => []);
const compliment = Array(n + 1).fill(0);
class Queue {
constructor() {
this.queue = {};
this.front = 0;
this.rear = 0;
}
enqueue(value) {
this.queue[this.rear] = value;
this.rear++;
}
dequeue() {
const temp = this.queue[this.front];
delete this.queue[this.front];
this.front++;
if (this.front === this.rear) {
this.front = this.rear = 0;
}
return temp;
}
size() {
return this.rear - this.front;
}
}
function bfs(start) {
const queue = new Queue();
queue.enqueue(start);
while (queue.size() > 0) {
const i = queue.dequeue();
for (const next of graph[i]) {
compliment[next] += compliment[i];
queue.enqueue(next);
}
}
}
for (let i = 1; i < n; i++) {
graph[superior[i]].push(i + 1); // graph[i] = i의 직속 부하
}
for (const [i, w] of employee) {
compliment[i] += w;
}
bfs(1);
compliment.shift();
console.log(compliment.join(' '));
그래프 탐색 외에도 DP를 사용하면 더 빠르고 간결하게 문제를 풀 수 있다.
DP (통과)
이 방법도 마찬가지로 compliment에 점수를 먼저 채워준다.
compliment[i] = i번 직원의 칭찬 점수 를 의미한다.
superior은 입력으로 주어진 직속 상사들의 번호가 담겨있다. superior[i] = i번 직원의 직속 상사 를 의미한다.
따라서 compliment[superior[i]] = i번 직원의 직속 상사의 칭찬 점수가 되고 이를 compliment[i] = i번 직원의 칭찬 점수 에 누적해주면 된다.
직원 번호 = 1 2 3 4 5
직속 상사 = -1 1 2 3 4
compliment = 0 2 4 0 6const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [n, m] = input[0].split(' ').map(Number);
const superior = [0].concat(input[1].split(' ').map(Number));
const employee = input.slice(2, 2 + m).map((e) => e.split(' ').map(Number));
const compliment = Array(n + 1).fill(0);
for (const [i, w] of employee) {
compliment[i] += w;
}
for (let i = 2; i <= n; i++) {
compliment[i] += compliment[superior[i]];
}
compliment.shift();
console.log(compliment.join(' '));
주의할 점
이 문제 입력값 개수가 좀 이상하다.
이걸 모르고 처음에는 아래와 같이 코드를 작성했었다.
const employee = input.slice(2).map((e) => e.split(' ').map(Number));하지만 계속해서 틀렸다는 결과가 나왔고, 도저히 뭐가 문젠지 모르겠어서 질문 게시판에 글을 올렸다.
그리고 잠시 후에 코드를 아래와 같이 수정해보라는 답변이 달렸다.
const employee = input.slice(2, 2+m).map((e) => e.split(' ').map(Number));그래서 위와 같이 코드를 수정했더니 통과했다.
이유를 들어보니 입력값 [직원의 번호, 칭찬 수치] = [i,w]의 개수는 m개여야 하지만, 실제로 제출했을 때 테스트케이스 중 [i,w]의 개수가 m개보다 많이 들어오는 경우가 있어서 틀렸다는 결과가 나온 것이다.
게다가 하필이면 for ... of문을 사용해서 employee의 원소의 개수에 따라 다르게 동작했기에 이런 문제가 발생한 것이다.
실제로 for ... of를 for문으로 바꿔서 제출하니 같은 코드임에도 통과가 되었다.
