길이가 같은 두 개의 문자열 S와 T가 있다. 이들이 같은 형태의 문자열인지를 판단하라. 같은 형태란 S에 있는 문자를 다른 문자로 치환해서 T와 같아지걸 의미한다.
예제.
"egg"와 "add"는 true를 반환한다. e를 a로 g를 d로 치환하면 add가 되기 때문이다.
"foo"와 "bar"는 false를 반환한다.
"paper"과 "title"는 true를 반환한다.
풀이
아래와 같은 방식으로 풀었다.
문자열 S를 순환한다. 인덱스 변수로 "i"를 사용한다.
S[i]와 T[i]가 서로 다르다면
S[i]를 T[i]로 바꾼다. 이때 S[i:]를 순환하면서 S[i]를 모두 T[i]로 바꾼다.
값을 바꿀 때, 이미 변환 된 문자인지를 map에서 확인한다.
값을 바꿀 때, 값의 패턴이 틀리면 false를 반환한다. S="foolo", T="brrpd"라고 가정해 보자. s의 모든 o는 r로 변환한다. 그런데 s의 마지막 o는 r이 아닌 d다. Replace 규칙에 어긋 나므로 이 문자열은 Unisomorphic 하다는 것을 알 수 있다.
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를 반환한다.
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를 반환한다.
위의 과정을 코드로 만들면 된다. 하지만 예외 사항이 있을 수 있다. 아래의 예를 보자.
s -> o의 규칙을 가진다. 4번 인덱스를 보면 o가 있지만, 이미 s -> o 라는 규칙이 있고 반드시 1:1이어야 하므로 j -> o는 허용 될 수가 없다. 따라서 문자열 S는 무조건 Unisomorphic 하다. 문자열을 순환하면서 치환하는 중에 변환 규칙을 검사해서 어긋 나는게 있다면 바로 false를 반환하면 된다. func (i *isomorphic) Replace() 메서드가 bool을 리턴하는 이유다.
더 이상의 예외 사항은 없을까 ? 알고리즘 해법을 찾는데 중요한 이슈다. 가능한 패턴을 하나하나 만들어 보면서 테스트하는 방법이 있을 것이다. 하지만 이 방법은 너무 비효율 적이다. 어떻게 해야 일일이 패턴을 만들지 않고, 가능한 예외들에 대한 검증이 충분하다는 걸 확인 할 수 있을 까 ?
같은 형태의 문자열 가려내기
풀이
풀이과정 회고
Recent Posts
Archive Posts
Tags