C# [HackerRank] Algorithm(Data Structures) - Equal Stacks

 

 

 

문제

 

 

 

 

 

 

문제 설명

 

스택과 유사한 구조로 만들어전 3개의 실린더가 있다.

 

각각의 실린더의 높이는 제각각인데 실린더의 요소로 구성된 숫자를 하나씩 제거하면서 3개의 실린더 높이를 동일하게 만드는 것이 최종 목표이다.

 

실린더는 아래의 그림과 같은 형태로 구성되고 맨 위에 위치하는 숫자에 해당하는 요소를 삭제해 가며 최종적으로는 같아진 높이의 값을 return 하면 되는 문제다.

 

 

실린더 예시

 

 

높이가 같아진 실린더 예시

 

 

최종적으로 같아진 높이는 5 이므로 5를 return 해주면 되는 문제다.

 

 

 

 

풀이 방법

 

 

먼저 각각의 실린더는 스택과 같은 구조로 이루어져있다.

 

함수에서 넘겨받는 매개 변수가 List로 이루어져 있기 때문에 각각의 리스트의 요소들을 먼저 스택에 담아주었다.

 

담는 과정에서 리스트를 그대로 담으면 스택의 특성 상 리스트의 첫번째 요소가 맨 밑으로 가기 때문에 리스트를 뒤집어준 다음 스택에 담는다.

 

 

 

실린더의 높이는 각 스택의 담겨있는 요소의 값을 모두 더해주고 3개의 실린더가 높이가 같아질때 까지 조건문을 돌리면서 스택의 요소를 Pop 해준다면 문제를 해결할 수 있다.

 

 

 

해당 코드

 

 

public static int equalStacks(List<int> h1, List<int> h2, List<int> h3)
{
        Stack<int> h1Stack = new Stack<int>();
        Stack<int> h2Stack = new Stack<int>();
        Stack<int> h3Stack = new Stack<int>();
        
        h1.Reverse();
        for(int i = 0; i < h1.Count; i ++)
        {
            h1Stack.Push(h1[i]);
        }
        
        h2.Reverse();
        for(int i = 0; i < h2.Count; i ++)
        {
            h2Stack.Push(h2[i]);
        }
        
        h3.Reverse();
        for(int i = 0; i < h3.Count; i ++)
        {
            h3Stack.Push(h3[i]);
        }
        
        int h1Sum = h1Stack.Sum();
        int h2Sum = h2Stack.Sum();
        int h3Sum = h3Stack.Sum();
        
        
        while(!(h1Sum == h2Sum && h2Sum == h3Sum))
        {
            if(h1Sum >= h2Sum && h1Sum >= h3Sum)
            {
                h1Sum -= h1Stack.Pop();
            }
            else if(h2Sum >= h1Sum && h2Sum >= h3Sum)
            {
                h2Sum -= h2Stack.Pop();
            }
            else
            {
                h3Sum -= h3Stack.Pop();
            }
            
        }
        return h1Sum;
}

 

 

처음에는 조건문을 돌리는 과정에서

(h1Sum >= h2Sum && h1Sum >= h3Sum) 에 해당하는 부분을

 

(h1Sum > h2Sum && h1Sum > h3Sum)로 작성했었다.

 

실린더의 높이가 같아진 상황을 비교할 필요가 없다고 생각해서 증감연산자를 >= 이 아니라 > 을 사용했지만 일부 테스트 케이스를 통과하지 못했다.

 

 

 

 

원인을 분석해보니

 

h1Sum = 10; h2Sum = 10; h3Sum = 5;

h1Sum = 15; h2Sum = 10; h3Sum = 15;

 

이러한 예시의 경우에서 첫번째 비교군의 크기가 같다면 무조건 else 쪽으로 빠지는 경우의 수를 확인할 수 있었다.

 

조건문을 조금 더 정교하게 다듬을 필요성을 느껴 증감 연산자를 수정했다.