[BOJ-16499][C++] 동일한 단어 그룹화하기

문제

소문자로 이루어진 단어 N개가 주어졌을 때, 단어가 총 최소 몇 개의 그룹으로 이루어져 있는지 구하는 프로그램을 작성하시오.

그룹에 속한 단어는 모두 같은 알파벳으로 이루어져 있어야 하고, 개수도 같아야 한다. 즉, 단어를 구성하는 알파벳의 순서만 달라야 한다.

 

입력

첫째 줄에 단어의 개수 N이 주어진다. (2 ≤ N ≤ 100) 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 소문자로만 이루어져 있고, 길이는 10을 넘지 않는다.

 

출력

첫째 줄에 그룹의 최소 개수를 출력한다.

 

예제 입력 1

4
cat
dog
god
tca

 

예제 출력 1

2

 

예제 입력 2 

2
a
a

 

예제 출력 2 

1

 

출처

University > 한양대학교 ERICA 캠퍼스 > 2018 ERICA Software-Up Programming Contest League B A번

 

알고리즘 분류

• 자료 구조
• 문자열
• 정렬
• 해시를 사용한 집합과 맵

 

문제 출처

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

16499번: 동일한 단어 그룹화하기

 

---

 

문제 해결 방법

• 맵과 정렬을 이용하여 쉽게 풀 수 있었던 문제였다.
• 맵의 특성(중복 불허용, 참조하기만 해도 요소 생성)을 잘 알면 쉽게 풀 수 있었던 문제였다.
• 입력 받은 문자열들을 @sort()@ 함수를 이용하여 오름차순 정렬을 수행하는 동시에 참조하는 방식으로 맵에 하나하나씩 넣으면, 중복되지 않은 문자열만 맵에 남아있게 된다.
• 최종적으로 맵의 요소 개수(@m.count()@)를 출력해주면 된다.

 

코드

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

int N;
string words[100];
map<string, int> m;

void Input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> words[i];
    }
}

int Solution() {
    for (int i = 0; i < N; i++) {
        sort(words[i].begin(), words[i].end());   // 오름차순 정렬
        m[words[i]];    // 맵에 넣기
    }

    return m.size();
}

void Output() {
    cout << Solution() << '\n';
}

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

    Input();
    Output();

    return 0;
}

 

채점 결과

 

참고

• 실버IV