[Baekjoon/JAVA] 9214번 - 첫 번째 항

[백준] Baekjoon Online Judge

문제로 이동

 

문제

다음 순열에서 이어지는 항은 무엇일까?

1, 11, 21, 1211, 111221, ...

규칙은 이러하다. 어떤 항이 있을 때 다음 항을 만드는 방법은 현재 항을 같은 숫자들로 구분되도록 쪼갠 후, 각 숫자가 반복되는 횟수를 앞에 붙이는 것이다. 예를 들어 21은 "한 개의 2, 한 개의 1"이므로 다음 항은 1211이 된다. 이와 같은 규칙에 따라서 111221 뒤에는 312211이 오게 된다(세 개의 1, 두 개의 2, 한 개의 1).

다음 항뿐 아니라 이전 항도 알아낼 수 있다. 2221은 그 자체로 "두 개의 2, 두 개의 1"이 있었다는 뜻이므로 이전 항은 2211이다. 또한 2211의 이전 항도 221임을 알 수 있다. 그런데 221의 이전 항은 존재하지 않는다. 왜냐면 이 값을 정보로 나타낼 수 있는 수가 없기 때문이다. 또한 2212도 이전 항이 없는데, "두 개의 2, 한 개의 2"인 수는 222인데 이 수의 다음 항은 2212가 아니라 32여야 하기 때문이다.

어떤 항이 주어졌을 때, 위 규칙을 따르면서 이 항이 존재하는 수열의 첫 번째 항을 찾아내는 프로그램을 작성하시오. 첫 번째 항은 절대 이전 항이 존재하지 않는다. 예를 들어 문제가 2221이면 답은 221이고, 문제가 312211이면 답은 1이다. 22처럼 이전 항이 자신과 동일할 경우는 예외로 그 자신이 첫 번째 항이 될 수 있다.

 

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 줄에 걸쳐 최대 100글자의 정수 n이 주어지며, 입력의 끝은 0으로 주어진다.

 

출력

각 n마다 첫 번째 항을 줄마다 양식에 맞춰서 출력한다.

 

---

예제 입력	예제 출력
2221 312211 22 0	Test 1: 221 Test 2: 1 Test 3: 22

---

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int count = 1; // 테스트 케이스 번호

        while (true) {
            String n = in.next(); // 최대 100글자의 정수 n

            // 입력의 끝은 0
            if (n.equals("0")) break;

            // n의 첫 번째 항 알아내기
            while (true) {
                StringBuilder sb = new StringBuilder();

                // 정수의 길이가 홀수인 경우 이전 항이 존재하지 않는다.
                if (n.length() % 2 == 1) break;

                // 이전 항 알아내기
                for (int i = 0; i < n.length(); i += 2) {
                    int idx = Integer.parseInt(n.charAt(i) + "");

                    for (int j = 0; j < idx; j++)
                        sb.append(n.charAt(i + 1));
                }

                // 첫 번째 항을 찾음
                if (n.equals(sb.toString())) break;

                n = sb.toString();
            }

            // 출력
            System.out.println("Test " + count++ + ": " + n);
        }
    }
}

정수 n은 100글자나 되기 때문에 String으로 값을 입력 받았다. 또한 이전 항을 구할 때 문자열의 변동이 잦기 때문에 StringBuilder을 사용했다.

 

// 정수의 길이가 홀수인 경우 이전 항이 존재하지 않는다.
if (n.length() % 2 == 1) break;

n의 이전 항을 구하기 위해서는 반복된 횟수(짝수 번째 숫자)와 반복된 숫자(홀수 번째 숫자)가 필요하다. 그렇기 때문에 만약 입력받은 n의 길이가 홀수라면 마지막 숫자는 짝이 없기에 이전 항을 구할 수 없다.

 

 // 이전 항 알아내기
for (int i = 0; i < n.length(); i += 2) {
	int idx = Integer.parseInt(n.charAt(i) + "");

	for (int j = 0; j < idx; j++)
		sb.append(n.charAt(i + 1));
}

정수 n의 0, 2, 4 ..... 앞에서부터 짝수 번째 자리의 숫자들은 바로 뒤의 숫자가 이전 항에서 몇 개가 연속으로 있었는지를 알려주는 수이다. 그렇기에 짝수 번째의 숫자만큼 바로 뒤의 홀수 번째 숫자를 반복해서 문자열(sb)에 추가해줬다.

 

// 첫 번째 항을 찾음
if (n.equals(sb.toString())) break;

위의 과정을 통해 얻은 이전 항이 현재의 항과 같다면 아무리 반복해서 이전 항을 구해도 자기자신만 나오게 되고, 이는 이미 현재의 행을 찾았다는 것이 된다.

 

만약 위의 2개의 if문에 걸리지 않는다면 이번에 구한 이전행을 n에 대입한 뒤 위의 과정을 다시 반복하게 된다.