[백준 BOJ] 16499번 동일한 단어 그룹화하기 (C++/cpp)

문제 설명

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

 

 

접근 방법 - 기초적인 문자열 정렬 문제

백준의 16499번 문제는 문자열에 대한 문자 정렬을 통하여 비교적 쉽게 해결할 수 있는 문제이다.

해당 문제는, 문자 구성은 같으나 순서만 다른 단어들을 하나의 그룹으로 묶을 때, 입력으로 주어지는 단어들에 대하여 그룹의 개수를 구하여 출력하면 되는 문제이다.

 

필자는 문제의 설명을 통하여, 단어를 구성하는 문자들을 알파벳 순으로 정렬하여 재구성하였을 때 같은 결과가 나오는 단어들을 하나의 그룹으로 취급하는 식으로 문제를 해결해보려 하였다.

이에 대해 좀 더 쉽게 이야기하기 위해, 문제에 제시된 예제 입력 1에 빗대어 설명을 추가해 본다.

(입력으로 주어진 4개의 단어)
cat, dog, god, tca

(각 단어들을, 알파벳 순으로 문자를 각각 재구성하면 아래와 같다.)
act, dgo, dgo, act

(정렬 결과가 같은 단어들끼리 묶으면 아래와 같다.)
{act(cat), act(tca)}, {dgo(dog), dgo(god)}

=> 2개의 그룹으로 나뉘기 때문에, 정답은 2라고 할 수 있다.

필자는 위와 같은 원리로 코드를 작성해 보았고, 이를 통해 문제를 해결할 수 있었다.

자세한 설명은 아래에 기재해 놓으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 주어지는 단어들을 저장할 문자열 배열 str을 전역 변수로 미리 선언해 둔다.

 

2) 입력받을 단어의 개수(n)를 입력받는다.

 

3) n의 크기만큼 반복문을 수행하여 단어를 하나씩 입력받고, 이를 배열 str에 저장한다. 

이때, 입력받은 문자열의 문자들을 알파벳 순으로 정렬하여 재구성한 결과를 str에 저장하도록 한다.

 

4) str에 저장된 단어들 간, 값 비교를 수행한다.

이때 동일한 문자열 값이 확인된다면, 원래의 이 2개의 단어는 동일한 그룹에 속한다는 점을 뜻한다.

필자는, 둘 중 하나의 문자열을 빈 값("")으로 저장하도록 하였다.

(중복되는 값들을 소거하여 하나의 값만 남긴 뒤에, 이를 통하여 그룹의 개수를 카운팅 하려 한다.)

 

5) 그룹의 개수를 카운팅 할 cnt를 0으로 초기화하여 선언해 둔다.

 

6) 반복문을 통하여 str 배열의 값들을 하나씩 탐색해 본다.

이때 빈 값("")이 아닌 값을 만난다면, 이는 새로운 그룹임을 의미하기 때문에 cnt에 1을 더해준다.

 

7) 위 연산이 모두 종료되었다면, 최종적으로 저장된 cnt를 출력한 뒤 실행 종료한다.

반응형

(사실 map 자료구조를 알고 있다면 보다 쉽게 해결할 수 있다.

당시에는 map을 몰라서 사용하지 못했던 것이니 참고하길 바란다..;;)

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 16499번 코드
string str[101];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> str[i];
		sort(str[i].begin(), str[i].end());
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (str[i] == str[j]) {
				str[j] = "";
			}
		}
	}

	int cnt = 0;
	for (int i = 0; i < n; i++) {
		if (str[i] != "") {
			cnt++;
		}
	}
	cout << cnt << endl;
}

 

제출 결과

(2022.10.12 백준 16499번 문제 제출 결과)