[Hackerrank 문제 풀이] Equal Stacks

Junu Kim·2025년 11월 17일

Java hackerrank

코딩테스트 문제 풀이 (백준, HackerRank)

목록 보기

39/46

[Stack] Equal Stacks

난이도: ★★☆☆☆ • solved on: 2025-11-17

문제 요약

문제 유형: 스택 시뮬레이션, 구현
요구사항: 세 개의 스택에서 top 요소를 제거해 세 스택의 높이가 동일해질 수 있는 최대 높이를 구해야 한다.

사용 개념

자료구조
- List (스택처럼 사용)
알고리즘/기법
- 누적합 관리
- top 제거 시뮬레이션
- 인덱스 기반 최적화
핵심 키워드
- equal height
- height reduction
- sum-driven selection

풀이 아이디어 및 코드

방법 1 : 처음 풀이 (remove(0) 기반 시뮬레이션)

문제 분해

각 스택의 총합을 계산한다.

세 합이 같아질 때까지 가장 큰 합을 가진 스택에서 top 원소를 제거한다.

top이 리스트의 첫 요소이므로 remove(0)으로 pop을 대체한다.
핵심 로직 흐름
while (모든 합이 동일하지 않으면):
    가장 큰 합을 가진 스택 선택
    해당 스택의 top 제거(remove(0))
예외 처리

스택 중 하나라도 비면 결과는 0

코드

    public static int equalStacks(List<Integer> h1, List<Integer> h2, List<Integer> h3) {
        // Write your code here
        int[] sumArr = {0, 0, 0, 0}; 
        for(int item : h1){
            sumArr[1] += item;
        }
        
        for(int item : h2){
            sumArr[2] += item;
        }
        
        for(int item : h3){
            sumArr[3] += item;
        }
             
        while(!(sumArr[1]==sumArr[2] && sumArr[2]==sumArr[3])){
            if(sumArr[1] <= sumArr[2]){
                if(sumArr[2] <= sumArr[3]){
                    sumArr[3] -= h3.get(0);
                    h3.remove(0);
                } else {
                    sumArr[2] -= h2.get(0);
                    h2.remove(0);
                }
            } else {
                if(sumArr[1] <= sumArr[3]){
                    sumArr[3] -= h3.get(0);
                    h3.remove(0);
                } else {
                    sumArr[1] -= h1.get(0);
                    h1.remove(0);
                }
            }
        }
        return sumArr[1]; 
    }

방법 2 : 개선 풀이 (인덱스 이동 방식으로 remove 비용 제거)

문제 분해

리스트에서 remove(0)은 매번 전체를 shift하여 O(n) 비용이 발생한다.

따라서 top 제거를 인덱스 증가(i++)로만 처리하여 제거 비용을 없앤다.

세 스택의 총합만 갱신하며 진행한다.
핵심 로직 흐름
index1, index2, index3 각 0에서 시작
while (세 높이가 같지 않으면):
    현재 가장 큰 높이를 가진 스택에서 index++ 적용
예외 처리

인덱스가 리스트 끝에 도달하면 스택은 비게 되며 결과는 0 (첫 풀이와 동일)

코드

public static int equalStacks(List<Integer> h1, List<Integer> h2, List<Integer> h3) {
    int s1 = h1.stream().mapToInt(i -> i).sum();
    int s2 = h2.stream().mapToInt(i -> i).sum();
    int s3 = h3.stream().mapToInt(i -> i).sum();

    int i1 = 0, i2 = 0, i3 = 0;

    while (!(s1 == s2 && s2 == s3)) {
        int max = Math.max(s1, Math.max(s2, s3));
        if (max == s1) s1 -= h1.get(i1++);
        else if (max == s2) s2 -= h2.get(i2++);
        else s3 -= h3.get(i3++);
    }
    return s1;
}

시간·공간 복잡도

방법 1 (최초 풀이)

시간 복잡도: O(N²) (remove(0) = O(N) × 반복)
공간 복잡도: O(1)

방법 2 (개선 풀이)

시간 복잡도: O(N) (각 스택을 최대 한 번씩만 순회)
공간 복잡도: O(1)

어려웠던 점

처음에는 리스트의 순서가 bottom to top이라고 해석해서 인덱싱을 잘못 했다.
전체 높이를 기준으로 제거하는 로직에 대해 확신이 없어 답안을 맞추고도 확신이 없었다. (더 개선된 풀이는 없었을까?)

배운 점 및 팁

remove(0)은 리스트 전체를 재배치하기 때문에 비효율적이다. (제거하고자 하는 인덱스를 기준으로 한 칸씩 땡겨오는 방식)
h1.stream().mapToInt(i -> i).sum()의 방식을 통해 리스트의 전체 합을 구하는 방식의 가독성을 높일 수 있다.
각 메소드의 의미와 흐름
1. h3.stream()
  리스트 h3를 Stream 형태로 변환한다. → 리스트를 하나씩 순회할 수 있는 “흐름”이 생성된다. (기존에는 직접 for문으로 접근해야했다.)
1. .mapToInt(i -> i)
  Stream 안에 있는 Integer 객체를 int 형으로 변환한다.
- (i -> i) 라는 람다식은 “원소 i를 그대로 int로 변환한다”는 의미
1. .sum()
  이제 int 형태의 스트림이 되었기 때문에
  .sum()을 호출하면 모든 값을 더한 합이 나온다.
java.util.stream interface를 활용하면 리스트 내의 값들에 대한 연산을 더 쉽게 할 수 있다. (Stream (Java Platform SE 8) )