BOJ-2661-좋은 수열 (백트래킹)

BOJ 2661 좋은수열

문제출저

풀이

• 처음에 빈 문자열(““)부터 시작해서 1, 2, 3을 하나씩 붙여나가면서 길이가 N인지 체크해준다.

• 단, 문자열의 길이를 하나씩 늘려줄때 늘려줄 문자열이 좋은 수열인지 확인해서,
  좋은 수열일 경우에만 늘려주도록 한다.
  처음에 무조건 N길이의 문자열을 만들어서 좋은 수열인지 확인했는데, 이럴 경우 시간초과가 발생했다.

  N길이의 좋은 수열을 만드는 코드는 아래와 같다.
  만약 N길이의 좋은 수열이 처음에 발견되었다면 그 다음으로는 진행이 되지 않도록 하였다.

    public  boolean makeSeq(String seq, int n) {
        if (seq.length() == n) {
            System.out.println(seq);
            return true;
        } else if (seq.length() > n) {
            return false;
        }
        for (int i = 1; i <= 3; i++) {
            if (isGoodSeq(seq + i) && makeSeq(seq + i, n)) {
                return true;
            }
        }
        return false;
    }
  

• 이제 N길이의 문자열이 좋은 수열인지를 확인해주어야한다.
  문자열 S에서 i부터 i + j까지가 검사대상 부분문자열(길이 j)이라고 하면, 좋은 수열인지 검사를 위해선
  i + j + 1부터 j + 2*j + 1까지 검사해주어야 한다.
  문자열의 substring, equals 함수를 이용하면 검사코드를 다음과 같이 작성할 수 있다.

	public  boolean isGoodSeq(String seq) {
		for (int i = 0, n = seq.length(); i < n; i++) {
			for (int j = 1; i + 2 * j <= n; j++) {
				if (seq.substring(i, i + j).equals(seq.substring(i + j, i + 2 * j))) {
					return false;
				}
			}
		}
		return true;
	}

소스코드

전체소스