[Java] Spiral

0 | 1/codearts | 2011. 4. 7. 11:04
Posted by oveRock

일단 소스 코드부터 보고...

public class spiral {

    public static void f(int r, int c) {

        int e[]=new int[r*c],x=0,y=-1,n=r*c;for(int
                    t                             :
                    e ){System.out.print(n/***/+" "
                    ) ;                         t =
                    ( ( t=n+x+y*c)<1||t>r*c||e[ t -
                    1 ]                       > 0 )
                    ? x=(y-=x+=y)+x:0;++e[n-1]; n =
                    n                           + (
                    x+y*c);}System.out.println(); ;

    }
    
   
    public static void main(String...args) {

        f(3, 4);

        f(5, 3);

    }
}

잘 살펴보면, int e[]=new 이후의 소스 코드가 반시계방향의 소용돌이를 그리고 있다. 깔맞춤을 위해서 잉여 세미콜론이나 주석문이 삽입된 건 걍 애교로 봐 주자.

어디에 쓰는 물건인고?
위 클래스를 컴파일하고 실행해 보면, 다음과 같은 결과물을 출력한다.
12 8 4 3 2 1 5 9 10 11 7 6
15 12 9 6 3 2 1 4 7 10 13 14 11 8 5

응? 아직도 뭐 하는 녀석인지 잘 모르겠다고?
하긴, 그럴 수도 있겠다. 얼핏 보기에 무의미한 숫자의 나열에 불과할 수도 있으니...

위 함수 f는 인자 r(row), c(colums)를 넘겨받아 r×c 크기의 행렬을 가정하고, 이 행렬에 좌측 상단부터 시작하여 차례로 1, 2, 3, .... , n(r×c)까지의 숫자를 채워넣은 다음, 우측 하단에서 윗 방향으로 출발하여 가장자리로부터 행렬상의 모든 숫자를 반시계방향으로 돌아가며 출력하는 프로그램이다. (2011년 사이냅소프트 추가 채용퀴즈 문제)

사이냅소프트 채용 공고 페이지에 제시된 설명.


전형적인 ACM 스타일의 퀴즈이며, 간단한 요구사항 치고는 해법도 무진장 많은 축에 속한다.

어떻게 작성되었나?
일단, 행렬에 배치된 숫자는 순차적이다. 즉 각 셀에 숫자를 저장할 공간이 필요하지는 않다는 뜻. 이미 해당 셀을 방문했는지의 여부를 저장한 공간만이 필요하며, (x, y) 위치에 해당하는 숫자는 (y×r + x)가 될 것이다.
또한, 요구조건대로 순회를 끝마치면, 모든 셀을 한 번씩 지나가며 순회에 필요한 반복 회수는 r×c회가 될 것이다.
순회상태 저장 공간조차 필요로 하지 않는 해법이 분명 있을 것으로 보이지만, 일단은 1차원 배열 boolean status[r*c]에 상태를 저장하는 공간을 만들어 두는 시나리오로 달려보자.

2차원 배열에 비해 1차원 배열의 선언은 얼핏 단순하지만, 한 가지 문제가 남는다. 바로 boundary check로, row 범위를 초과하는지 여부는 0 < (index) <= r×c라는 비교적 간단한 공식으로 확인가능하지만, column 범위를 초과하는지 여부를 판단하는 것은 쉽지 않다.
하지만 알고 보면 이 조건은 고의적으로 무시 가능하다. 왜냐 하면 문제의 조건상 column 범위를 초과하는 경우는 단 한번, ... -> 3 -> 2 -> 1 -> ? 로 가는 경우 뿐이기 때문이다. 이건 다행히(?) row의 boundary check 조건과 중복되며, 그밖의 경우는 이미 방문한 셀을 다시 방문하지 않는다는 조건상 발생 가능성이 없다.

따라서 방향의 전환을 결정하는 조건문은 다음과 같이 정의 가능하다.
(nextIdx < 0) || (nextIdx > row * column) || (status[next-1] == true)

