Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>

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

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

예제.
  • "egg"와 "add"는 true를 반환한다. e를 a로 g를 d로 치환하면 add가 되기 때문이다.
  • "foo"와 "bar"는 false를 반환한다.
  • "paper"과 "title"는 true를 반환한다.

풀이

아래와 같은 방식으로 풀었다.
  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

  • 0번 index부터 순환한다. f를 b로 변환한다. 무조건 성공 할 것이다.
  • 1번 index에서 o를 s로 변환한다. 이때 모든 o를 s로 변환한다.
  • 2번 index의 경우 두 값이 모두 s이므로 건너뛴다.
  • 3번 index는 l을 p로 변환한다. map에 p가 없으므로 이 변환은 참이다.
  • 4번 index는 s를 p로 변환해야 한다. 하지만 map에 p가 있는데, 이는 p는 이미 다른 값으로의 변환 규칙이 있다는 의미가 된다. 따라서 변환 실패한다.
  • false를 반환한다.
위의 과정을 코드로 만들면 된다. 하지만 예외 사항이 있을 수 있다. 아래의 예를 보자.

 Isomorphic 실패 예

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

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