[프로그래머스] - 종이접기

문제설명

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

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

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

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

• 위 그림에서 ∨ 모양이 생긴 부분은 점선(0)으로, ∧ 모양이 생긴 부분은 실선(1)으로 표시했습니다.
• 종이를 접은 횟수 n이 매개변수로 주어질 때, 종이를 절반씩 n번 접은 후 모두 펼쳤을 때 생기는 접힌 부분의 모양을 배열에 담아 return 하도록 solution 함수를 완성해주세요.

 

제한사항

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

 

입출력 예

 

입출력 예 설명

• 입출력 예 #1
  • 종이의 오른쪽 절반을 왼쪽으로 한번 접었다 펴면 아래 그림과 같이 굴곡이 생깁니다.
  • 따라서 [0]을 return 하면 됩니다.

• 입출력 예 #2
  • 문제의 예시와 같습니다.
• 입출력 예 #3
  • 종이를 절반씩 세 번 접은 후 다시 펼치면 아래 그림과 같이 굴곡이 생깁니다.
  • 따라서 [0, 0, 1, 0, 0, 1, 1]을 return 하면 됩니다.

 

솔루션

• 종이접기를 보면 규칙을 발견할 수 있다.
  • 종이 접기의 굴곡 수는 항상 홀수가 나온다.
  • 여기서 굴곡의 중간 위치 0을 기준으로 양옆 숫자 배열들은 위치와 숫자 반대 대칭 (?) 을 이룬다.
  • 요약하자면 0은 1, 1은 0, 그리고 위치도 정반대이다.
• 입출력 예 2번과 3번 그림을 통해 확인해보자.

입출력 예 2

입출력 예 3

• 그림과 같이 반대 대칭 (?) 형태를 이루는 것을 확인해보자.
  • 1번 위치 값은 마지막 위치 (7번) 값과 반대 (0과 1)
  • 2번 위치 값은 마지막 - 1 위치 (6번) 값과 반대 (0, 1)
  • 3번 위치 값은 마지막 -2 위치 (5번) 값과 반대 (1, 0)

 

Code

public static int[] solution(int n) {
    StringBuilder sb = new StringBuilder("0");
 
    while ((--n) > 0) {
        String str = sb.toString();
        
        sb.append(0);
        
        for (int i = str.length() - 1; i >= 0; i--) {
            if (str.charAt(i) == '1')
                sb.append(0);
            else
                sb.append(1);
        }
    }
 
    int[] result = new int[sb.length()];
 
    for (int i = 0; i < result.length; i++)
        result[i] = sb.charAt(i) - '0';
 
    return result;
}

 

결과