[84. Largest Rectangle in Histogram] - 이 문제 겁나 어렵습니다.
2일 이상 시간이 소모되었지만 문제가 안 풀려서 미쳐버릴 것 같습니다.

풀이 진행

풀이를 진행하는데 필자는 조건이 크게 3가지로 나뉜다고 생각 되었다.
1. 현재 넓이가 구해지는 세로보다 클 때
2. 현재 넓이가 구해지는 세로보다 동일할 때
3. 현재 넓이가 구해지는 세로보다 작을 때

이유

1의 이유는 값이 크면 조건에 따라 세로 값이 바뀌기 때문이다.
세로 값이 현제 적용되는 세로 값보다 작게 차이가 나서 넓이가 작으면 바뀌지 않지만
높이가 넓이 만큼 크면 넓이를 바꿔서 기억해야 되기 때문이다.

2의 이유는 값이 동일하면 무지성으로 더해주면 되기 때문이다.

3의 이유는 값이 작으면 더 이상 증가하지 못하고 넓이는 고정되기 때문이다.

기본 틀 제작

일단 값을 저장할 변수형태부터 정하고 제작하자
처음 생각한 것은 int[,]형태 첫 번째 값에는 세로가 되는 값, 두 번째는 가로의 갯수를 넣었다.
하지만 계속 진행함으로 써 문제가 발생한다. 세로가 되는 값이 몇번째 있는지 몰라서 for문으로 찾아야 되는 것이다.

그래서 다음으로 정한것이 List<int[]>이다. 이는 .Contains를 통해 해당값이 있는지 확인이 가능하기 때문이라고 생각하여 진행하였다. 하지만 생각과 다르게 배열을 .Contains로 확인을 할려면 똑같이 int형 배열을 만들어서 비교해야 되기에 foreace돌려 수동으로 확인했다...

{
    List<int[]> list = new List<int[]>();
    int sum = 0;
    for (int i = 0; i < heights.Length; i++)
    {
        sum = sum < heights[i] ? heights[i] : sum;
        List<int[]> deleteList = new List<int[]>();
        if (i == 0)
            list.Add(new int[] { heights[i], 1 });
        else
        {
            int newIndex = 0;
            bool isNum = false;
            foreach (int[] n in list)
                if (n[0] == heights[i]) { isNum = true; break; }
            if (!isNum)
            {
                int[] newNum = new int[] { heights[i], 1 };
                list.Add(newNum);
                newIndex = list.IndexOf(newNum);
                for (int j = 0; j < list.Count; j++)
                {
                    if (list[j][0] < heights[i])
                        list[j][1]++;
                    else if (list[j][0] > heights[i])
                    {
                        list[newIndex][1]++;
                        deleteList.Add(list[j]);
                    }
                }
            }
            else
            {
                for (int j = 0; j < list.Count; j++)
                {
                    if (list[j][0] <= heights[i])
                        list[j][1]++;
                    else if (list[j][0] > heights[i])
                        deleteList.Add(list[j]);
                }
            }
        }
        foreach (int[] n in list)
            sum = sum < n[0] * n[1] ? n[0] * n[1] : sum;
        foreach (int[] n in deleteList)
            list.Remove(n);
    }
    return sum;
}

하지만 이 코드를 사용하면 높은 값들이 삭제되어 버려 낮은값이 들와왔을때 제대로 카운트가 안된다..

이를 해결한 다음코드

List<int[]> list = new List<int[]>();
List<bool> isAddNum = new List<bool>();
int sum = 0;
for (int i = 0; i < heights.Length; i++)
{
    sum = sum < heights[i] ? heights[i] : sum;
    if (i == 0)
    {
        list.Add(new int[] { heights[i], 1 });
        isAddNum.Add(true);
    }
    else
    {
        list.Add(new int[] { heights[i], 0 });

        isAddNum.Add(true);

        for (int j = 0; j < list.Count; j++)
        {
            if (list[j][0] <= heights[i] && isAddNum[j] && j != i)
                list[j][1]++;
            else if (list[j][0] > heights[i] && isAddNum[j])
            {
                isAddNum[j] = false;
                list[i][1]++;
            }
            else if (list[j][0] == heights[i] && isAddNum[j])
            {
                list[j][1] = 0;
                for (int n = 0; n < list.Count; n++)
                {
                    if (list[n][0] >= heights[i])
                    {
                        list[j][1]++;
                    }
                    else if (list[n][0] < heights[i])
                        list[j][1] = 0;
                }
            }
        }
    }
    foreach (int[] n in list)
        sum = sum < n[0] * n[1] ? n[0] * n[1] : sum;
}
return sum;

이 코드는 정상적으로 작동된다. 하지만 코드를 제출하면 런타임에러가..... 그래서 최적화를 시도하였다. for문을 줄이고 변수도 줄이고 다양한 시도를 하였다.

그 결과

List<int[]> list = new List<int[]>();
List<int> isLimitNum = new List<int>();
int sum = 0;
for (int i = 0; i < heights.Length; i++)
{
    sum = sum < heights[i] ? heights[i] : sum;
    if (i == 0)
    {
        list.Add(new int[] { heights[i], 1 });
        isLimitNum.Add(-1);
    }
    else
    {
        list.Add(new int[] { heights[i], 0 });
        isLimitNum.Add(-1);
        for (int j = 0; j < list.Count; j++)
        {
            if (list[j][0] <= heights[i] && (isLimitNum[j] == -1 || isLimitNum[j] >= heights[i]))
                list[j][1]++;
            else if (list[j][0] > heights[i] && (isLimitNum[j] == -1 || isLimitNum[j] >= heights[i]))
            {
                list[i][1]++;
                isLimitNum[j] = heights[i];
            }
        }
    }

    foreach (int[] n in list)
        sum = sum < n[0] * n[1] ? n[0] * n[1] : sum;
}
return sum;

많이 줄어들었고 깔끔해졌다. 하지만 이 코드도 런타임 에러가 발생한다. 나는 이보다 더 뛰어난 코드가 생각나질 않아서 결국 답안을 확인했다. (5일간 이것만 잡고 생각하니 더이상 나의 한계라고 느꼈다...)

AlgoTree

여기를 참조하면 정말 깔끔하게 설명되어 있으며 최적화도 너무 잘되어 있다. 이 문제를 해결하기 위해 선택한 변수타입은 Stack이며 2개의 Stack을 이용해 하나는 값을 다른 하나는 포지션을 기억 후 작은 값이 들어오면 큰 값과 포지션들을 버리면서 넓이를 구해 answer에 저장하는 형태이다.

나도 Stack을 생각하였지만 값을 찾는 방법이 오래걸릴 것 같았으며 포지션을 어떻게 보관해야될지 생각을 못했다. 하지만 이걸 확인한 후에는 머리가 맑아진 느낌이며 다음에는 꼭 이 방법으로 문제를 해결해야 겠다는 마음을 먹었다...