JUNGOL/Intermediate_Coder/자료구조/1124 : 색종이(고)

코딩 테스트/JUNGOL 2021. 9. 15. 02:12

Intermediate_Coder/자료구조/색종이(고)

문제

가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다.

이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 붙인다.

이러한 방식으로 색종이를 한 장 또는 여러 장 붙인 후 도화지에서 검은색 직사각형을 잘라내려고 한다.

직사각형 또한 그 변이 도화지의 변과 평행하도록 잘라내어야 한다.

예를 들어 흰색 도화지 위에 세 장의 검은색 색종이를 <그림 1>과 같은 모양으로 붙였다.

<그림 1>에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 22×5=110이 된다.

반면 <그림 2>에 표시된 대로 검은색 직사각형을 잘라내면 그 넓이는 8×15=120이 된다.

검은색 색종이의 수와 각 색종이를 붙인 위치가 주어질 때 잘라낼 수 있는 검은색 직사각형의 최대 넓이를 구하는 프로그램을 작성하시오.

*주의. 직사각형은 정사각형을 포함한다.

입력 형식

첫째 줄에 색종이의 수가 주어진다. 이어 둘째 줄부터 한 줄에 하나씩 색종이를 붙인 위치가 주어진다.

색종이를 붙인 위치는 두 개의 자연수로 주어지는데 첫 번째 자연수는 색종이의 왼쪽 변과 도화지의 왼쪽 변 사이의 거리이고, 두 번째 자연수는 색종이의 아래쪽 변과 도화지의 아래쪽 변 사이의 거리이다.

색종이의 수는 100 이하이며, 색종이가 도화지 밖으로 나가는 경우는 없다.

출력 형식

첫째 줄에 잘라낼 수 있는 검은색 직사각형의 최대 넓이를 출력한다.

입력 예

3
3 7
15 7
5 2

출력 예

120

ColoredPaper3.h

#include <iostream>
#include <stack>
#include <vector>

using std::stack;
using std::vector;

class ColoredPaper3 : public Base
{
private:
	struct Point
	{
		Point(int x, int y, int width) : x(x), y(y), width(width) {}
		Point() : x(0), y(0), width(0) {}

		int x;
		int y;
		int width;
	};

	void FillArr(bool** arr, Point p);
	int CheckArea(bool** arr, stack<Point>& pointStack,
		vector<Point>& pointVector);
	int GetCurLineWidth(bool** arr, int x, int y);
	bool IsDuplicated(vector<Point>& pointVector, int x, int y, int width);
};

ColoredPaper3.cpp

void ColoredPaper3::Code()
{
	bool** arr = new bool*[100];
	for (int i = 0; i < 100; i++)
	{
		arr[i] = new bool[100];
		std::fill_n(arr[i], 100, false);
	}

	int n;
	std::cin >> n;

	stack<Point> pointStack;
	for (int i = 0; i < n; i++)
	{
		Point p;
		std::cin >> p.x >> p.y;
		pointStack.push(p);

		FillArr(arr, p);
	}

	vector<Point> pointVector;

	int maxArea{ 100 };
	while(!pointStack.empty())
	{
		int area{ CheckArea(arr, pointStack, pointVector) };
		if (area > maxArea)
		{
			maxArea = area;
		}
	}

	std::cout << maxArea;

	for (int i = 0; i < 100; i++)
	{
		delete[] arr[i];
	}
	delete[] arr;
}

/// <summary>
/// 입력된 위치에 색종이를 채워준다.
/// </summary>
/// <param name="arr">배열</param>
/// <param name="x">x 시작 인덱스</param>
/// <param name="y">y 시작 인덱스</param>
void ColoredPaper3::FillArr(bool** arr, Point p)
{
	for (int i = p.y; i < p.y + 10; i++)
	{
		for (int j = p.x; j < p.x + 10; j++)
		{
			arr[i][j] = true;
		}
	}
}

/// <summary>
/// 주어진 좌표에서 시작하는 최대 넓이를 확인하여 반환한다.
/// </summary>
/// <param name="arr">배열</param>
/// <param name="x">x 시작 인덱스</param>
/// <param name="y">y 시작 인덱스</param>
/// <returns>넓이</returns>
int ColoredPaper3::CheckArea(bool** arr, stack<Point>& pointStack,
	vector<Point>& pointVector)
{
	Point p{ pointStack.top() };
	pointStack.pop();

	pointVector.push_back(Point(p.x, p.y, p.width));

	int x{ p.x }, y{ p.y };
	int width{ p.width > 0 ? p.width : GetCurLineWidth(arr, x, y) };
	int count{ 0 };
	int lastAddedWidth{ 0 };

	int area{ 0 };
	for (int i = y; i < 100; i++)
	{
		if (arr[i][x])
		{
			int curWidth{ GetCurLineWidth(arr, x, i) };

			if (curWidth >= width)
			{
				count++;
				area = width * count;

				if (lastAddedWidth != curWidth
					&& !IsDuplicated(pointVector, x, y, curWidth))
				{
					pointStack.push(Point(x, i, curWidth));
					lastAddedWidth = curWidth;
				}
			}
			else
			{
				if (curWidth > 0 && !IsDuplicated(pointVector, x, y, curWidth))
				{
					pointStack.push(Point(x, y, curWidth));
				}
				break;
			}
		}
		else
		{
			for (int j = x; j < x + 10; j++)
			{
				if (arr[i][j])
				{
					int curWidth{ GetCurLineWidth(arr, j, i) };
					if (!IsDuplicated(pointVector, j, y, curWidth))
					{
						pointStack.push(Point(j, y, curWidth));
					}
					break;
				}
			}
			break;
		}
	}

	return area;
}

