JUNGOL/Intermediate_Coder/백트래킹-DFS/1027 : 좋은수열

Intermediate_Coder/백트래킹-DFS/좋은수열

---

문제                                            

숫자 1 2 3으로만 이루어지는 수열이 있다.

 

임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있으면, 

그 수열을 나쁜 수열이라고 부른다. 그렇지 않은 수열은 좋은 수열이다.

 

다음은 나쁜 수열의 예이다. (밑줄 부분때문에 나쁜 수열이다.)

33

32121323

123123213

 

다음은 좋은 수열의 예이다.

2

32

32123

1232123

 

길이가 N인 좋은 수열들을 N자리의 정수로 보아 그 중 가장 작은 수를 나타내는 수열을 구하는 프로그램을 작성하라.

예를 들면 1213121과 2123212는 모두 좋은 수열이지만 그 중에서 작은 수를 나타내는 수열 1213121이다.​

 

입력 형식                                     

입력파일은 숫자 N 하나로 이루어진다.

N은 1 이상 80 이하이다.

 

출력 형식                                     

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서

가장 작은 수를 나타내는 수열만 출력한다.

수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

 

입력 예                                        

7

 

출력 예                                        

1213121

---

GoodSequence.h

#include <iostream>

class GoodSequence : public Base
{
private:
	bool FindGoodSequence(int arr[], int n, int depth = 0);
	bool IsGoodPatern(int arr[], int idx);

protected:
	void Code() override;
};

 

GoodSequence.cpp

void GoodSequence::Code()
{
	int n;
	std::cin >> n;

	int* arr = new int[n];
	
	FindGoodSequence(arr, n);

	for (int i = 0; i < n; i++)
	{
		std::cout << arr[i];
	}

	delete[] arr;
}

/// <summary>
/// 좋은 수열을 찾아 반환한다.
/// </summary>
/// <param name="arr">배열(결과 수열)</param>
/// <param name="n">배열의 길이</param>
/// <param name="depth">깊이</param>
/// <returns>수열을 찾았는지 여부</returns>
bool GoodSequence::FindGoodSequence(int arr[], int n, int depth)
{
	if (depth == n)
	{
		return true;
	}

	for (int i = 1; i <= 3; i++)
	{
		arr[depth] = i;
		if (IsGoodPatern(arr, depth))
		{
			bool foundSequence{ FindGoodSequence(arr, n, depth + 1) };
			if (foundSequence)
			{
				return true;
			}
		}
	}

	return false;
}

/// <summary>
/// 현재 입력으로 패턴이 중복되는지 확인
/// </summary>
/// <param name="arr">배열</param>
/// <param name="idx">입력한 인덱스</param>
/// <returns>패턴이 중복이 없는지 여부</returns>
bool GoodSequence::IsGoodPatern(int arr[], int idx)
{
	// 첫 입력은 항상 참
	if (idx == 0) return true;
	// 직전 입력과 동일한 것 허용 X
	if (arr[idx - 1] == arr[idx]) return false;

	for (int i = idx - 1; i >= 0; i--)
	{
		// 패턴을 찾기 위해 입력된 값과 같은 값 위치 찾기
		if (arr[i] == arr[idx])
		{
			int leftIdx{ i }, rightIdx{ idx };
			int paternLength{ rightIdx - leftIdx };

			// 같은 값 위치에 패턴 길이 만큼이 안 나오면 참
			if (leftIdx + 1 < paternLength)
			{
				break;
			}

			// 패턴 검사
			while (--paternLength > 0)
			{
				if (arr[--leftIdx] != arr[--rightIdx])
				{
					break;
				}
			}
			
			// 모든 패턴이 일치한 경우 X
			if (paternLength <= 0)
			{
				return false;
			}
		}
	}

	return true;
}

 

---

실행 결과 Success(100)

---

 

코드 해설

- 가장 작은 패턴을 찾기

패턴을 1, 2, 3 순서대로 진행하면서 최대 길이에 도달한 경우 가장 작은 패턴을 찾은 것으로 간주하고 더 이상 찾는 것을 멈추고 값을 출력하도록 한다.

			bool foundSequence{ FindGoodSequence(arr, n, depth + 1) };
			if (foundSequence)
			{
				return true;
			}

 

- 중복된 패턴 거르기

입력된 값과 같은 값을 기존 값에서 찾고 해당 위치에서 왼쪽으로 진행하며 같은 패턴이 존재하는지 확인하여 좋은수열을 찾아낸다.

			// 패턴 검사
			while (--paternLength > 0)
			{
				if (arr[--leftIdx] != arr[--rightIdx])
				{
					break;
				}
			}
			
			// 모든 패턴이 일치한 경우 X
			if (paternLength <= 0)
			{
				return false;
			}

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermeditate_Coder/백트래킹-DFS/좋은수열-JUNGOL