이제 방향의 전환에 대해서 고민해보자.
현재 index에서 다음 index를 결정하는 변량 dR, dC를 바꾸어 주는 것 역시 여러가지 방법이 있다. switch...case문으로 '무식하게' 돌려주는 방법도 있을테고, 조금 엘레강스하게 dR, dC를 배열(상,좌,우,하)로 선언하여 접근하는 방법도 있을 것이다.
하지만 고등학교를 준수히 졸업한 사람이라면 행렬의 곱셈을 이용해서 다음과 같은 식을 얻을 수 있겠다. 분명히 고교를 무사히 졸업했는데도 잘 생각이 나지 않는다면, '행렬을 이용한 회전 변환'을 다시 공부하자.
dC = dR
dR = -dC

굳이 쉬운 길을 돌아가기 위해서, 임시 변수를 두지 않고 두 수를 변환해 보자.
dC += dR -= dC += dR

어? 그런데 자바에서 위 식은 의도한 대로 결과가 나오지 않는다(C에서는 잘 된다). 이는 자바가 call-by-value 방식으로 변수 또는 인스턴스에 접근하기 때문이다. 아쉽지만 조금 모양을 바꾸어 보자
dC = (dR -= dC += dR) + dC

.... 그냥 임시변수 하나 쓸 걸 그랬나보다.

마지막으로, 이러한 코드아트 작성에 가장 큰 애로사항이 두 가지 남았다.
  1. 길다란 키워드
  2. 어쩔 수 없이 공백으로 분리되어야 하는 토큰
원래 boolean[]이었던 상태배열 status를 int[]형으로 바꾸고, 변수명은 죄다 한 글자로 줄여버린다.
하지만 작성 도중 조건문인 if가 공교롭게도 코드아트에 큰 걸림돌이 되었다. 이걸 i f라고 떼어서 쓸 수도 없고....

고민 끝에 if(cond) (stmt); 부분을 다음과 같이 치환했다.
t = (cond) ? (stmt) : 0 ;

야호! 드디어 코드 중간에는 모든 토큰이 1자이며, 서로 분리되거나 붙여도 상관없는 상태로 모두 치환되었다.
(삽질도 정말 가지가지 한다 -_-;;)

나머지는 뭐... 적당히 손질하고 썰어저 나선 모양으로 만들되, 피치 못한 공간은 주석문이나 세미콜론으로 메우면 끝.
숫자들 사이에 공백(" ")이 들어가야 하는데, 이 부분을 코드아트에 녹여버린 점도 눈여겨 볼 것.

뽀나스
점잖은(?) 소스.
public static void f(int row, int col)
{
    StringBuffer ret = new StringBuffer();
    boolean idx[] = new boolean[row*col];
    
    for(int i=0, nextIdx, curIdx=row*col, dX=0, dY=-1; i<idx.length; ++i)
    {
        idx[curIdx-1] = true;
        ret.append(curIdx).append(" ");
        
        nextIdx = curIdx+dX+dY*col;
        if(nextIdx<1 || nextIdx>row*col || idx[nextIdx-1])
        {
            dX += dY;
            dY -= dX;
            dX += dY;
        }
        
        curIdx += dX+dY*col;
    }
   
    System.out.println(ret);
}


뽀나스 #2
MSG와 트랜스지방을 빼서 더 맛깔나고 담백한 소스(읭?!).... 는 훼이크고, 방문상태를 저장하는 배열 없이 문제를 해결한 프로그램이다. 변수명이 신경쓰이면 지는거다. 분석은 각자 알아서...
public class TheFinalSpiral {

    public static void f(int r, int c) {

        String b="";

        int m,e,a,t,s,p,i,n;for(e=0,p=r,m=c,i=-1,
            a                                  =
            0 ,t=1,s=r*c,n=s;e<r*c;++e){b+=n+" "
            ; t                              = t
            + ( ((n=(p+i-1)*c+(m+a))==s)?c+1 : 0
            ) ;                            s = s
            - ((n==s)?c+1:0);if(n<t||n>s)a=( i =
            i                                - (
            a=a+i))+a;p=i+p;m=a+m;n=(p-1)*c+m; }
        
       
        System.out.println(b);

    }
    
   
    public static void main(String... args) {

        f(3,4);

        f(5,3);

    }
}

댓글을 달아 주세요

블로그 이미지

oveRock

(life) = ∫(decision)dt

카테고리

분류 전체보기 (129)
Kaffa (13)
Muzik (18)
Skeptic (4)
Foto (10)
0 | 1 (16)
Etc... (68)