[백준] 9933번 C/C++ 풀이 _ 민균이의 비밀번호

 

출처 : https://www.acmicpc.net/problem/9933 

시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초128 MB39051201100831.382%

문제

창영이는 민균이의 컴퓨터를 해킹해 텍스트 파일 하나를 자신의 메일로 전송했다. 파일에는 단어가 한 줄에 하나씩 적혀있었고, 이 중 하나는 민균이가 온라인 저지에서 사용하는 비밀번호이다.

파일을 살펴보던 창영이는 모든 단어의 길이가 홀수라는 사실을 알아내었다. 그리고 언젠가 민균이가 이 목록에 대해서 얘기했던 것을 생각해냈다. 민균이의 비밀번호는 목록에 포함되어 있으며, 비밀번호를 뒤집어서 쓴 문자열도 포함되어 있다.

예를 들어, 민균이의 비밀번호가 "tulipan"인 경우에 목록에는 "napilut"도 존재해야 한다. 알 수 없는 이유에 의해 모두 비밀번호로 사용 가능하다고 한다.

민균이의 파일에 적혀있는 단어가 모두 주어졌을 때, 비밀번호의 길이와 가운데 글자를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 수 N (2 ≤ N ≤ 100)이 주어진다. 다음 N개 줄에는 파일에 적혀있는 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있으며, 길이는 2보다 크고 14보다 작은 홀수이다.

출력

첫째 줄에 비밀번호의 길이와 가운데 글자를 출력한다. 항상 답이 유일한 경우만 입력으로 주어진다.

예제 입력 1 

4
las
god
psala
sal

예제 출력 1 

3 a

출처

Contest Croatian Open Competition in Informatics COCI 2013/2014 Contest #5 1번

알고리즘 분류

풀이

map 을 이용하여 문제를 해결했습니다.
이 문제는 쉽지만 비밀번호가 앞뒤가 똑같은 펠린드롬으로 구성되어있을 경우에, 
하나만 들어와도 비밀번호인 것을 알아내는 것만 처리해주면 간단합니다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
using namespace std;
 
int main() {
    int N; cin >> N;
    set<string> str_set;
    for (int idx = 0; idx < N; idx++) {
        string sub; cin >> sub;
        // 만약, 찾는 얘가 없으면 
        if (str_set.find(sub) == str_set.end()) { 
            str_set.insert(sub);  
            reverse(sub.begin(), sub.end());
            // 팰린드롬이면 종료
            if (str_set.find(sub) != str_set.end()) {
                cout << sub.size() << " " << sub[sub.size() / 2];
                return 0;
            }
            str_set.insert(sub); 
        // 이미 저장된 값이라면 
        } else {
            cout << sub.size() << " " << sub[sub.size()/2]; 
            return 0
        }
    }
    return 0
}
cs