(Java) 프로그래머스 - 삼각 달팽이

문제의 요구사항은 간단한데 뭔가 될듯 말듯 한 느낌에 풀기가 어려웠다.

처음에는 재귀로 풀어보려고 시도했으나 실패했고 n x n 배열을 만들어서 좌표로 접근했다.

 

로직은 n x n 배열을 만들고 탐색 메서드를 호출해서 0,0 부터 값을 삽입한다.

탐색 메서드에서 상태를 알기 위해서 flag라는 변수를 두었고

배열의 범위를 벗어나지 않으면서 방문하지 않았다면 각 x, y의 변수를 증가시켜서 좌표를 얻었고

그게 아니라면 flag의 상태를 변경시켰다.

 

flag가 0이면 왼쪽 아래로 좌표를 변경,

flag가 1이면 오른쪽으로 좌표를 변경

flag가 2이면 왼쪽 위로 좌표를 변경하였다.

 

탐색이 끝나면 1부터 n까지 idx를 증가시켜가면서 필요한 값만 리스트에 저장하고 리스트를 다시 배열로 변환하여

최종적인 답을 구했다.

 

처음부터 이런 설계로 풀려던건 아니였는데 좀 우당탕 풀었고 그래서 로직이 깔끔하지 않은 느낌이 든다.

---

최종 코드

import java.util.*;
class Solution {
    public int[] solution(int n) {
        // n * n 배열 생성
        int[][] arr = new int[n][n];
        // 방문여부를 확인하기 위한 배열
        boolean[][] visited = new boolean[n][n];

        // 목표 값 (1+2+3...+n)
        int targetNum = 0;
        for (int i = 1; i <= n; i++) {
            targetNum += i;
        }

        // 탐색 메서드 호출
        search(arr, visited, targetNum,0, 0, 1, n);

        int[] answer = new int[targetNum];
        List<Integer> list = new ArrayList<>();

        // 배열을 돌며 idx 까지 list에 추가
        int idx = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j <= idx; j++) {
                list.add(arr[i][j]);
            }
            idx++;
        }

        // 리스트 값 배열에 담기
        for (int i = 0; i < list.size(); i++) {
            answer[i] = list.get(i);
        }
        return answer;
    }
    // 탐색 메서드
    static void search(int[][] arr, boolean[][] visited, int target, int x, int y, int sum, int n) {
        // 연산을 위한 변수
        int flag = 0;

        while (sum <= target) {
            // 방문하지 않았다면
            if(!visited[x][y]) {
                visited[x][y] = true;
                arr[x][y] = sum;
                sum++;
            }

            // flag == 0 이면 x값 증가
            if(flag == 0) {
                // 배열의 범위를 벗어나지 않으면서 방문하지 않았다면
                if((x < n- 1) && (!visited[x + 1][y])) {
                    x++;
                } else {
                    flag = 1;
                }
                // flag == 1 이면 y값 증가
            } else if (flag == 1) {
                // 배열의 범위를 벗어나지 않으면서 방문하지 않았다면
                if((y < n - 1) && (!visited[x][y + 1])) {
                    y++;
                } else {
                    flag = 2;
                }
                // flag == 2 이면 x, y값 감소
            } else {
                // 방문하지 않았다면
                if(!visited[x - 1][y - 1]) {
                    x--;
                    y--;
                } else {
                    flag = 0;
                }
            }
        }
    }
}