[ 프로그래머스 Level 3 종이접기 ] 문제 풀이(Java) - 써머/윈터코딩 2019

프로그래머스의 '종이접기' 문제를 풀어보았다.

 

 

문제보기

https://programmers.co.kr/learn/courses/30/lessons/62049

프로그래머스

문제 설명

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

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

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

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

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

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

 

제한사항

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

---

입출력 예

n	result
1	[0]
2	[0,0,1]
3	[0,0,1,0,0,1,1]

입출력 예 설명

입출력 예 #1
종이의 오른쪽 절반을 왼쪽으로 한번 접었다 펴면 아래 그림과 같이 굴곡이 생깁니다.

따라서 [0]을 return 하면 됩니다.

 

입출력 예 #2
문제의 예시와 같습니다.

 

입출력 예 #3
종이를 절반씩 세 번 접은 후 다시 펼치면 아래 그림과 같이 굴곡이 생깁니다.

따라서 [0,0,1,0,0,1,1]을 return 하면 됩니다.

 

 

나의 풀이

 

처음 시도> 0과 1을 저장할 ArrayList를 하나 선언한 후 이전 단계에서 만들어진 선의 좌, 우에 0과 1을 추가하는 방식으로 풀었다. 그래서 몇 번째 단계에서 만들어진 선인지 구분하기 위해 Paper class를 만들어 idx에 단계를 추가적으로 저장해줬다.

 

1차 코드

import java.util.*;

class Paper{
    int idx;
    int num;    //0인지 1인지
    
    Paper(int idx, int num){
        this.idx = idx;
        this.num = num;
    }
}
class Solution {
  public int[] solution(int n) {
      
      ArrayList<Paper> list = new ArrayList<Paper>();
      list.add(new Paper(1, 0));
      for(int i=2;i<=n;i++){
          for(int j=list.size()-1;j>=0;j--){
              if(list.get(j).idx == i-1){
                  list.add(j+1, new Paper(i, 1));
                  list.add(j, new Paper(i, 0));
              }
          }
      }
      int [] answer = new int[list.size()];
      
      for(int i=0;i<answer.length;i++)
          answer[i] = list.get(i).num;
      return answer;
  }
}

하지만 결과는 시간 초과였다,,,,, 아무래도 리스트의 중간에 계속 삽입하는 방식은 하나를 삽입하면 이후 원소들까지 자리를 바꾸는 연산 때문에 오래 걸리는 듯 하다!

 

 

2차 생각> 종이 접기에 의해 생기는 선은 대칭이다. 따라서, 다음과 같은 규칙이 가능하다.

 

n = 2일 때,

 

0  0  1

 

n = 3일 때를 구하기 위해서는, n = 2일 때의 결과에 뒤에 0을 하나 추가

 

0  0  1  0

 

그리고 앞선 원소들에 대해 대칭이므로 뒤에 원소를 추가

 

0  0  1  0  0  1  1

 

그러면 색깔이 같은 원소들끼리 대칭을 이루게 된다.

 

0  0  1  0  0  1  1

 

다음과 같이 구현하여 시간 초과 문제 해결!

 

 

코드

class Solution {
  public int[] solution(int n) {
      int[] answer = new int[(int)Math.pow(2, n) - 1];
      answer[0] = 0;
      for(int i=2;i<=n;i++){
          int center = (int)Math.pow(2, i-1) - 1;
          answer[center] = 0;
          for(int j=center-1;j>=0;j--){
              int dist = center - j;
              if(answer[j] == 0)
                answer[center+dist] =  1;
              else if(answer[j] == 1)
                  answer[center+dist] = 0;
          }
      }
      return answer;
  }
}

 

결과

모든 테케 통과!