백준 - 좋은 수열

문제 설명

숫자 1,2,3으로만 N길이의 좋은 수열을 만들 수 있는 수열중 가장 작은 수를 반환하는 문제이다.

여기에서의 좋은 수열은 인접한 두 개의 부분수열이 동일하지 않는 수열이다.

그리고 나쁜 수열은 인접한 두 개의 부분수열이 동일한 경우의 수열이다.

ex)

33

32121323

123123213

주의사항

• 길이가 n자리를 만드는 것에 유념해아햔다. int 또는 long 형의 타입도 커버할 수 없다.
• 인접한 길이의 부분 수열 로직을 잘 작성해야한다.
  • 앞자리에서 시작하는 부분 수열만을 체크하는 것이 아니라 중간 부분에서 시작한 부분수열에도 동일한 수열이 존재하면 그것은 나쁜 수열로 인식해야 한다.

풀이

  static int n;
	static int arr[] = {1, 2, 3};

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

		n = Integer.parseInt(reader.readLine());

		/**
		 * 1,2,3으로 이루어지는 n 자리 수열을 만들 때, 좋은 수열 중 가장 작은 수를 출력하는 문제
		 * - n자리를 만들 때 2/n까지의 길이를 만들면서 같은 것이 있는지 판별하면 시간초과에 안걸릴까? 라는 의문... 
		 */

		makeSequence(0, "");
	}

	/**
	 *
	 * @param cnt
	 * @param result : int 형으로 *10을해서 1의자리를 더해준다면 overflow가 발생한다. 왜나하면 최대 80자리이기 때문이다!
	 */
	static void makeSequence(int cnt, String result) {
		if (cnt == n) {
			System.out.println(result);
			System.exit(0);
			return;
		}

		for (int i = 1; i <= 3; i++) {
			if (isBadSequence(result+i)) {
				continue;
			}
			makeSequence(cnt + 1, result+i);
		}
	}

	/**
	 * 인접한 두개의 부분수열이 동일하면 그것을 나쁜 수열이라 인지한다.
	 * @param str
	 * @return
	 */
	static boolean isBadSequence(String str) {
		for (int i = 0; i < str.length()- 1; i++) {
			for (int j = i + 1; j <= str.length(); j++) {
				String front = str.substring(i, j);
				if (j + front.length() > str.length()) {
					break;
				}
				String next = str.substring(j, j + front.length());

				if (front.equals(next)) {
					return true;
				}
			}
		}

		return false;
	}