Menu

문서정보

같은 형태의 문자열 가려내기

길이가 같은 두 개의 문자열 ST가 있다. 이들이 같은 형태의 문자열인지를 판단하라. 같은 형태란 S에 있는 문자를 다른 문자로 치환해서 T와 같아지걸 의미한다.

예제.

풀이

아래와 같은 방식으로 풀었다.
  1. 문자열 S를 순환한다. 인덱스 변수로 "i"를 사용한다.
  2. S[i]와 T[i]가 서로 다르다면
  3. S[i]를 T[i]로 바꾼다. 이때 S[i:]를 순환하면서 S[i]를 모두 T[i]로 바꾼다.
  4. 값을 바꿀 때, 이미 변환 된 문자인지를 map에서 확인한다.
  5. 값을 바꿀 때, 값의 패턴이 틀리면 false를 반환한다. S="foolo", T="brrpd"라고 가정해 보자. s의 모든 o는 r로 변환한다. 그런데 s의 마지막 o는 r이 아닌 d다. Replace 규칙에 어긋 나므로 이 문자열은 Unisomorphic 하다는 것을 알 수 있다.
  6. 값을 바꿨다면, 이 정보는 map 타입으로 기록 한다.
package main

import (
    "fmt"
)

type isomorphic struct {
    Source []byte
    Target []byte
    cMap   map[byte]byte
    Index  int
}

func (i *isomorphic) Test() bool {
    i.cMap = make(map[byte]byte)
    if len(i.Source) != len(i.Target) {
        return false
    }
    for i.Index = 0; i.Index < len(i.Source); i.Index++ {
        s := i.Source[i.Index]
        t := i.Target[i.Index]
        if !i.Replace() {
            return false
        }
        if s == t {
            continue
        } else {
            if _, ok := i.cMap[t]; ok {
                return false
            }
        }

        i.cMap[t] = s
    }
    return true
}

func (i *isomorphic) Replace() bool {
    s := i.Source[i.Index]
    t := i.Target[i.Index]
    for idx := i.Index; idx < len(i.Source); idx++ {
        if i.Source[idx] == s {
            if i.Target[idx] == t {
                i.Source[idx] = i.Target[i.Index]
            } else {
                return false
            }
        }
    }
    return true
}

func main() {
    s := []byte("foolo")
    t := []byte("brrpd")
    org := string(s)
    iso := isomorphic{Source: s, Target: t}
    if iso.Test() {
        fmt.Println(string(org), " isomorphic ", string(t))
    } else {
        fmt.Println(string(org), " unisomorphic ", string(t))
    }
}

		

풀이과정 회고

문자를 치환하면 간단할 것 같지만 1. 문자의 연속된 패턴, 2. 문자의 비연속적인 패턴을 감안해야 하므로 치환만으로는 풀 수 없다. 단순 치환은 패턴에 대한 상태 정보를 유지하거나 혹은 판단 할 수 없기 때문이다. 따라서 치환과 함께 패턴을 어떻게 처리 할 것인지에 대한 방법을 찾아야 한다. 나는 S 배열의 맨 앞부터 시작해서 패턴이 T와 일치하는 지를 확인하는 방식을 사용하기로 했다. 중간에 패턴이 어긋 나면 즉시 false를 반환한다.

 Isomorphic String

위의 과정을 코드로 만들면 된다. 하지만 예외 사항이 있을 수 있다. 아래의 예를 보자.

 Isomorphic 실패 예

s -> o의 규칙을 가진다. 4번 인덱스를 보면 o가 있지만, 이미 s -> o 라는 규칙이 있고 반드시 1:1이어야 하므로 j -> o는 허용 될 수가 없다. 따라서 문자열 S는 무조건 Unisomorphic 하다. 문자열을 순환하면서 치환하는 중에 변환 규칙을 검사해서 어긋 나는게 있다면 바로 false를 반환하면 된다. func (i *isomorphic) Replace() 메서드가 bool을 리턴하는 이유다.

더 이상의 예외 사항은 없을까 ? 알고리즘 해법을 찾는데 중요한 이슈다. 가능한 패턴을 하나하나 만들어 보면서 테스트하는 방법이 있을 것이다. 하지만 이 방법은 너무 비효율 적이다. 어떻게 해야 일일이 패턴을 만들지 않고, 가능한 예외들에 대한 검증이 충분하다는 걸 확인 할 수 있을 까 ?