알고리즘 스터디 (좋은수열[백준 2661])

박윤택·2022년 6월 21일
2

알고리즘

목록 보기
16/25

문제


문제 이해

  • N을 입력받는다.
  • 1, 2, 3으로만 이루어진 문자열로 이루어진다.
  • 제일 작은 수를 나타내는 수열을 출력해야한다.
  • 문자열을 뒤집어서 문자열 내부를 비교하여 좋은 수열을 찾는다.

코드

import java.io.*;
import java.util.*;

public class GoodSequence {
  static int N;
  static Integer candidates[] = { 1, 2, 3 };

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());

    make("");
  }

  // 수열 만드는 함수
  public static void make(String answer) {
    if (answer.length() == N) {
      System.out.println(answer);
      System.exit(0); // 완전히 종료
    }
    for (Integer candidate : candidates) {
      if (isGood(answer + candidate.toString()))
        make(answer + candidate.toString());
    }
  }

  // 좋은 수열인지 확인하는 함수
  public static boolean isGood(String sequence) {
  	// 뒤집어서 끝에서 부터 같은 길이 만큼이 연속되어 있는지 확인
    StringBuffer sb = new StringBuffer(sequence).reverse();
    for (int i = 1; i <= sb.length() / 2; i++) {
      if (sb.substring(0, i).equals(sb.substring(i, i * 2))) {
        return false;
      }
    }
    return true;
  }
}

코드 설명

1, 2, 3을 탐색하면서 해당 문자열에 더해가면서 좋은 수열이면 계속해서 진행하고 그렇지 않을 경우에는 거기서 종료하게끔 하여 좋은 수열을 찾는다.

핵심 부분은 해당 문자열을 뒤집은 다음 끝에서 부터 1씩 증가시켜가면서 해당 길이만큼이 반복되었는지 확인하는 부분이다.

0개의 댓글