[BOJ][C++] 백준 1411번 비슷한 단어
Updated:
1411번 비슷한 단어
1. 문제 정보
백준 온라인 저지 [1411번 비슷한 단어] 문제의 링크입니다.
문제
만약 어떤 단어A를 숌스럽게 바꿔서 또다른 단어 B로 만든다면, 그 단어는 비슷한 단어라고 한다.
어떤 단어를 숌스럽게 바꾼다는 말은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다는 소리다. 그리고, 단어에 등장하는 알파벳의 순서는 바뀌지 않는다. 두 개의 다른 알파벳을 하나의 알파벳으로 바꿀 수 없지만, 자기 자신으로 바꾸는 것은 가능하다.
예를 들어, 단어 abca와 zbxz는 비슷하다. 그 이유는 a를 z로 바꾸고, b는 그대로 b, c를 x로 바꾸면, abca가 zbxz가된다.
단어가 여러 개 주어졌을 때, 몇 개의 쌍이 비슷한지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 각각의 단어는 모두 다르다.
출력
첫째 줄에 총 몇 개의 쌍이 비슷한지 출력한다.
예제 입력1
5
aa
ab
bb
cc
cd
예제 출력1
4
시간 / 메모리 제한
2초 / 128MB
2. 생각
1.다른 분의 코드를 참고하여 어렵게 푼 문제였습니다. 하지만 방법을 알고 나면 어렵지 않습니다.
- 비슷한 단어의 쌍을 찾는 문제입니다. 문자를 바꿀 때 어떤 문자로 바꾸었는지 표시해두는 방법을 사용합니다. 만약 0이라면 문자를 바꾸지 않았다는 뜻이고, 다른 숫자라면 그 숫자에 해당하는 문자로 바꾼 것입니다.
ex1) 비슷한 단어인 경우 abca - zbxz
k=1 2 3 4 word[i] a b c a word[j] z b x z 1) k=1일 때, 비교 문자는 a와 z입니다.
1 2 3 … 24 25 26 visited1 0 -> 26 0 0 … 0 0 0 visited2 0 0 0 … 0 0 0 -> 1 k=2일 때, 비교 문자는 b와 b입니다.
1 2 3 … 24 25 26 visited1 26 0 -> 2 0 … 0 0 0 visited2 0 0 -> 2 0 … 0 0 1 k=3일 때, 비교 문자는 c와 x입니다.
1 2 3 … 24 25 26 visited1 26 2 0 -> 24 … 0 0 0 visited2 0 2 0 … 0 -> 3 0 1 k=4일 때, 비교문자는 a와 z입니다.
1 2 3 … 24 25 26 visited1 26 2 24 … 0 0 0 visited2 0 2 0 … 3 0 1
- visited[1]이 0이 아니고 이미 z로 바꿨다는 표시(26)가 있습니다.
- 이미 바꾼 값이(z) 지금 바꾸려고 하는 값(z)와 같기 때문에 문제 없습니다.
따라서, 단어 abca와 zbxz는 비슷한 단어입니다.
ex2) 비슷한 단어가 아닌 경우 aa - ab
k=1 2 word[i] a a word[j] a b k=1일 때, 비교 문자는 a와 a입니다.
1 2 … 26 visited1 0 -> 1 0 … 0 visited2 0 -> 1 0 … 0 k=2일 때, 비교문자는 a와 b입니다.
1 2 … 26 visited1 1 0 … 0 visited2 1 0 … 0
- visited[1]이 0이 아니고 이미 a로 바꿨다는 표시(1)가 있습니다.
- 이미 바꾼 값이(a) 지금 바꾸려고 하는 값(b)와 같지 않기 때문에 이 경우 비슷한 단어가 아닙니다.
따라서 단어 aa와 단어 ab는 비슷한 문자열이 아닙니다.
3. 소스코드 (C++)
