[2204번] 도비의 난독증 테스트

문제 출처 :

https://www.acmicpc.net/problem/2204

알고리즘 분석 :

문제 해결에 필요한 사항

1. string

2. 문자열 처리

이 문제는 한글 번역본 말고 원문으로 문제를 풀기를 적극 추천한다.

문제를 보고 너무 많이 햇갈렸다.

이문제를 한글본으로 보고 bbb와 bbBb중 어느 단어가 사전순으로 앞서냐 물으면

bbb라고 말하는사람도 있을거고 bbBb라고 말하는 사람도 있을 것이다.

예를 들어, apPle은 Bat보다 앞서지만 AnT보다는 뒤에 있는 단어다.

위의 힌트 때문에 그렇다.

a와 A를 보고 '대문자 A가 소문자 a보다는 앞서는구나 -> 아 같은 문자일 경우 대문자는 소문자보다 앞서는구나'라고 될 수 있기 때문이다.

원문을 보면 '대문자 소문자를 무시한다.'라고 한다.

이제 이문제를 풀기 위해서는 그냥 입력받은 string을 소문자로 변환하고 비교한 뒤 사전순으로 앞서는 문자를 찾아내서 원래 문자를 출력하면 된다.

어렵지 않은 문제지만 한글이 더 어려운 적은 처음인 듯 하다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
 
using namespace std;
 
int map[600];
 
int compStr(string str, string tmp)
{
    int len;
    
    if (str.size() > tmp.size())
        len = tmp.size();
    else
        len = str.size();
    
    bool chk = true;
    int ret = 0; // 1이면 str이 사전상 앞, 2면 tmp가 사전상 앞, 3이면 둘다 같다.
 
    for (int i = 0; i < len; i++)
    {
        int s = map[str[i]];
        int t = map[tmp[i]];
        
        if (s == t)
            continue;
        else
        {
            if (s < t)
                ret = 1;
            else
                ret = 2;
 
            chk = false;
            break;
        }
    }
 
    // 위의 방식에서 끝을 못봤다면
    // 즉, 둘다 계속 같은 문자였다면 길이가 결국 긴 단어가 사전상 뒤
    if (chk)
    {
        if (str.size() > tmp.size())
            ret = 2;
        else if (str.size() == tmp.size())
            ret = 3;
        else
            ret = 1;
    }
 
    return ret;
}
 
int main()
{
    for (int i = 'a', val = 2; i <= 'z'; i++, val += 2)
        map[i] = val;
 
    while (1)
    {
        int n;
        scanf("%d", &n);
 
        if (!n)
            break;
 
        string str;
        cin >> str;
        
        for (int i = 1; i < n; i++)
        {
            // t에 str을 넣어두고 str을 소문자로 초기화
            string t = str;
            str.clear();
            for (int i = 0; i < t.size(); i++)
                str += tolower(t[i]);
 
            string tmp;
            cin >> tmp;
 
            // tt에 tmp를 넣어두고 tmp를 소문자로 초기화
            string tt = tmp;
            tmp.clear();
            for (int i = 0; i < tt.size(); i++)
                tmp += tolower(tt[i]);
 
            // 소문자로 다 변한 str과 tmp 비교
            int get = compStr(str, tmp);
 
            if (get == 2)
                str = tt;
            else
                str = t;
        }
 
        cout << str << endl;
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>