코딩테스트는 많은 개발자들이 겪는 어려운 과정입니다. 특히 자바스크립트로 문제를 해결해야 할 때는 언어의 특성을 잘 이해하고 있어야 합니다. 이번 강좌에서는 ‘거짓말쟁이가 되긴 싫어’라는 문제를 통해 자바스크립트의 특성과 알고리즘 접근 방식을 살펴보겠습니다.
문제 설명
다음과 같은 상황을 상상해보세요. 당신은 여러 친구와 함께 캠프를 가고 있습니다. 친구들 중 일부는 괴짜들이어서, 어떤 특정 사건에 대해서는 거짓말을 하기로 결심했습니다. 다음은 각 친구들이 이야기한 내용입니다.
주어진 입력은 배열로 표현되며, 각 배열의 값은 친구들이 주장하는 친구의 숫자입니다. 당신의 목표는 주장에 맞는 친구의 수가 다수일 때, 그 친구들이 거짓말을 하고 있다고 판단하는 것입니다.
예시 입력
const statements = [
[0, 1], // 친구 0은 친구 1을 주장
[1, 2], // 친구 1은 친구 2를 주장
[2, 0], // 친구 2는 친구 0을 주장
[3, 2], // 친구 3은 친구 2를 주장 (여기서 친구 3은 거짓말쟁이다)
];
예시 출력
거짓말을 하는 친구의 수: 1
문제 해결 과정
이 문제에 접근하는 첫 번째 단계는 각 친구가 누군가를 주장하는 관계를 이해하는 것입니다. 여기서는 유향 그래프를 사용하여 각각의 친구를 노드로, 주장하는 관계를 간선으로 나타낼 수 있습니다.
1. 데이터 구조 설계
우선, 각 친구에 대한 주장을 저장할 수 있는 자료구조를 정의해야 합니다. 이를 위해 객체를 사용하여 친구의 ID와 그 친구가 주장하는 친구의 ID의 목록을 맵핑할 수 있습니다.
const graph = {};
statements.forEach(([speaker, listener]) => {
if (!graph[speaker]) {
graph[speaker] = [];
}
graph[speaker].push(listener);
});
2. DFS/BFS를 통한 탐색
주장 간의 관계를 탐색하기 위해 DFS(깊이 우선 탐색) 혹은 BFS(너비 우선 탐색)를 사용할 수 있습니다. 이렇게 하면 각 친구의 주장이 유효한지를 확인할 수 있습니다.
function hasContradictions(speaker) {
const visited = new Set();
const stack = [speaker];
while (stack.length) {
const curr = stack.pop();
if (visited.has(curr)) {
return true; // 이미 방문한 노드를 다시 방문할 경우 모순 발생
}
visited.add(curr);
if (graph[curr]) {
graph[curr].forEach(listener => {
stack.push(listener);
});
}
}
return false;
}
3. 전체 친구에 대해 확인
모든 친구를 확인하여, 주장이 유효하지 않은 친구의 수를 셉니다. 전체 친구의 수중 몇 명이 모순을 만드는지를 파악하는 과정입니다.
let liarsCount = 0;
for (let i = 0; i < statements.length; i++) {
if (hasContradictions(i)) {
liarsCount++;
}
}
return liarsCount;
최종 코드
function findLiars(statements) {
const graph = {};
statements.forEach(([speaker, listener]) => {
if (!graph[speaker]) {
graph[speaker] = [];
}
graph[speaker].push(listener);
});
function hasContradictions(speaker) {
const visited = new Set();
const stack = [speaker];
while (stack.length) {
const curr = stack.pop();
if (visited.has(curr)) {
return true;
}
visited.add(curr);
if (graph[curr]) {
graph[curr].forEach(listener => {
stack.push(listener);
});
}
}
return false;
}
let liarsCount = 0;
for (let i = 0; i < statements.length; i++) {
if (hasContradictions(i)) {
liarsCount++;
}
}
return liarsCount;
}
console.log(findLiars(statements)); // 출력: 1
결론
위와 같은 문제를 통해 자바스크립트의 기본 문법, 자료구조 활용, 그리고 DFS/BFS 알고리즘을 적용하는 법을 배웠습니다. 코딩테스트 준비 시 이러한 문제들을 연습하여 알고리즘적 사고를 키우는 것이 중요합니다.