[TIL] 2019-10-24

undefcat·2019년 10월 23일

TIL

목록 보기

37/228

알고리즘

종만북

9.9 - 드래곤 커브

문제를 풀었는데, 저번에 풀었을 때 나왔던 오답이 또 나왔다. 그때는 아무리 생각해도 이해가 안돼서 그냥 넘겼는데, 오늘은 이유를 알아내서 이 문제의 해설을 정리본다.

우선 문제가 요구하는 답을 생성하는 함수의 윤곽을 1차적으로 생각해보면

func curve(seed string, generation, p, l int) string

로 간단하게 생각해볼 수 있다.

이 때, X Y 문자가 재귀적으로 확장되므로 함수의 형태를 재귀함수로 바꿔볼 수 있다. 그러면 p l이 걸림돌이 된다. 따라서 문제가 요구하는 p번째부터 l개의 문자를 출력하는 대신에, 그냥 p번째를 출력하게 만들고 이를 여러번 호출하는 형태로 바꿔볼 수 있다.

func curve(seed string, generation, p int) rune

for i := 0; i < l; i++ {
  curve(seed, generation, p+i)
}

대략 위처럼 호출하면 될 것 같다.

또, 문제에서는 부분 문자열만 출력하라고 했으므로 그 이전 문자열들에 대해서는 무시하고 넘어가는 방법이 있을 수 있다고 눈치챌 수 있다. 또한 X Y는 재귀적인 구조를 가지므로 X Y의 길이값은 generation에 대한 1:1대응 함수라고 눈치챌 수 있다.

따라서 X Y의 길이를 미리 계산할 수 있을텐데

xLen(gen) = xLen(gen-1) + yLen(gen-1) + 2
yLen(gen) = xLen(gen-1) + yLen(gen-1) + 2

위와 같은 수식을 문제로부터 얻어낼 수 있는데, 이 때 두 값이 같으므로 결국

len(gen) = 2 * len(gen-1) + 2

위의 수식으로 표현할 수 있다. 또한

len(0) = 1

이므로, 문제에서 generation은 최대 50세대까지이므로 이를 미리 계산할 수 있다.

length := make([]int, 51)
length[0] = 1

for gen := 1; gen <= 50; gen++ {
  length[gen] = length[gen-1]*2 + 2
}

위와 같이 간단하게 계산할 수 있다. 사실 이 값이 overflow될 수 있음을 주의해야 하는데, Golang에서는 int값이 int32 혹은 int64등이 될 수 있는데, 내 머신의 경우 64비트머신이므로 int64로 구현되어있는데 이 값을 overflow하지 않아서 그냥 계산했다.

안전하게 하고자 한다면 문제에서는 p번째 글자부터 l개를 출력하라고 했으니, 1 <= p <= 1,000,000,000, 1 <= l <= 50 이므로 MAX값을 1,000,000,050으로 설정하고 이 값을 넘지 않게 length에 넣어주면 된다.

그 다음, curve의 구현을 생각해보자.

위에서 얘기했듯, 부분 문자열을 출력하면 되므로 그 이전 문자열에 대해서 넘어갈 수 있는 방법이 있을 수 있다고 추측하고 length를 구했다. 즉, k번째 수문제로 접근할 수 있다.

그렇다면 p번째를 출력하기 위해 p-1번을 넘어가면 된다. 따라서

curve(seed string, generation, skip int) rune

위와 같이 p를 skip으로 생각할 수 있고 skip = p - 1로 두면 될 것이다.

curve는 재귀함수형태를 띌 것이므로, 기저사례를 생각해보자. 당연히 generation이 0이면 남은 skip만큼 출력하면 될 것이다.

if generation == 0 {
  return rune(seed[skip])
}

이 때, 정상적인 경우라면 skip은 seed의 길이를 넘어가지 않을 것이다.

그 다음, seed문자열에 대해 확장할 것인지 넘어갈 것인지 출력할 것인지 결정하면 된다.

여기서 여러 상황들을 생각해보면

skip이 0이면 그냥 출력하면 된다.
X Y가 아니면 skip--하면 된다.
X Y면, 확장했을 때 값이 skip보다 작거나 같으면 넘기고 아니면 확장해서 출력하면 된다.

위와 같이 단편적으로 생각할 수 있다. 이를 곧이 곧대로 구현하면

for _, c := range seed {
  if skip == 0 {
    return c
  }
  
  if c != 'X' && c != 'Y' {
    skip--
    continue
  }
  
  if skip >= length[generation] {
    skip -= length[generation]
    continue
  }
  
  if c == 'X' {
    return curve("X+YF", generation-1, skip)
  } else {
    return curve("FX-Y", generation-1, skip)
  }
}

panic("impossible case")

위와 같이 구현할 수 있다. 이러면 어떤 경우에는 답이 잘 나오는데, 어떤 경우에는 답이 잘 나오지 않는다. 내가 이 부분에서 왜 안되지? 고민을 많이 했었는데

if skip == 0 {
  return c
}

이 부분에 문제가 있었다. 만약에 Y문자열의 확장값이 FX-Y가 아니라 YF-X 같은 문자열이었다면, 아마 그냥 아무런 문제 없이 문제를 풀었을 것이다. 문제는 Y의 경우, 확장되었을 때 첫번째 문자열이 Y가 아니라는 것에 있었다. 아직 진화 세대가 남아있음에도 그냥 출력해버리니, Y의 진화 이후 문자열이 바뀌는 것을 생각하지 못했던 것이다. 그래서 문제의 답이 얼추 비슷하긴 했는데, F가 나와야 할 곳에 Y가 나와서 당황했었다.

따라서 이를 해결하려면