문제 출처 : https://www.acmicpc.net/problem/1411
[1411번: 비슷한 단어
첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복
www.acmicpc.net](https://www.acmicpc.net/problem/1411)
문제
만약 어떤 단어A를 숌스럽게 바꿔서 또다른 단어 B로 만든다면, 그 단어는 비슷한 단어라고 한다.
어떤 단어를 숌스럽게 바꾼다는 말은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다는 소리다. 그리고, 단어에 등장하는 알파벳의 순서는 바뀌지 않는다. 두 개의 다른 알파벳을 하나의 알파벳으로 바꿀 수 없고, 임의의 알파벳을 자기 자신으로 바꾸는 것은 가능하다.
예를 들어, 단어 abca와 zbxz는 비슷하다. 그 이유는 a를 z로 바꾸고, b는 그대로 b, c를 x로 바꾸면, abca가 zbxz가된다.
단어가 여러 개 주어졌을 때, 몇 개의 쌍이 비슷한지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복되지 않는다. 또, 알파벳 소문자로만 이루어져 있다.
출력
첫째 줄에 총 몇 개의 쌍이 비슷한지 출력한다.
문제 풀이
import sys
import math
replace_word = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
n = int(sys.stdin.readline())
s_dict = {}
for _ in range(n):
count = 0
s = sys.stdin.readline().rstrip()
for i in range(len(s)):
if s[i].isupper():
continue
s = s.replace(s[i],replace_word[count])
count+=1
if s not in s_dict:
s_dict[s] = 1
else:
s_dict[s] +=1
result = 0
for v in s_dict.values():
result += math.comb(v,2)
print(result)
문자열의 형태가 같은 쌍의 개수를 찾아내는 문제이다.
문제에서 알파벳 소문자로만 구성되어있다고 하였으므로, 이를 알파벳 대문자로 바꾸어 동일한 형태를 찾아 문제를 해결하였다.
예를 들어, xyxz, abad, efeg 의 경우 ABAC의 동일한 형태이므로 비슷한 단어임을 알 수 있다.
여기서 xyxz - abad, xyxz - efeg, abad - efeg 총 3개의 쌍이 나오게 된다.
쌍의 개수를 구하기 위하여 조합(Combination)을 이용하였고, n개의 같은 형태의 단어들의 쌍의 개수를 구하기 위하여 nC2를 구해주었다.
최종적으로 구한 모든 쌍들의 수를 더하고 출력하면 된다.
'Koala - 11기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/Python] N과 M (백트레킹) (0) | 2023.07.16 |
---|---|
[백준/Python] 1476번 날짜 계산 (0) | 2023.07.16 |
[백준 C++] 1065 : 한수 (0) | 2023.07.16 |
[백준/Python] 2661 좋은수열 (0) | 2023.07.16 |
[백준/C++] 1182번 부분수열의 합 (0) | 2023.07.16 |