본문 바로가기

BAEKJOON/자료 구조

백준 25957번 [단어 우월 효과 (캠브릿지 대학의 연구결과)](C++) -yes6686- 티스토리

728x90
SMALL

백준 문제 풀이: 25957 (단어 우월 효과 - 캠브릿지 대학의 연구결과)


문제 링크: https://www.acmicpc.net/problem/25957

문제 설명:

단어의 순서를 바꿔도 첫 글자와 마지막 글자가 같다면 사람이 이해할 수 있다는 연구결과를 기반으로: 1. 주어진 단어의 첫 글자와 마지막 글자를 기억합니다. 2. 단어를 알파벳 순으로 정렬한 후 첫 글자와 마지막 글자를 기준으로 단어를 저장합니다. 3. 주어진 여러 단어에 대해 원래 단어를 출력해야 합니다.


문제 해결 코드


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

string s[200001]; // 단어를 저장할 배열
map<pair<string, string>, string> mp; // 첫, 마지막 글자와 정렬된 문자열을 키로 하는 맵

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int n; // 저장할 단어의 개수
    cin >> n;
    for (int i = 0; i < n; i++) {
        string s; 
        cin >> s;

        string k = s; // 단어 복사본
        string se = "";
        se += s[0]; // 첫 글자 저장
        se += s[s.size() - 1]; // 마지막 글자 저장

        sort(k.begin(), k.end()); // 단어 정렬
        mp[{se, k}] = s; // (첫글자+마지막글자, 정렬된 문자열)를 키로 원래 단어 저장
    }

    int m; // 테스트 단어 개수
    cin >> m;
    for (int i = 0; i < m; i++) {
        string s;
        cin >> s;

        string k = s; // 단어 복사본
        string se = "";
        se += s[0]; // 첫 글자
        se += s[s.size() - 1]; // 마지막 글자

        sort(k.begin(), k.end()); // 단어 정렬
        cout << mp[{se, k}] << ' '; // 원래 단어 출력
    }

    return 0;
}

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명:

  • 단어 저장 과정: - 각 단어의 첫 글자와 마지막 글자를 **키로 사용**합니다. - 단어를 알파벳 순으로 정렬한 문자열도 키에 포함됩니다. - 이를 **map**에 저장합니다: mp[{se, k}] = s.
  • 단어 찾기: - 주어진 단어의 첫 글자와 마지막 글자를 구합니다. - 단어를 정렬한 후, map에서 원래 단어를 찾아 출력합니다.

입출력 예시

  • 입력 예시:
    4  
    hello  
    world  
    cambridge  
    university  
    3  
    hlelo  
    wolrd  
    cnabrigde
  • 출력 예시:
    hello world cambridge

시간 복잡도 분석

  • **단어 저장:** 단어 하나를 정렬하는 데 O(L log L)가 소요됩니다. 여기서 L은 단어의 길이입니다.
  • **단어 찾기:** map을 사용하므로 키를 찾는 시간 복잡도는 O(log N)입니다.
  • **총 시간 복잡도:** - 단어 N개를 처리하는 데 O(N ⋅ L log L) - 테스트 단어 M개를 조회하는 데 O(M ⋅ L log L) 따라서 총 시간 복잡도는 **O((N + M) ⋅ L log L)**입니다.

결과

주어진 조건에 따라 원래 단어를 정확히 출력합니다.

  • 정렬과 키-값 매핑을 사용해 단어를 효과적으로 저장하고 조회합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!

728x90
LIST