문제 설명
여러분은 최근에 신입사원 채용을 위한 코딩테스트를 준비하고 있습니다. 이 코딩테스트 문제는
‘거짓말쟁이가 되긴 싫어’라는 주제로 구성되어 있습니다. 이 문제에서는 여러 직원의 이야기를
바탕으로 누군가가 거짓말을 하고 있는지를 판단해야 합니다. 직장 내에서 누가 진실을 말하고
누가 거짓말을 하는지를 명확히 구분하기 위한 알고리즘을 개발해야 합니다.
문제 내용
N명의 직원이 있습니다. 각 직원(A, B, C, …)은 다른 직원에 대해서
‘A는 거짓말쟁이다’, ‘B는 거짓말쟁이다’와 같은 식으로 주장합니다.
각 직원의 주장은 모두 신뢰할 수 있고, 주장이 맞지 않는 경우
일반적으로 그 주장은 거짓말이 됩니다.
입력
- 첫 번째 줄에 직원의 수 N (1 ≤ N ≤ 1000)가 주어집니다.
- 다음 N줄에 각 직원의 주장에 대한 정보가 주어집니다. 각 주장은 “이 직원은 거짓말쟁이다” 형식입니다.
출력
가장 거짓말을 많이 한 직원의 수를 출력합니다. 거짓말을 하지 않은 직원의 수가 1명일 경우에는
0을 출력합니다.
문제 풀이 과정
이 문제를 해결하기 위해서는 직원 간의 관계를 분석하고, 각 직원의 주장을 바탕으로
거짓말을 하는 직원 수를 계산해야 합니다. 여기서 우리는 각 직원의 주장이
어떻게 연결되어 있는지를 파악해야 합니다.
1단계: 데이터 구조 설계
우선, 각 직원의 주장을 저장할 수 있는 데이터 구조를 선택해야 합니다.
우리는 각 직원의 번호를 key로 하고, 그 직원이 거짓말이라고 주장하는 직원 리스트를
value로 가지는 Map을 사용할 수 있습니다.
예를 들어, 직원 1이 직원 2를 거짓말쟁이라고 주장한다면, Map은 다음과 같습니다:
{
1: [2],
2: [3, 4],
3: [1],
...
}
2단계: 그래프 탐색 (DFS 또는 BFS)
Map 구조가 준비되었다면, 이제 그래프 탐색을 통해 누가 진실을 말하고 누가
거짓말을 하고 있는지를 판단해야 합니다. 이를 위해 DFS(Depth-First Search) 또는
BFS(Breath-First Search) 알고리즘을 활용합니다.
3단계: 수집된 데이터 기반으로 결과 계산
탐색이 완료되면 각 직원이 거짓말을 하는지에 대한 정보를 바탕으로
누가 거짓말을 가장 많이 했는지를 계산해 최종 결론을 내립니다.
4단계: 전체적인 코드 작성
자바를 사용하여 위의 단계들을 코드로 구현할 것입니다. 아래는
해당 문제를 해결하기 위한 코드의 예시입니다:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
Map> statements = new HashMap<>();
// 직원 주장을 입력받기
for (int i = 1; i <= n; i++) {
int liarIndex = scanner.nextInt();
if (!statements.containsKey(i)) {
statements.put(i, new ArrayList<>());
}
statements.get(i).add(liarIndex);
}
int maxLiars = 0;
// 각 직원에 대해 거짓말쟁이 수를 계산
for (int i = 1; i <= n; i++) {
HashSet visited = new HashSet<>();
boolean[] isLiar = new boolean[n + 1];
isLiar[i] = true;
dfs(i, statements, visited, isLiar);
int countLiars = 0;
for (int j = 1; j <= n; j++) {
if (isLiar[j]) countLiars++;
}
maxLiars = Math.max(maxLiars, countLiars);
}
System.out.println(maxLiars);
}
private static void dfs(int employee, Map> statements,
HashSet visited, boolean[] isLiar) {
if (visited.contains(employee)) return;
visited.add(employee);
if (statements.containsKey(employee)) {
for (int liar : statements.get(employee)) {
isLiar[liar] = true;
dfs(liar, statements, visited, isLiar);
}
}
}
}
결론
본문에서는 ‘거짓말쟁이가 되긴 싫어’라는 주제로 문제를 정의하고,
그 문제를 해결하기 위한 알고리즘을 단계별로 설명했습니다.
직원들의 주장에 대한 정보를 활용해 누가 거짓말을 했는지를 분석하고,
그 결과를 통해 거짓말을 가장 많이 한 직원을 알아낼 수 있습니다.
이 과정을 통해 코딩테스트 준비와 알고리즘 문제 해결 능력을 향상시킬 수 있습니다.