코딩테스트에서는 종종 데이터 구조와 알고리즘 관련 문제가 출제됩니다. 특히 친구 관계를 파악하는 문제는 그래프 이론과 관련이 있으며, 많은 기업들이 이러한 문제를 통해 지원자의 논리적 사고와 코딩 능력을 평가합니다.
문제 설명
친구 관계를 파악하는 알고리즘 문제는 다음과 같습니다.
문제: 친구 관계 탐색
주어진 인원 N과 친구 관계를 나타내는 M개의 쌍이 있을 때, 특정 인원이 친구가 아닌 모든 사람들의 수를 구하는 함수를 작성하시오.
입력 형식
- 첫 번째 줄: 사람의 수 N (1 ≤ N ≤ 100)
- 두 번째 줄: 친구 관계의 수 M (1 ≤ M ≤ 1000)
- 세 번째 줄: M개의 친구 관계 쌍 (a b) 형태로 제공되며, 이는 a와 b가 친구임을 의미한다.
- 네 번째 줄: 특정 인원 X (1 ≤ X ≤ N) – 친구 관계를 확인할 인원
출력 형식
입력된 인원 X의 친구가 아닌 사람의 수를 출력하시오.
예제 입력
5
4
1 2
1 3
2 4
4 5
1
예제 출력
3
문제 풀이 과정
1단계: 문제 이해 및 분석
주어진 문제를 이해하기 위해서는 입력으로 제공되는 친구 관계를 그래프로 표현할 수 있어야 합니다. 이를 위해 인접 리스트를 사용하기로 합니다. 이 방법을 통해 각 인원과 그들의 친구를 연결하여 관계를 쉽게 파악할 수 있습니다.
2단계: 데이터 구조 설계
각각의 인원은 배열의 인덱스를 통해 친구 관계를 저장할 수 있습니다. 예를 들어, 인원 1과 친구인 인원을 저장하기 위해 인접 리스트에 상대 인원의 번호를 추가합니다. 이 구조를 사용하면 특정 인원의 친구를 쉽게 찾을 수 있습니다.
3단계: 알고리즘 설계
친구가 아닌 사람의 수를 계산하기 위해 다음과 같은 절차를 따릅니다:
- 모든 인원(1부터 N까지)과 친구 관계를 확인하여 친구 리스트를 생성합니다.
- 특정 인원 X의 친구 리스트를 참조하여 친구가 아닌 사람의 수를 계산합니다.
- 최종적으로 friendCount 변수를 선언하고, 인원 수에서 X와 X의 친구 수를 빼면 친구가 아닌 사람의 수를 얻을 수 있습니다.
4단계: 자바스크립트 구현
function countNonFriends(N, M, relations, X) {
// 인접 리스트 생성
const friends = Array.from({ length: N + 1 }, () => []);
// 관계 추가
relations.forEach(([a, b]) => {
friends[a].push(b);
friends[b].push(a);
});
// 친구가 아닌 인원 수 세기
const friendSet = new Set(friends[X]);
let count = 0;
for (let i = 1; i <= N; i++) {
if (i !== X && !friendSet.has(i)) {
count++;
}
}
return count;
}
const N = 5;
const M = 4;
const relations = [[1, 2], [1, 3], [2, 4], [4, 5]];
const X = 1;
console.log(countNonFriends(N, M, relations, X)); // 3
5단계: 시간 복잡도 분석
이 알고리즘의 시간 복잡도는 각각의 친구 관계를 확인하고 세는 과정에서 O(N + M)의 복잡도를 가집니다. 이는 각 관계를 한 번씩만 탐색하기 때문에 효율적입니다.
결론
이 문제를 통해 그래프 관련 문제를 푸는 과정과 친구 관계를 파악하는 방법을 배울 수 있습니다. 또한, 자바스크립트의 배열과 객체를 활용하여 데이터를 관리하고, 알고리즘을 구현하는 연습을 할 수 있습니다. 코딩테스트 준비 시, 이러한 문제 유형을 여러 번 풀어보는 것이 중요합니다.