[민정님] SWEA-1954, 2007 코드 리뷰

[psychology50]

달팽이 숫자

• 처음 이 문제를 봤을 때, '어떤 규칙이 있을까?'라는 생각이 들었지만 금방 접었습니다. 왜냐하면, N이 최대 10이기 때문에 O(N^5)이라는 무식하기 그지없는 코드를 작성하더라도 반드시 통과될테니까요. (그렇다고 진짜 저런 알고리즘을 사용할 생각은 없습니다.)
• 그럼 이제 고민해야 하는 것은 2가지가 됩니다.
  • 어떻게 방향을 지정할 것인가?
  • 언제 방향을 지정할 것인가?

1. 어떻게?

• 2차원 그래프 상에서 상하좌우로 움직이는 방법은 너무나 쉽습니다.
  • 현재가 (y, x)위치라면, (y-1, x)가 상, (y+1, x)가 하, (y, x-1)가 좌, (y, x+1)가 우입니다.
  • 저희는 우→하→좌→상 순서로 움직이므로 편하게 dy, dx를 다음과 같이 정의합시다. (해당 값은 불변하므로 전역 변수로 할당하셔도 무방합니다.)

  int[] dy = new int[]{0, 1, 0, -1};
  int[] dx = new int[]{1, 0, -1, 0};

• 그럼 다시 현재 위치가 (y, x)라면, 방향을 어떻게 지정할 수 있을까요?
  • y + dy[0], x + dx[0]은 곧 (y+0, x+1)이므로 오른쪽으로 이동합니다.
  • 그렇다면 dy, dx의 인덱스 값인 0, 1, 2, 3을 잘 이용하면 방향을 컨트롤할 수 있게 되겠네요.

2. 언제?

• 만약 오른쪽으로만 이동한다면, 아래의 코드만으로도 충분하겠죠.

  int y=0, x=0;
  for (int cnt = 0; cnt <= N*N; ++i) {
    box[y][x] = cnt;
    y += dy[0]; x += dx[0]; // 언제나 오른쪽만
  }

• 하지만 이건 NN 길이의 일차원 배열이 아닌, NN 크기의 이차원 배열이므로 오른쪽으로만 값을 채우는 것은 불가능하겠죠. 그러니 다음과 같이 이동하다가 범위를 벗어난 경우가 곧, 방향을 바꿔줘야 할 시기가 됩니다.
  • 위에 올려놓은 그림을 보시면, 범위는 벗어나지 않았지만 이미 방문했던 좌표가 진행 경로 상에 있을 때도 방향을 바꿔줘야 겠네요.

  int dir=0; // 방향 조절용 (0, 1, 2, 3) == (우, 하, 좌, 상)
  int y=0, x=0;
  for (int cnt = 0; cnt <= N*N; ++i) {
    box[y][x] = cnt;
  
    int ny = y + dy[dir], nx = x + dx[dir]; // 다음 이동할 좌표 확인
    if (!isValid()) // 유효하지 않은 범위거나, 이미 방문했던 좌표라면?
       dir = 어떻게?;
  
    y += dy[dir]; x += dx[dir];
  } 

• 이제 거의 다 왔는데, 그럼 어떻게 방향타인 dir의 값을 조절할 수 있을까요?
  • dir이 0일 때는 dy[0], dx[0]을 가리키게 될 것이므로 오른쪽을 의미합니다.
  • dir += 1 을 해주면 dy[1], dx[1]을 가리키게 되어 아래쪽을 의미하겠죠? 그럼 마냥 더하기를 해주면 될까요?
  • dir의 값이 4가 되었을 때, dy, dx의 인덱스는 3까지 밖에 없으므로 OutOfIndex 에러가 발생할 겁니다. 그렇다면 다시 0으로 초기화해야 할 텐데, 어떻게 해야 할까요?
  • 값에 대해 %4로 나머지 연산을 해주면, 이는 곧 숫자의 범위를 0~3 내로 제한하는 효과를 가져옵니다. (dir의 값이 0, 1, 2, 3일 때는 상관 없지만, 4가 되는 순간 나머지 연산에 의해 0으로 돌아가게 됩니다.)

패턴 마디의 길이

• 이 문제는 N=30, 마디 최대 길이가 10이므로 무식하게 풀려면 진짜 무식하게 풀 수도 있겠네요.
• 첫 번째는 최대 길이를 1부터 10까지 늘려보면서 마디를 찾아내는 방법입니다.
  • 최대 길이가 1이면, s[0, 0]과 s[1, 1]
  • 최대 길이가 2이면, s[0, 1]과 s[2, 3]
  • 최대 길이가 3이면, s[0, 2]와 s[3, 5]
  • 이걸 반복하면서 마디를 찾아내면 못 해도 10번 내로 찾아낼 수 있긴 하겠네요.
• 조금 더 생각을 해보자면 마디는 곧 반복되는 문자열이므로, 반복이 되기 위해서는 시작되는 문자가 같아야 한다는 말이 됩니다.
  • 예를 들어, KoreaKoreaKorea라는 문자열에서 마디를 찾으려면 가장 먼저 Korea의 시작 문자인 K가 같은 지점부터 찾아봐야겠죠.

• 하지만 시작 문자가 같다고 마디가 되진 않습니다. SAMSUNG에는 S가 두 번이나 들어가니까요.
• 그러니 SAM의 S와 SUNG의 S에 대해 문자 매칭을 하는 작업이 필요합니다. (s[0, now-1]과 s[now, now + (now-1)] 비교)
• 이런 식으로 찾는 것도 가능은 하겠네요.