내일배움캠프 25일차 TIL - 알고리즘 문제 풀이

leetcode에서 제공하는 알고리즘 문제중, 하나를 풀고 해설을 읽어보았습니다.

 

문제는 이러합니다.

 

정수형 숫자 배열 height 가 주어지며, 가로의 길이는 모두 1이라고 할때, 여기서 넓이가 가장 큰 직사각형을 구하는 문제입니다.

이때, 배열의 조건은 다음과 같습니다.

• 1 <= heights.length <= 10^5
• 0 <= heights[i] <= 10^4

---

먼저, 처음 저의 풀이는 자신의 우측 배열을 확인한 후, 이 배열의 값이 자신보다 크거나 같으면 길이를 1 늘리고, 그렇지 않으면 반복문을 종료합니다.

이후 저장된 길이와 자신의 높이를 곱해서 넓이를 구한 뒤, 저장된 최대값과 비교하여 저장합니다.

 

이 과정을 배열 전체에 반복하여 가장 큰 넓이를 구합니다.

public class Solution 
{
    public int LargestRectangleArea(int[] heights) 
    {
        int maxArea = 0;

        for(int i = 0; i < heights.Length; i ++)
        {
            int length = 1;

            for(int j = i + 1; j < heights.Length; j ++)
            {
                if(heights[i] > heights[j])
                {
                    break;
                }

                length ++;
            }

            int area = length * heights[i];

            if(area > maxArea)
            {
                maxArea = area;
            }
        }

        return maxArea;
    }
}

 

실행 결과, [2, 1, 2] 배열에서 오류가 발생하였습니다.

이 경우, 자신 우측만 보기 때문에 가장 큰 값을 2로 정하게 됩니다.

2, 1 ,2 배열에서 가장 큰 값은 1 X 3 값인 3이기 때문에 오류가 발행합니다.

 

따라서 좌측값을 확인하는 for문을 추가하였습니다.

좌측값은 1씩 작아지는 반복문에서 0이 나올때 까지 반복하며, 마찬가지로 좌측값이 자신보다 작을경우 종료, 클경우 길이를 1 늘리는 방식으로 작동합니다.

public class Solution 
{
    public int LargestRectangleArea(int[] heights) 
    {
        int maxArea = 0;

        for(int i = 0; i < heights.Length; i ++)
        {
            int length = 1;
            int sameHeight = 0;
            
            for(int j = i + 1; j < heights.Length; j ++)
            {
                if(heights[i] > heights[j])
                {
                    break;
                }

                length ++;
            }

            for(int k = i - 1; k >= 0; k --)
            {
                if(heights[i] > heights[k])
                {
                    break;
                }

                length ++;
            }

            int area = length * heights[i];

            if(area > maxArea)
            {
                maxArea = area;
            }
        }

        return maxArea;
    }
}

 

실행 결과, 시간 초과가 발생하였습니다.

알고리즘문제는 케이스당 제한시간이 존재하기 때문에, 처리시간이 길어지면 실패하게됩니다.

이 경우, 8783 으로 배열을 꽉 채운 테스트 케이스에서 실패하였습니다.

 

내용을 확인한 후, 우측값을 확인할 때, 같은값이 연속해서 나올경우 다음 연산은 현재 연산과 동일한 값이 나온다는것을 깨달았습니다.

 

따라서 우측값을 확인할 때, 현재 연산중인 값이 연속으로 나올경우 그만큼 연산을 건너뛰도록 설계해보았습니다.

→ 배열이 (5, 5, 5, 4, 2) 형태일경우, 첫번째 연산 종료후, i 에 3이 더해져 4부터 연산을 시작합니다.

public class Solution 
{
    public int LargestRectangleArea(int[] heights) 
    {
        int maxArea = 0;

        for(int i = 0; i < heights.Length; i ++)
        {
            int length = 1;
            int sameHeight = 0;

            if(heights[i] == 0)
            {
                continue;
            }

            for(int j = i + 1; j < heights.Length; j ++)
            {
                if(heights[i] > heights[j])
                {
                    break;
                }

                if(heights[i] == heights[j] && heights[j-1] == heights[j])
                {
                    sameHeight++;
                }

                length ++;
            }

            for(int k = i - 1; k >= 0; k --)
            {
                if(heights[i] > heights[k])
                {
                    break;
                }

                length ++;
            }

            int area = length * heights[i];

            if(area > maxArea)
            {
                maxArea = area;
            }

            i = i + sameHeight;
        }

        return maxArea;
    }
}

 

이 코드를 사용하였을때, 문제풀이에 성공하였습니다.

 

이후, 솔루션 코드를 확인하고 분석하였습니다.

public class Solution 
{
    public int LargestRectangleArea(int[] heights) 
    {
        int n = heights.Length;
        int max = 0;
        var stack = new Stack<int>();

        for(int i = 0; i <= n; i++)
        {
            var height = i < n ? heights[i] : 0;

            while(stack.Any() && heights[stack.Peek()] > height)
            {
                var currHeight = heights[stack.Pop()];
                var prevIndex = stack.Count == 0 ? -1 : stack.Peek();
                
                max = Math.Max(max, currHeight * (i - 1 - prevIndex));
            }

            stack.Push(i);
        }
        
        return max;
    }
}

솔루션 코드의 작동방식은 이러합니다

 

먼저, 확인할 인덱스 값을 저장할 스택을 만들어줍니다.

이후 for문을 사용하여 배열의 모든 값에 접근합니다.

 

두번째 반복문은 스택에 값이 단 하나라도 있으며, 현재 인덱스에 저장된 높이값이 스택의 가장 마지막에 저장된 인덱스의 높이값보다 클 때 작동합니다.

 

i = 0 일때, 스택은 무조건 비어있음으로 while 문은 작동하지 않습니다.

 

다음 인덱스부터는 이전 인덱스와 높이를 비교하여 while 문의 작동 여부를 결정합니다.

직전 인덱스의 높이값이 현재 높이값보다 크면 while 문이 작동합니다.

 

 

while 문에서는 먼저, 스택의 값을 Pop() 하여 스택에 쌓인 마지막 값을 현재 높이값에 저장하고 그 스택을 삭제합니다.

이후, 스택에 쌓인 값이 없으면 -1, 있으면 다음값의 인덱스를 prevIndex에 저장합니다.

이때는 Peek를 사용하기 때문에 값이 삭제되지 않습니다.

 

다음 현재값과 pop 인덱스의 높이 * (현재 인덱스 - 1 - 이전 인덱스값) 을 사용하여 넓이를 계산합니다.

이후, 다시 스택의 마지막 값을 현재 인덱스의 높이와 비교하여 추가 연산 여부를 결정합니다.

 

이 방법을 통해 가장 큰 값을 반환해줍니다.

 

이 풀이를 보고, 알고리즘에 좀 더 익숙해져야 할 필요를 느꼈습니다.