백준 1411 비슷한 단어 Kotlin (완전 탐색)

문제 출처 : https://www.acmicpc.net/problem/1411

1411번: 비슷한 단어

문제

만약 어떤 단어A를 숌스럽게 바꿔서 또다른 단어 B로 만든다면, 그 단어는 비슷한 단어라고 한다.

어떤 단어를 숌스럽게 바꾼다는 말은 단어 A에 등장하는 모든 알파벳을 다른 알파벳으로 바꾼다는 소리다. 그리고, 단어에 등장하는 알파벳의 순서는 바뀌지 않는다. 두 개의 다른 알파벳을 하나의 알파벳으로 바꿀 수 없지만, 자기 자신으로 바꾸는 것은 가능하다.

예를 들어, 단어 abca와 zbxz는 비슷하다. 그 이유는 a를 z로 바꾸고, b는 그대로 b, c를 x로 바꾸면, abca가 zbxz가된다.

단어가 여러 개 주어졌을 때, 몇 개의 쌍이 비슷한지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에 한 줄에 하나씩 단어가 주어진다. 단어의 길이는 최대 50이고, N은 100보다 작거나 같은 자연수이다. 모든 단어의 길이는 같고, 중복되지 않는다. 또, 알파벳 소문자로만 이루어져 있다.

출력

첫째 줄에 총 몇 개의 쌍이 비슷한지 출력한다.

알고리즘 분류

• 구현
• 문자열
• 브루트포스 알고리즘

풀이

완전 탐색 문제이다.

O(n*n*len)으로 풀 수 있는데 풀이는 다음과 같다.

우선 예시를 보면,  ab와 bb는 짝이될 수 없다.

a는 b로 매칭할 수 있다.

b는 이미 b가 a와 매칭되어있으므로 매칭할 수 없다.

abca와 opqr도 짝이될 수 없다.

a는 o와 매칭

b는 p와 매칭

c는 q와 매칭

마지막 a는 이미 o와 매칭되어있기 때문에 r과 매칭할 수 없다.

그럼 어떻게 이를 검사할 수 있을까

visited1[26], vsisited2[26] 배열을 두고,

visited1 배열엔 첫 번째 문자열의 문자와 매칭된 두 번째 문자열의 문자를 저장

visited2 배열엔 두 번째 문자열의 문자와 매칭된 첫 번째 문자열의 문자를 저장한다.

이후 visited1 배열에서 현재 문자가 아직 매칭이 안 된 경우, 매칭할 문자가 다른 문자랑 매칭되어있다면 짝이 될 수 없고, visited1 배열에서 현재 문자가 매칭이 이미 된 경우, 매칭할 문자가 이미 매칭한 문자와 같지 않다면 짝이 될 수 없다.

 

 

코드

val br = System.`in`.bufferedReader()

fun main() = with(System.out.bufferedWriter()) {
    val n = br.readLine().toInt()
    val input = Array<String>(n){""}
    for(i in 0 until n){
        input[i] =br.readLine()
    }

    var answer=0
    for(i in 0 until n){
        for(j in i+1 until n){
            answer+=canPair(input[i],input[j],IntArray(26){-1}, IntArray(26){-1})
        }
    }
    write("$answer")

    close()
}

fun canPair(a : String, b : String,visited1 : IntArray ,visited2 : IntArray) : Int {
    val left = a.toCharArray()
    val right = b.toCharArray()

    for(i in left.indices){
        if(visited1[left[i]-'a']==-1){
            if(visited2[right[i]-'a']!=-1)
                return 0
            visited1[left[i]-'a'] = right[i]-'a'
            visited2[right[i]-'a'] = left[i]-'a'

        }else{
            if(visited1[left[i]-'a']!=right[i]-'a'){
                return 0
            }
        }
    }
    return 1

}