[둥근 길]

[문제]

엘보니아의 왕은

width 미터 * length미터 넓이의 궁전에서 살고 있다. 그는 신하들을 진흙 위에 살고 있게 하였기 때문에 인기 있는 왕은 아니었다. 그는 방문자들이 그를 접견하기 위해 오래 걷게 만들고 싶어서 궁전을 나누고 싶어했다. 왕의 보안 고문은 나선형으로 나누자고 제안했다. 방문자는 남서쪽 모서리에서 입궁하여 동쪽으로 걷는다. 방문자 앞에 벽이 나타나면 왼쪽으로 방향을 바꾼다. 나선형 복도의 너비는 1미터이다.

아래 다이어그램은 나선형 길의 한 예제이다:

방문객은 a (남서쪽 모서리)에서 출발하여 알파벳 순서대로 x (왕좌)까지 이동한다.

nmlkji

oxwvuh

pqrstg

abcdef

왕은 궁전의 길을 새로 만들기 전에 그의 왕좌를 먼저 정확한 위치로 옮기고 싶어하기 때문에 나선형의 길이 어디서 끝날지 알아야 한다. 왕좌의 좌표를 두개의 정수로 리턴하시오.

남서쪽 모서리는 (0, 0)이고 남동쪽 모서리는 (width - 1, 0), 그리고 북동쪽 모서리는 (width - 1, length - 1)이다.

풀이 1) - python

class Solution:
    def solution(self, width, length):
        check=x=y=0
        N=width*length
        
        while True:
            x+=(width-1)
            check+=width
            if check==N:
                return [x,y]
        
            y+=(length-1)
            check+=(length-1)
            if check==N:
                return [x,y]
            
            x-=(width-1)
            check+=(width-1)
            if check==N:
                return [x,y]
        
            y-=(length-2)
            check+=(length-2)
            if check==N:
                return [x,y]
        
            x+=1
            width-=2
            length-=2

풀이 2) - python

class Solution:
    def solution(self, width, length):
        answer = {'x':0,'y':0}
        
        if width>2 and length>2 : # 양쪽 변이 둘다 2보다 큰 경우는 2줄씩 삭제하고 x,y 2줄씩 삭제할 때마다 한칸씩 이동한 것과 같은 효과를 가지므로,
            detector = min(width,length)
            answer['x'] =  answer['x'] + int((detector-1)/2)
            answer['y'] =  answer['y'] + int((detector-1)/2)
            width = width - int((detector-1)/2)*2
            length = length - int((detector-1)/2)*2
 
        if width >= 2 :
            if length >= 2 :
                answer['y'] =  answer['y'] + 1
            else :
                answer['x'] =  answer['x'] + width - 1 
        else :
            if length >= 2 :
                answer['y'] =  answer['y'] + length - 1
            else :
                pass
        
        return [answer['x'], answer['y']]

풀이 3) - java

public class Solution{
    public int[] solution(int width, int length){
        int pos[]=new int[2];
        int posx=0,posy=0;
        boolean state=true;    //true면 가로이동 false면 세로이동
        boolean xstate = true,ystate = true; //true면 인덱스숫자 추가중, false면 감소중
        int countx=0, county=0;
        
        for(int i=width*length;i>1;i--){
            boolean flag=true;
            if(i==width*length){
                if((posx+1)>=width)  state=false;
            }
            if(flag&&state){  
                if(flag&&xstate){ //가로로 증가
                    posx++;
                    if(posx>=(width-1-countx)){
                        state=false;
                        xstate=false;
                        flag=false;
                    }
                    
                }else if(flag){  //가로로 감소
                    posx--;
                    if(posx<=0+countx){
                        state=false;
                        xstate=true;
                        flag=false;
                        county++;
                    }
                }
               
            }else if(flag){
                if(flag&&ystate){ //세로로 증가
                    posy++;
                     if(posy>=(length-1-county)){
                        state=true;
                        ystate=false;
                        flag=false;
                    }
                  
                }else if(flag){  //세로로 감소
                    posy--;
                    if(posy<=0+county){
                        state=true;
                        ystate=true;
                        flag=false;
                        countx++;
                    }
                }
              
            }
   //         System.out.println(posx+" "+posy);
        
        }
        pos[0]=posx;
        pos[1]=posy;
        return pos;
    }
}