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
'BAEKJOON > 자료 구조' 카테고리의 다른 글
백준 14427번 [수열과 쿼리 15](C++) -yes6686- 티스토리 (0) | 2024.08.17 |
---|---|
백준 27497번 [알파벳 블록](C++) -yes6686- 티스토리 (0) | 2024.07.13 |
백준 2295번 [세 수의 합](C++) -yes6686- 티스토리 (0) | 2024.05.10 |
백준 23757번 [아이들과 선물 상자](C++) -yes6686- 티스토리 (0) | 2024.05.07 |
백준 1406번 [에디터](C++)-yes6686- 티스토리 (0) | 2024.01.18 |