FENCE

구현 소스

#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>

using namespace std;

const int MAX_BUFFER_SIZE = 1024;
vector<int> fenceHeights;

int getMaxArea(int start, int end);
int getCenterMax(int start, int end, int mid);
void splitStringWithDelim(char* source, vector<int> &result, char delim, int maxSize);

int main()
{
	int caseNum = 0, elNum = 0;
	char inputBuffer[MAX_BUFFER_SIZE];

	cin >> caseNum;

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		fenceHeights.clear();

		cin >> elNum;
		cin.ignore();

		cin.getline(inputBuffer, MAX_BUFFER_SIZE);

		splitStringWithDelim(inputBuffer, fenceHeights, ' ', MAX_BUFFER_SIZE);

		int ret = getMaxArea(0, fenceHeights.size() - 1);

		cout << ret << endl;
	}
}

int getMaxArea(int start, int end)
{
	if (start == end) return fenceHeights[start];

	int mid = (start + end) / 2;

	int leftMax = getMaxArea(start, mid);
	int rightMax = getMaxArea(mid + 1, end);
	int centerMax = getCenterMax(start, end, mid);
	
	int ret = max(leftMax, rightMax);
	ret = max(ret, centerMax);

	return ret;
}

int getCenterMax(int start, int end, int mid)
{
	int low = mid, high = mid;
	int height = fenceHeights[mid];
	int area = fenceHeights[mid];

	while (start < low || high < end)
	{
		if (high < end && (low == start || fenceHeights[low - 1] < fenceHeights[high + 1]))
		{
			high++;

			height = min(height, fenceHeights[high]);
			area = max(area, height * (high - low + 1));
		}
		else
		{
			low--;
			
			height = min(height, fenceHeights[low]);
			area = max(area, height * (high - low + 1));
		}
	}

	return area;
}


void splitStringWithDelim(char* source, vector<int> &result, char delim, int maxSize)
{
	char *buf = new char[256]();
	int sourceIdx = 0;
	int bufIdx = 0;

	for (sourceIdx = 0; sourceIdx < maxSize; sourceIdx++)
	{
		if (source[sourceIdx] == delim || source[sourceIdx] == '\0')
		{
			// copy buffered string to result array
			buf[bufIdx] = '\0';
			result.push_back(atoi(buf));

			// if source string is end, break for loop
			if (source[sourceIdx] == '\0') break;

			bufIdx = 0;
		}
		else
		{
			buf[bufIdx] = source[sourceIdx];
			bufIdx++;
		}
	}

	return;
}

중복 코드 제거하기 전

if (low == start)
		{
			if (high == end)
			{
				break;
			}
			else
			{
				high++;

				height = min(height, fenceHeights[high]);

				int nextArea = height * (high - low + 1);
				area = max(area, nextArea);
			}
		}
		else if(high == end)
		{
			low--;

			height = min(height, fenceHeights[low]);

			int nextArea = height * (high - low + 1);
			area = max(area, nextArea);
		}
		else
		{
			if (fenceHeights[low - 1] < fenceHeights[high + 1])
			{
				high++;

				height = min(height, fenceHeights[high]);

				int nextArea = height * (high - low + 1);
				area = max(area, nextArea);
			}
			else
			{
				low--;

				height = min(height, fenceHeights[low]);

				int nextArea = height * (high - low + 1);
				area = max(area, nextArea);
			}
		}              

중복 코드 제거한 후

if (high < end && (low == start || fenceHeights[low - 1] < fenceHeights[high + 1]))
		{
			high++;

			height = min(height, fenceHeights[high]);
			area = max(area, height * (high - low + 1));
		}
		else
		{
			low--;
			
			height = min(height, fenceHeights[low]);
			area = max(area, height * (high - low + 1));
		}

- 이번 문제는 왼쪽 부분문제와 오른쪽 부분문제 말고 3번째 부분문제, 즉 왼쪽과 오른쪽 모두에 걸친 부분문제를 해결하는 데 애를 먹었다. 다. 분할 정복으로 구현하였는데, 절반 나누어 왼쪽 부분문제의 가장 큰 너비 값과 오른쪽 부분문제의 가장 큰 너비 값을 비교하여 큰 쪽을 택하는 전략이다. 그런데 왼쪽과 오른쪽 모두에 걸쳐있는 너비를 어떻게 계산할지 난감하였다. 왼쪽의 가장 큰 너비값을 가지는 인덱스(start 와 end) 와 오른쪽의 그것을 비교하여 왼쪽의 end와 오른쪽의 start 가 겹치면 둘을 더하는 건 어떨까 생각하였다. 그래서 Range 클래스를 생각했던 것이었다. 이 방식으로 코딩을 하다가 너무 산으로 가는 것 같아서 중도에 그만두었다.

- 결국 종만북을 조금 참고하였는데, 거기는 양쪽에 걸치는 너비를 따로 구하는 방식을 쓰고 있었다.  나도 그런 방식으로 구해서 getCenterMax() 함수를 새로 만들었다. 그래서 왼쪽 부분문제와 오른쪽 부분 문제는 getMaxArea() 로 너비를 구하고 가운데는 getCenterMax() 로 너비를 구하였다.

- getCenterMax() 를 구현할 때 애를 먹은 게 배열의 인덱스에 관한 것이었다. 처음에는 (배열의 처음 인덱스) 를 start, (배열의 마지막 인덱스 + 1) 을 end로 잡았는데 getMaxArea(start, end) 를 호출할 때 그냥 end 로 넣어버린 것이었다. 그래서 새로 호출된 getMaxArea() 에서는 fenceHeights[end] 가 무시되는 현상이 발생하였다. 그래서 end 의 정의를 (배열의 마지막 인덱스) 로 바꾸었다.

- getCenterMax()를 구현할 때 또 하나의 문제는 중복 코드였다. mid 로부터 범위를 넓혀가는 데 start <= low && high <= end 범위를 유지하면서 low - 1 과 high + 1 의 값에 접근해야 했다. low == start 인 경우 low - 1 에 접근하면 원소가 없어서 오류가 난다. 그래서 low == start 일 때와 high == end 일 때를 예외처리 해야 했는데 코드를 중복시키는 방법 말고는 생각나는 방법이 없었다. 종만북을 보니 내가 "while(start <= low && high <= end)" 로 구현한 것과 달리 "while(start < low || high < end)" 로 구현하였다. 이렇게 하면 low == start 의 경우와 high == end 의 경우를 막을 수 있다. 또한 && 대신에 || 를 사용하여 low, high 둘 중 하나가 경계에 다다랐다 하더라도 다른 쪽이 경계에 도달하지 않았다면 while 문은 계속 진행될 수 있다. 또 어느 쪽으로 범위를 확장할 지 판단하는 로직에서 "if (high < end && (low == start || fenceHeights[low - 1] < fenceHeights[high + 1])" 로 구현하여 low == start 인 경우 else 문 내에서 연산하는 "low--" 에 접근하지 못하도록 하였다. 

FenceInput.txt

FenceOutput.txt