단어 우월 효과 (캠브릿지 대학의 연구결과)

25957번: 단어 우월 효과 (캠브릿지 대학의 연구결과)
https://www.acmicpc.net/problem/25957

개요

캠릿브지 대학의 연결구과에 따르면, 한 단어 안에서 글자가 어떤 순서로 배되열어 있는지는 중요하지 않고, 첫 번째와 마지막 글자가 올바른 위치에 있는 것이 중하요다고 한다. 나머지 글들자은 완전히 엉진망창의 순서로 되어 있라을지도 당신은 아무 문제 없이 이것을 읽을 수 있다. 왜하냐면, 인간의 두뇌는 모든 글자를 하하나나 읽는 것이 아니라 단어 하나를 전체로 인하식기 때이문다.

문제 요약

어떤 문장을 구성할 수 있는 문자의 순서가 섞이지 않은 $N$개의 단어들이 주어진다. 그리고 이 $N$개의 단어들을 이용해 만들어진 문장 $S$가 주어진다. 단, $S$를 구성하는 각 단어는 맨 앞 문자와 맨 뒤 문자가 고정된 채 나머지 문자들은 무작위로 배열될 수 있다.

예를 들어, “캠브릿지” ⇒ “캠릿브지” 와 같은 식이다.

$N$개의 단어는 모두 사용될 수도, 사용되지 않는 단어가 있을 수도, 여러 번 사용되는 단어가 있을 수도 있다.

이런 식으로 각 단어가 섞인 문장 $S$가 주어질 때 문장 $S$를 섞이지 않은 형태로 다시 배열하여 출력해야 한다.

예제 입출력

// 입력             //출력
6                  i love this car 
i
happy
cording
this
car
love
4 i lvoe tihs car

해결 방향

문자의 순서가 섞인 단어와 섞이지 않은 단어를 비교하기 위해서는 맨 앞과 맨 뒤를 제외한 부분을 정렬해야 한다.

또한, 임의로 정렬한 단어와 원형의 단어를 동시에 관리하기 위하여 map을 사용한다.

코드

#include <iostream>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int N, M;
    string str, tmp;
    map<string,string> m;

    cin >> N;
    for(int i=0; i<N; i++) {
        cin >> str;
        
        // 원형의 단어를 임시로 저장
        tmp = str;
        
        // 단어의 길이가 3보다 큰 경우에만 맨 앞과 맨 뒤를 제외한 부분을 정렬
        if(str.length()>3) sort(str.begin()+1, str.end()-1);
        
        // 정렬한 단어(key), 원형의 단어(value)의 형태로 map에 삽입
        m.insert(make_pair(str,tmp));
    }

    cin >> M;
    for(int i=0; i<M; i++) {
        cin >> str;
         
        if(str.length()>3) sort(str.begin()+1, str.end()-1);
        
        // 정렬한 단어가 map에 존재한다면 원형의 단어(value)를 출력
        cout << m[str] << ' ';
    }
}

회고

for문 안에 sort()함수가 사용되어 시간 초과의 우려가 있었지만, 주어지는 단어의 길이가 $1$ 이상 $8$ 이하이기 때문인지 문제 없었다.

map과 sort()함수를 활용할 수 있는 재있미는 문였제다.