[Programmers] 풍선 터트리기

안뱅·2022년 6월 22일
0

[Coding Test]

목록 보기
18/35
post-thumbnail

문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/68646

풀이

특정 풍선을 기준으로 좌측파트와 우측파트에 인접한 풍선 중 큰 풍선을 모두 터트리면 특정풍선에 대해 좌측과 우측에 각 1개의 풍선이 남게 된다.
이때 각 파트에는 각파트의 최소값을 가진 풍선이 남게 되게 된다.

이후 보다 작은 풍선을 터트릴 수 있는 기회가 1회 있으니깐,
특정 풍선이 양쪽에 남아있는 풍선들보다 항상 크지만 않으면 특정 풍선은 최후까지 살아 남는다.

또한, 양끝에 있는 풍선은 파트가 1개밖에 나오지 않음으로 무조건 살아남게 된다.

즉, 어떤 풍선을 최후까지 남길 수 있는지 확인하긴 위해선,
해당 풍선을 제외한 우측파트와 좌측파트의 최소값을 갖는 풍선을 가져와서 해당 풍선과 크기를 비교하면 된다.

Solution1 : 시간초과

def solution1(a):
    answer = 2
    
    for i in range(1,len(a)-1):
        target = a[i]
        ls = a[0:i].sort()
        rs = a[(i+1):(len(a))]

        left_min = min(ls)
        right_min = min(rs) 
    
        if target > left_min and target > right_min:
            continue
        else:
        
            answer+=1
    return answer

solution1 풀이

문제 조건을 자세히 안봤더니, 시간초과를 마주했다...
문제 조건을 다시보면 a의 길이는 최대 100만까지 가능하다.
즉, 각 a의 요소에 대해 좌측파트와 우측파트의 최소값을 매번 새롭게 min()을 통해 구하게 되면 시간 초과가 날 수 밖에 없다.

Solution2 : 시간초과

def solution2(a):
    answer = 2
    
    lsm = a[0]
    rsm =  min(a[1:len(a)-1])
        
    for i in range(1,len(a)-1):
        target = a[i]
        
        if a[i-1] < lsm:
            lsm = a[i-1]
            
        if target == rsm:
            rsm = min(a[i+1:len(a)])
            

        if target > lsm and target > rsm:
            continue
        else:
            answer+=1
    
    return answer

solution2 풀이

이번에는 반복문 밖에서 좌측, 우측파트의 최소값을 미리 정해주고, 반복문 안에서 기준이 되는 풍선이 바뀔때마다, 비교를 통해 최소값을 갱신하는 로직을 만들었다.

좌측 파트의 경우
기준 풍선이 바귈때마다, 제일 최근의 기준풍선이 좌측파트에 속하게 됨으로 제일 최근의 기준풍선이 처음에 설정한 최소값보다 작을때 좌측파트의 최소값을 갱신하게 했다.
우측파트의 경우
기준 풍선이 바귈때, 좌측파트가 최소값을 구하는 범위가 증가하는 반면, 우측파트의 최소값을 구하는 범위가 줄어들게 됨으로, 기준풍선이 처음 설정한 우측파트의 최소값일때 최소값을 갱신하게끔 만들었다.

우측파트의 갱신 로직이 이전보다 크게 효율적으로 바뀌지는 않아서 애매하긴 했는데, 그래도 통과할줄 알았다.
하지만 역시나 시간초과를 맞이했다.

Solution3 : Pass

def solution3(a):
    answer = 2
    lsm = [a[0]]
    rsm = [a[-1]]
    for i in range(1, len(a)):
        
        if lsm[len(lsm)-1] > a[i]:
            lsm.append(a[i])
        else:
            lsm.append(lsm[len(lsm)-1])
        
        if rsm[len(rsm)-1] > a[len(a)-i-1]:
            rsm.append(a[len(a)-i-1])
        else:
            rsm.append(rsm[len(rsm)-1])
    
    rsm.reverse()
    
    for i in range(1,len(a)-1):
        target = a[i]
        if target > lsm[i] and target > rsm[i]:
            continue
        else:
            answer+=1
    
    return answer

solution3 풀이

이번에는 메모라이제이션 기법을 사용해 모든 기준풍선의 경우에 대해 좌측, 우측 파트의 최소값을 별도로 리스트에 기록하고, 반복문에서 기준풍선이 바뀔때마다 각 파트의 최소값을 리스트에서 가져오는 방식을 써봤다

좌측 파트의경우
이전 로직과 동일하게 최소값 리스트를 구현했다.
우측 파트의 경우
우측 파트의 경우 기준풍선이 우측에서 좌측으로 이동한다고 생각하고, 나중에 우측파트 최소값 리스트를 reverse하는 형식으로 구현했다.

이전 로직에서 기준풍선이 좌측에서 우측으로 이동하기 때문에,
좌측파트는 로직을 세우기 쉬웠다.
반면 우측파트의 경우 역방향에서 최소값을 구하는 로직을 세울때 헷갈리는 측면이 있어서 min()를 사용하는 로직을 세웠었다.

그래서 이번에는 우측 파트의 경우 기준풍선이 우측에서 좌측으로 이동한다고 생각하고, 나중에 우측파트 최소값 리스트를 reverse하는 방식으로 로직을 세웠더니 좌측 파트처럼 쉽게 로직을 세울 수 있었다.

FeedBack

솔직히 solution2의 우측파트의 최소값을 구하는 로직이 효율적이지 못해 시관초과를 마주할 것은 어느정도 예측하고 있었다.
근데, solution3의 경우 우측 파트 최소값을 구하는 로직을 개선하기 했지만, 이를 위해 for문을 한번더 돌리고, append()를 사용했다는 점에서 solution2와 효율성이 비슷할 줄 알았는데 solution3를 통과했다는 점이 상당히 당황스러웠다.
이부분에 대해서는 시간복잡도에 대해 좀더 공부를 해야할 것 같다.

0개의 댓글