C++ 코딩테스트 강좌, 거짓말쟁이가 되긴 싫어

1. 문제 설명

여러분은 한 거짓말쟁이 마을의 주민입니다. 이 마을에서는 매일 저녁마다 사람들이 모여 이야기를 나누고, 가끔씩 서로의 이야기 중에서 진짜와 거짓을 가려내는 게임을 합니다. 마을 사람들은 검증할 수 있는 사항을 가지고 있습니다. 예를 들어, A라는 사람이 B라는 사람이 오늘 저녁 식사를 함께 했다고 주장할 때, 이를 확인할 수 있는 방법이 있습니다.

게임의 목적은 누가 진실을 말하고 있는지, 누가 거짓말을 하고 있는지를 판별하는 것입니다. 하지만 오늘은 마을의 주민들 중 일부가 거짓말을 하고 있다고 합니다. 여러분은 이 주민들의 진실과 거짓은 얼마나 유의미한지 판단하고, 그들의 말을 기반으로 다른 사람의 거짓말도 확인해야 합니다.

2. 문제 정의

이 문제를 다루기 위해서는 다음과 같은 정보를 필요로 합니다:

n: 마을 주민의 수 (1 ≤ n ≤ 100)
input: 각 주민이 내놓은 이야기
output: 진실을 말하는 주민의 수

각 주민은 자신이 알고 있는 진실을 바탕으로 이야기를 하며, 누가 거짓말을 하는지를 확인해야 합니다. 여러분은 진실을 이야기한 사람들을 최대한 많은 수를 찾아야 합니다.

3. 입력 예시

3
A가 B와 저녁을 먹었다.
B가 C와 저녁을 먹었다.
C가 A와 저녁을 먹었다.

4. 출력 예시

3 (모든 주민이 서로 저녁을 먹었다고 주장함)

5. 접근 방법

이 문제를 해결하기 위한 접근 방법은 다음과 같습니다:

학생들의 이야기를 저장하기 위한 자료구조 준비: 주민과 그의 주장을 키-값 쌍으로 저장하는 맵이나 다차원 배열을 사용할 수 있습니다.
이야기의 일관성을 검증: 각 주민의 주장과 관련된 다른 주민들의 주장과의 연관성을 분석하며, 공통점과 모순점을 찾아야 합니다.
최대 여부 판단: 가장 많은 주민이 서로의 이야기를 지지하는 경우에 해당하는 주민을 찾습니다.
결과 출력: 최종적으로 진실을 말한 주민의 수를 출력합니다.

6. C++ 구현

위의 접근 방법을 바탕으로 구체적인 C++ 구현을 아래와 같이 진행할 수 있습니다.

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <set>

using namespace std;

int main() {
    int n;
    cout << "주민의 수를 입력하세요: ";
    cin >> n;

    unordered_map<string, set<string>> claims;
    string person, claimsPerson;

    for (int i = 0; i < n; ++i) {
        cout << "주장의 내용을 입력하세요: ";
        cin >> person >> claimsPerson;
        claims[person].insert(claimsPerson);
    }

    // 진실을 확인하는 과정 (생략)
    // 결과를 출력합니다.
    int truthful = 0; // 진실을 말하는 주민의 수

    // 여기서 claims를 기반으로 진실을 판단합니다.
    // ...

    cout << "진실을 말한 주민의 수: " << truthful << endl;
    return 0;
}

7. 코드 설명

위 코드에서 우리는 유저로부터 주민 수와 서로의 주장에 대한 정보를 입력받습니다. 먼저 주민의 주장을 unordered_map을 사용하여 저장하고, 이후 이 정보를 가지고 누가 진실을 말하고 있는지를 판단합니다.

8. 코드의 확장성

이 코드는 주민의 주장 수에 따라 반복적으로 확장할 수 있습니다. 만약 주민 수가 증가한다면, 적절한 데이터 구조를 통해 이 주장들을 보다 효율적으로 전달하고 검증할 수 있습니다.

9. 최적화 및 추가 아이디어

문제의 복잡도를 줄이기 위한 추가적인 최적화 접근법으로는 다음을 고려해볼 수 있습니다:

조건부 분기 처리: 주민 각각의 주장에 따라 처리해야 할 경우, 특정 조건에 따라 처리를 분기할 수 있습니다.
DFS 또는 BFS 방식: 그래프 탐색 알고리즘을 이용하여 서로 연결된 주민들 간의 관계를 탐색함으로써 진실을 말하는 가능성을 높일 수 있습니다.
거짓말 판단 기준 확립: 쉽게 판단할 수 있는 기준을 정해 진실을 일괄적으로 평가할 수 있게 하면 복잡도를 낮출 수 있습니다.

10. 결론

이 문제는 알고리즘적 사고 방식을 요구하는 흥미로운 문제입니다. 이를 통해 여러분은 데이터 처리 및 판단에 대한 몇 가지 중요한 원칙을 배우게 될 것입니다. 이러한 문제는 프로그래밍 인터뷰에서 매우 자주 발생하며, 기본적으로 자신이 알고 있는 개념을 바탕으로 문제를 풀 수 있는 능력을 요구합니다.

마지막으로, 코딩 테스트 준비에 있어서는 다양한 유형의 문제를 접해보는 것이 중요합니다. 이러한 문제들을 많이 해결하다 보면 자연스럽게 알고리즘적 능력이 향상되는 것을 느낄 수 있을 것입니다. 여러분의 성공적인 코딩 테스트 준비를 기원합니다.