[프로그래머스 level_3] 종이접기 for JAVA (Summer/Winter Coding(2019))

[문제 설명]

직사각형 종이를 n번 접으려고 합니다. 이때, 항상 오른쪽 절반을 왼쪽으로 접어 나갑니다. 다음은 n = 2인 경우의 예시입니다.

먼저 오른쪽 절반을 왼쪽으로 접습니다.

다시 오른쪽 절반을 왼쪽으로 접습니다.

종이를 모두 접은 후에는 종이를 전부 펼칩니다. 종이를 펼칠 때는 종이를 접은 방법의 역순으로 펼쳐서 처음 놓여있던 때와 같은 상태가 되도록 합니다. 위와 같이 두 번 접은 후 종이를 펼치면 아래 그림과 같이 종이에 접은 흔적이 생기게 됩니다.

위 그림에서 ∨ 모양이 생긴 부분은 점선(0)으로, ∧ 모양이 생긴 부분은 실선(1)으로 표시했습니다.

종이를 접은 횟수 n이 매개변수로 주어질 때, 종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접힌 부분의 모양을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 종이를 접는 횟수 n은 1 이상 20 이하의 자연수입니다.
• 종이를 접었다 편 후 생긴 굴곡이 ∨ 모양이면 0, ∧ 모양이면 1로 나타냅니다.
• 가장 왼쪽의 굴곡 모양부터 순서대로 배열에 담아 return 해주세요.

[풀이]

일단 문제를 봤을 때 종이를 접고 접는 과정에서 접히는 선들이 늘어나는 것이 2의 (접는 수) 승 -1 인 것을 알게 돼서 이진트리를 이용해 문제를 풀려고 했다. 그리고 규칙을 찾았어야 했는데 어떻게 규칙을 찾아볼까 하는 과정에서 종이들을 실제로 접어보고 규칙을 찾아냈다. 아래 사진을 보면 좋겠다.

0인 부분은 뒤로 접혀있고 1인 부분은 앞으로 접혀있다.

각 노드의 지점은 종이를 접었을 때 순서대로 접히는 부분을 의미한다.

이진트리로 표현하면 이런 모양이 나온다.

저 패턴을 어떻게 순서대로 표현할 것인지에 대한 방법은 이진트리 순회방법 중 중위 순회를 사용하는 것이다.

 

[코드]

public class Origami {
 
    public int[] binaryTree;
    public int[] answer;
    int idx;
 
    public int[] solution(int n) {
        binaryTree = new int[(int) (Math.pow(2, n))];        //이진 트리
        answer = new int[(int) (Math.pow(2, n)-1)];            //답지
        idx = 0;
        
        binaryTree[0] = -500000;                            //이진트리 특성상 편히 계산하기 위해 인덱스 0에는 아무 값이 들어가지 않음.
        binaryTree[1] = 0;                            
        for(int i = 1; i < (Math.pow(2, n)-1) /2 ; i++) {   //이진 트리 만들기.
            binaryTree[i*2] = 0;
            binaryTree[i*2+1] =1;
        }
        
        inOrder_tree(1);                                    //중위 순회하기
        return answer;
        
    }
    public void inOrder_tree(int n) {                        
        if(n * 2 >= binaryTree.length) {                    //해당 인덱스가 리프노드이면
            answer[idx++] = binaryTree[n];
            return;
        }else {
            inOrder_tree(n*2);                                //중위 순회
            answer[idx++] = binaryTree[n];
            inOrder_tree(n*2+1);
        }
        
    }
}

프로그래머스 테스트 케이스 통과

느낀 점 : 처음부터 규칙을 찾으려고 하는 내 모습이 노하우가 조금 늘은 모습 같아서 살짝 기분 좋았다. 실제로 아는 지식을 동원해서 규칙을 찾았을 때 혹은 풀이 방법을 알게 됐을 때 얻는 성취감? 뿌듯함은 오묘하게 중독되는 것 같다. 

다 풀고 나서 다른 사람들의 풀이를 보았을 때, 다른 문제들 보다 풀이 방법, 규칙을 도출해 내는 방법이 여러 가지가 있어서 신기했다. 더 열심히 해서 그분들처럼 고수가 되어야겠다.

 

**피드백은 언제나 환영입니다!!