SW Expert Academy 1954 달팽이 숫자를 통해 구현 문제 공략하기
적절한 타이밍에 어려운 문제를 만났다.
삼성 소프트웨어 아카데미 D2 문제들 거의 대부분이 쉽지만, 중간 중간에 어려운 문제가 보이는 건 사실이고, 내가 볼 땐 D3 쯤에 있어야할 문제 같지만 단순 숫자 위치를 상,하,좌,우 이동에 따라 배치를 바꾸는 문제라 D2에 문제가 할당된 것 같다.
하드 코딩을 한다고 하더라도 이 값을 구현하는 것은 관련 코딩 경험이 적은 나로서는 어려운 일이고, 앞으로 시뮬레이션 문제에 대해 심화 코딩을 충분히 해볼 일이 많은 나로서는 넘어야할 난관인 것 같았다.
문제 설명은 전혀 어렵지 않았고, 증가하는 숫자 값을 달팽이 껍질 모양처럼 시계 방향에 따라 배치하는 것이다.
문제 설명은 굉장히 쉽지만, 코딩하는 과정은 순탄치 않았다. 방법이 도저히 떠오르지 않아서 정답을 보게 되었고, 정답을 보니 구현이 꽤 어려운 문제였다. 아래의 코드는 누군가 작성한 모범 답안이다.
이 문제를 “구현”하는데 있어서 핵심은 아래의 절차를 통해 확인할 수 있다.
n이 4로 주어졌다 가정하고, 코드가 실행되는 절차를 차분히 작성해보자.
- 0행 0열부터 시작해서 1열, 2열, 3열로 증가하는 것을 볼 수 있다. (n 만큼 열 증가)
- 이번엔 3열을 유지하고, 1행, 2행, 3행으로 증가하는 것을 볼 수 있다. 0행은 이미 채워졌으니 1행부터 채우는 것이다. (n-1만큼 행 증가)
- 3행 3열에서 다시 열 감소가 이루어져 3행 0열까지 돌아온다. (n-1만큼 열 감소)
- 3행 0열에서 다시 행 감소로 위로 올라간다. (n-2만큼 행 감소)
위의 과정들이 반복되어서 n이 0보다 작으면 종료되면 되는 것이다.
만약 n이 4 이상이라면,
n-2 → n-3 → n-3 → n-4 형태로 외부에서 내부로 점점 값이 좁혀나가는 것이다. (다만, 백준에서 비슷한 유형의 알고리즘을 찾아보니 외부 → 내부 형태 뿐만 아니라 그 반대의 경우, 내부 → 외부 형태로 값을 찾아나가는 것도 출제될 수 있다는 것을 알 수 있었다)
그래서 이 방식 대로라면 하나의 이중 배열 내 요소 값을 기준으로 아래의 형태로 값을 비교하게 될 것이고, 그게 현재 코드에서 dx, dy 변수다.
또한 여기서 한 가지 더 중요한 사실은 이동하려는 옆 칸 또는 상, 하 값에 이미 0 이외의 값이 할당 되어 있다면 (즉, 이미 지나온 길이라면) 해당 경로는 가지 않는 형태로 활용해야한다.
이 내용들이 17번째 라인에 모두 조건으로 담겨 있는 것이다.
ori 라는 변수가 3까지 왔다면 (즉, 방향 전환을 4번 했다면) 다시 0으로 초기화해서 다시 똑같은 패턴을 반복하는 것이다.
(i 값 자체는 코드에서 손대지 않는다.)
솔직히 말해서, 발상이 너무 어려웠다. 특히 이중 배열을 활용하는 문제는 보통 좌표나 체스, 팩맨 같은 게임을 가장해 출제되는 경우가 많은데 (특히나 삼성은 탐색 관련 문제를 매우 사랑하는 걸로 알려져있다) 그 문제의 기초의 기초 문제였다.
5월 전에 소프트웨어 역량 테스트 A, B 유형 모두 통과하는 것을 목표로 잡아야겠다.
Reference
Ryan