/// <summary>
/// 주어진 좌표의 너비를 반환한다.
/// </summary>
/// <param name="arr">배열</param>
/// <param name="x">x 시작 인덱스</param>
/// <param name="y">y 시작 인덱스</param>
/// <returns>해당 라인의 넓이</returns>
int ColoredPaper3::GetCurLineWidth(bool** arr, int x, int y)
{
	int width{ 0 };
	for (int i = x; i < 100; i++)
	{
		if (!arr[y][i])
		{
			break;
		}

		width++;
	}
	return width;
}

/// <summary>
/// 주어진 값이 이미 처리된 적 있는 값인지 여부를 반환한다.
/// </summary>
/// <param name="pointVector">처리된 값</param>
/// <param name="x">추가할 x 값</param>
/// <param name="y">추가할 y 값</param>
/// <param name="width">추가할 width 값</param>
/// <returns>중복 여부</returns>
bool ColoredPaper3::IsDuplicated(vector<Point>& pointVector, int x, int y, int width)
{
	for (size_t total = pointVector.size(), i = 0; i < total; i++)
	{
		if (pointVector[i].x == x && pointVector[i].y == y
			&& pointVector[i].width == width)
		{
			return true;
		}
	}
	return false;
}

실행 결과 Success(100)

코드 해설

- 주어진 영역에 대한 처리 방법

먼저, 예제에 대한 그림을 보면 (5, 2)가 주어질 때 x의 범위는 (5, 15)이고, y의 범위는 (2, 12)가 된다.

그런데 프로그램에서 이러한 방식의 처리는 굉장히 헷갈리게 된다.

현재 관심이 있는 것은 넓이 이므로 영역을 만들 수 있는 것을 1단위로 하여 입력을 받고 영역을 채운다.

	stack<Point> pointStack;
	for (int i = 0; i < n; i++)
	{
		Point p;
		std::cin >> p.x >> p.y;
		pointStack.push(p);

		FillArr(arr, p);
	}

- 입력에 대한 최대 넓이 구하기

기본적으로 입력된 정점이 최초 시작 좌표가 되며 해당 지점에서 부터 훑으면서 크기를 확인한다.

시작 지점에서의 너비와 이동한 좌표의 너비를 비교하여 동일하거나 큰 경우 같은 크기의 개수를 증가시키고 더 큰 경우엔 그 크기로 최대 넓이가 발생할 수 있으므로 해당 좌표를 스택에 등록한다.

이동한 지점의 너비가 작은 경우엔 시작 지점을 좌표에 더해 크기를 이동한 지점의 너비로 하여 스택에 다시 등록한다.

이를 통해 최초로 입력된 좌표에서 발생 가능한 새로운 좌표를 찾을 수 있다.

		if (arr[i][x])
		{
			int curWidth{ GetCurLineWidth(arr, x, i) };

			if (curWidth >= width)
			{
				count++;
				area = width * count;

				if (lastAddedWidth != curWidth
					&& !IsDuplicated(pointVector, x, y, curWidth))
				{
					pointStack.push(Point(x, i, curWidth));
					lastAddedWidth = curWidth;
				}
			}
			else
			{
				if (curWidth > 0 && !IsDuplicated(pointVector, x, y, curWidth))
				{
					pointStack.push(Point(x, y, curWidth));
				}
				break;
			}
		}

다만 이렇게만 처리하는 경우 다음과 같은 경우에 적절한 좌표를 체크하지 못 하게 된다.

이를 체크하기 위해 진행 방향에서 빈 공간이 나타나면 색종이의 크기 내에서 새로운 좌표를 탐색하도록 한다.

		else
		{
			for (int j = x; j < x + 10; j++)
			{
				if (arr[i][j])
				{
					int curWidth{ GetCurLineWidth(arr, j, i) };
					if (!IsDuplicated(pointVector, j, y, curWidth))
					{
						pointStack.push(Point(j, y, curWidth));
					}
					break;
				}
			}
			break;
		}

마지막으로 중복된 좌표가 등록되어 무한 루프에 빠지지 않도록 막기 위해 vector를 이용하여 중복 검사를 한다.

/// <summary>
/// 주어진 값이 이미 처리된 적 있는 값인지 여부를 반환한다.
/// </summary>
/// <param name="pointVector">처리된 값</param>
/// <param name="x">추가할 x 값</param>
/// <param name="y">추가할 y 값</param>
/// <param name="width">추가할 width 값</param>
/// <returns>중복 여부</returns>
bool ColoredPaper3::IsDuplicated(vector<Point>& pointVector, int x, int y, int width)
{
	for (size_t total = pointVector.size(), i = 0; i < total; i++)
	{
		if (pointVector[i].x == x && pointVector[i].y == y
			&& pointVector[i].width == width)
		{
			return true;
		}
	}
	return false;
}

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

NadanKim/CodingTest_JUNGOL

JUNGOL 코딩 테스트를 위한 저장소. Contribute to NadanKim/CodingTest_JUNGOL development by creating an account on GitHub.

github.com

문제출처

Intermediate_Coder/자료구조/색종이(고)-JUNGOL

저작자표시 비영리 변경금지

ABOUT ME

코딩시간 코딩시간

Intermediate_Coder/자료구조/색종이(고)

코드 해설

문제출처

티스토리툴바

ABOUT ME

Intermediate_Coder/자료구조/색종이(고)

코드 해설

문제출처

관련글 관련글 더보기

티스토리툴바