HackerRank : Equal Stacks

https://www.hackerrank.com/challenges/equal-stacks/problem?isFullScreen=true

 

첫번째 시도

def equalStacks(h1, h2, h3):
    # Write your code here
    sh1,sh2,sh3= [],[],[]
    fh = []
    vh = 0
    for i in reversed(h1):
        vh+=i
        sh1.append(vh)
    vh = 0
    for i in reversed(h2):
        vh += i
        sh2.append(vh)
    vh = 0
    for i in reversed(h3):
        vh += i
        sh3.append(vh)

    for i in sh1:
        if i in sh2:
            fh.append(i)
    for i in fh:
        if i not in sh3:
            del i
            
    if len(fh) ==0:
        return 0
    else:
        return fh[-1]

 

바보같이 cumulative sum 을 사용하여 각 stack 의 가능한 높이를 다 구하고 3가지 리스트에서 같은값을 찾아 썻다.

그렇게 하니까 for 문을 5개나 써서 시간이 모자란 문제도 있었고 좀 복잡한 stack 에 대해서는 틀렸다.

 

충격은 이 문제는 stack 난이도 easy 라는거...ㅠㅜ 아직 갈길이 멀다...

 

약간의 도움을 받아 다시 생각해낸 방법은 pop 을 사용하는 것.

Stack 구조는 LIFO 를 사용하는 데에 적합한 구조이다. 즉, stack 을 사용하는 문제에서는 우선적으로 pop 을 이용해서 문제를 풀도록하자! 다른 방법 생각하면서 삽질하지 말구..!!!

 

두번째 시도

def equalStacks(h1, h2, h3):
	h1.reverse()
    h2.reverse()
    h3.reverse()
    s1=sum(h1)
    s2=sum(h2)
    s3=sum(h3)
    if s1==s2 and s2==s3:
            return s1
    while True:
        # vh = max([s1,s2, s3])
        if s1>=s2 and s1>=s3:
            h1.pop()
            s1=sum(h1)
            if sum(h1)==s2 and s2==s3:
                return s2
        elif s2>=s1 and s2>=s3:
            h2.pop()
            s2=sum(h2)
            if sum(h2)==s1 and s1==s3:
                return s1
        else:
            h3.pop()
            s3=sum(h3)
            if sum(h3)==s2 and s2==s1:
                return s2

pop() 을 사용해서 for 문을 엄청 줄였지만 여전히 시간복잡도에서 걸려서 틀렸다...

 

3번째 시도

약간(?) 의 도움을 받아 다시 풀었다.

def equalStacks(h1, h2, h3):
    # Write your code here
    h = [h1, h2, h3]
    h_sum = [sum(h1), sum(h2), sum(h3)]
    while True:
        if h_sum[0] == h_sum[1] and h_sum[1] == h_sum[2]:
            return h_sum[0]
        m = max(h_sum)
        m_idx = h_sum.index(m)
        element = h[m_idx].pop(0)
        h_sum[m_idx] -= element

 

이전은 바보같이 sum 을 계속 했다.

pop() 한 element 를 빼기만 하면 되는거였다..!!

풀었다ㅠㅜㅠㅜ