[Programmers/Level 3/Java] 종이접기

Programmers(프로그래머스) 종이접기

코딩테스트 연습 - 종이접기

문제 설명

직사각형 종이를 n번 접으려고 한다. 이 때, 항상 오른쪽 절반을 왼쪽으로 접는다.
종이를 모두 접은 후 전부 펼쳤을 때, ∨ 모양이 생긴 부분을 0으로, ∧ 모양이 생긴 부분은 1로 표시하여 접힌 부분의 모양 배열을 return 하라.

예)
n = 1 -> result = [0]
n = 2 -> result = [0, 0, 1]
n = 3 -> result = [0, 0, 1, 0, 0, 1, 1]

풀이

여러 풀이가 나올 수 있겠지만, 이 문제 역시 효율성을 잘 생각해야 하는 문제이다.
풀기 전, 두 가지로 접근해 보았다.

1. 현재가 k번째 일 때, k-1번째 리스트 원소 앞, 뒤로 0과 1을 번갈아 나타난다.
즉, k-1번째 리스트가 [0, 0, 1]이라면, k번째 리스트는 [0, 0, 1, 0, 0, 1, 1]
(k-1번째 리스트의 원소를 제외하면, 0을 시작으로 0과 1이 반복되어 삽입되는 것을 알 수 있다.)

2. 중앙의 원소를 기준으로, 양 옆이 반전된 대칭의 모습을 가지고 있다. 이 때 왼 편은 이전 k-1번째 리스트의 모습을 하고 있음을 알 수 있다.
즉, k-1번째 리스트가 [0, 0, 1]이라면, k번째 리스트는 [0, 0, 1, 0, 0, 1, 1]
(4번째 원소인 0을 기준으로,1번째 원소(0)와 7번째 원소(1), 2번째 원소(0)와 6번째 원소(1), 3번째 원소(1)와 5번째 원소(0)가 반전된 대칭의 모습을 보이고 있다.)

먼저 1번의 접근으로 문제를 풀어보았다.
결론부터 말하자면, 채점에서 테스트 케이스 17번만 시간 초과로 실패했다. 효율이 좋지 못한 방식이었다.

// 시간 초과로 실패한 코드

import java.util.*;

class Solution {
    public int[] solution(int n) {
        ArrayList<Integer> listFold = new ArrayList<>();   // 접힌 모양 리스트를 저장하는 ArrayList
        listFold.add(0);   // n은 1 이상이므로, 무조건 1번은 접힌다.
        
        for(int i = 2; i <= n; i++)
        {
            int preFoldNum = listFold.size();    // 이전 접힌 모양 ArrayList의 길이를 미리 저장해둔다.
            int foldState = 0;    // 삽입할 접힌 모양을 나타낸다.
            for(int j = 0; j < preFoldNum; j++)
            {
                listFold.add(j*2, foldState);    // 이전 접힌 모양 리스트 원소의 앞에만 삽입하는 방식으로 진행
                foldState = (foldState == 1)? 0 : 1;     // 이번에 넣은 원소가 1이면 0으로, 0이면 1로 변경
            }
            
            listFold.add(foldState);    // 마지막 접힌 모양을 직접 삽입
        }
        
        // ArrayList -> Array
        int[] answer = new int [listFold.size()];
        for(int i = 0; i < listFold.size(); i++)
            answer[i] = listFold.get(i);
        
        return answer;
    }
}

* LinkedList로 바꾸어 풀어도 시간 초과가 발생한다.

다음으로 2번 접근으로 풀어보았다. 
코드의 형태는 비슷해보이나, 리스트 중간에 삽입이 들어가는 것보다 리스트 맨 뒤에 추가되는 것이 훨씬 빠르기 때문에 제한된 시간 안에 통과된 것이 아닐까 생각한다.

// 채첨을 모두 통과한 코드

import java.util.*;

class Solution {
    public int[] solution(int n) {
        ArrayList<Integer> listFold = new ArrayList<>();
        listFold.add(0);
        
        for(int i = 2; i <= n; i++)
        {
            int preFoldNum = listFold.size();
            listFold.add(0);
            for(int j = preFoldNum-1; j >= 0; j--)
            {
                listFold.add((listFold.get(j) == 1)? 0 : 1);   
            }
        }
        
        // ArrayList -> Array
        int[] answer = new int [listFold.size()];
        for(int i = 0; i < listFold.size(); i++)
            answer[i] = listFold.get(i);
        
        return answer;
    }
}