24-06-30 알고리즘 문제 풀이

오늘은 컨디션이 썩 좋지 않아서 조금 쉬면서 과제를 조금 손보는 정도로만 공부를 했던 것 같다. 이럴 때는 무리하지 말고 아예 잘 쉬는 것이 앞으로 지속적으로 공부하는데에 더 좋을 것 같다는 생각이다.

 

여기에는 오늘 풀어본 알고리즘 문제 하나를 간단하게 정리해보았다.

 

1. 알고리즘 문제 풀이

오늘은 프로그래머스에 있는 '삼각 달팽이' 문제를 풀어보았다.

1-1. 풀어본 문제

[문제]

 

정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.

 

 

- 제한 사항

• n은 1 이상, 1000 이하입니다

- 입출력 예

n	result
4	[1,2,9,3,10,8,4,5,6,7]
5	[1,2,12,3,13,11,4,14,15,10,5,6,7,8,9]
6	[1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11]

 

 

1-2. 문제 풀이

어찌보면 참으로 단순한 문제인 것 같은데 문제 해결을 위한 아이디어를 떠올리는 게 참으로 쉽지 않았다. 규칙성 같은 것이 있나 찾아보려고 했는데 그런 것은 쉽지 않았다.

 

결국 진짜로 달팽이 채우기를 수행한 뒤에 결과를 반환하도록 프로그램을 짜야했다. 위와 같이 피라미드 모양으로 숫자를 채워나가는 것은 어렵다고 생각해서 n×n 모양의 배열을 만들어서 채워넣기로 했다.

 

n이 5인 경우는 아래와 같이 채워진다

1	0	0	0	0
2	12	0	0	0
3	13	11	0	0
4	14	15	10	0
5	6	7	8	9

 

먼저 모두 0이 들어간 배열을 만든다. 그런 다음 다음과 같은 화살표 방향으로 움직이며 숫자를 채워 넣는다. 먼저 ↓ 방향으로 가다가 더 이상 채울 수 없으면 → 방향으로 이동하고 역시 더 이상 채울 수 없으면 ↖방향으로 이동하면 된다. 이것을 1~n 까지의 합에 해당하는 수(삼각형에서의 네모 상자의 갯수)가 될 때까지 계속 반복하면 된다. 

 

작성한 코드는 아래와 같다. 따라가기 쉽도록 주석을 최대한 자세히 달아보았다.

class Solution {
    fun solution(n: Int): IntArray {
        // 채워지게 될 숫자의 갯수 1~n까지의 합
        val totalNumb = (n+1) * n / 2
        
        // 숫자들이 채워질 n*n 배열
        val answerArray = Array(n) { IntArray(n) }
        var x = 0
        var y = 0
        
        // 이동할 방향을 가리키는 변수
        var direction = 'x'
        
        // 채워질 숫자
        var numb = 1
        
        // 채워져야할 숫자가 모두 채워지면 반복 종료
        while (numb <= totalNumb) {
            when (direction) {
                'x' -> {
                    answerArray[x][y] = numb
                    
                    // x가 n보다 커지거나, 이동하려는 칸이 0이 아니라면 방향을 전환
                    if(x + 1 >= n || answerArray[x+1][y] != 0) {
                        direction = 'y'
                        y++
                        numb++
                    } else {
                        x++
                        numb++
                    }
                }
                'y' -> {
                    answerArray[x][y] = numb
                    
                    // y가 n보다 커지거나, 이동하려는 칸이 0이 아니라면 방향을 전환
                    if(y + 1 >= n || answerArray[x][y+1] != 0) {
                        direction = 'd'
                        x--
                        y--
                        numb++
                    } else {
                        y++
                        numb++
                    }
                }
                else -> {
                    answerArray[x][y] = numb
                    
                    //이동하려는 칸이 0이 아니라면 방향을 전환
                    if(answerArray[x-1][y-1] != 0) {
                        direction = 'x'
                        x++
                        numb++
                    } else {
                        x--
                        y--
                        numb++
                    }
                }
            }
        }
        
        val answer = IntArray(totalNumb)
        var index = 0
        
        
        // 0을 제외하고 차례대로 배열에 담는다.
        for (intArray in answerArray) {
            
            for (int in intArray) {
                if(int != 0) answer[index++] = int
            }

        }
        
        return answer
    }
}

위와 같이 작성했더니 답안으로 잘 통과되었다. 이 문제는 코드로 구현하는 부분에서 꽤나 어려움이 있었고, 다 작성하고 나서도 이게 잘 작동할까 의심이 되었을 정도 였는데 아무 이상없이 잘 작동했다.

 

꽤 어렵게 느껴졌던 문제였는데 잘 풀 수 있어서 만족스러웠다.

 

2. 오늘 배운 것

- 오늘은 그간 공부했었던 네트워크 관련 정리했던 것을 복습하는 시간을 가졌다. 앞으로도 매일 일정시간은 관련 공부를 할 예정이다.