문제의 핵심을 이해하고 정확히 구현하는 알고리즘

1. 문제

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh&categoryId=AV134DPqAA8CFAYh&categoryType=CODE&problemTitle=view&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 

SW Expert Academy

 

강변에 빌딩들이 옆으로 뺵빽하게 밀집한 지역이 있다.

 

이곳에서는 빌딩들이 너무 좌우로 밀집하여, 강에 대한 조망은 모든 세대에서 좋지만 왼쪽 또는 오른쪽 창문을 열었을때 바로 앞에 옆 건물이 보이는 경우가 허다하였다.

 

그래서 이 지역에서는 왼쪽과 오른쪽으로 창문을 열었을 때, 양쪽 모두 거리 2 이상의 공간이 확보될 때 조망권이 확보된다고 말한다.

 

빌딩들에 대한 정보가 주어질 때, 조망권이 확보된 세대의 수를 반환하는 프로그램을 작성하시오.

 

아래와 같이 강변에 8채의 빌딩이 있을 때, 연두색으로 색칠된 여섯 세대에서는 좌우로 2칸 이상의 공백이 존재하므로 조망권이 확보된다. 따라서 답은 6이 된다.

 

 

 

A와 B로 표시된 세대의 경우는 왼쪽 조망은 2칸 이상 확보가 되었지만 오른쪽 조망은 한칸 밖에 확보가 되지 않으므로 조망권을 확보하지 못하였다.

 

C의 경우는 반대로 오른쪽 조망은 2칸이 확보가 되었지만 왼쪽 조망이 한 칸 밖에 확보되지 않았다.

 

 

2. 제약사항

 

가로 길이는 항상 1000이하로 주어진다.

 

맨 왼쪽 두 칸과 맨 오른쪽 두칸에는 건물이 지어지지 않는다(예시에서 빨간색 땅)

 

각 빌딩의 높이는 최대 255

 

 

3. 나의 풀이

 

문제를 도대체 어떻게 접근해야할까?

2차원 평면을 구상하고, 빌딩의 높이만큼 1을 채워서 각 행을 순회하고 1이 있는 부분의 좌우 2칸을 확인해봐야할까?

 

그러면 어떻게 할수는 있겠지만 너무 복잡하지 않나?

 

사실 조금만 생각해보면, 아주 자연스럽게, 빌딩의 높이를 1차원 리스트로 어떻게든 받을 수 있을 것이다

 

예를 들어 위 그림은 [0,0,3,5,2,4,9,0,6,4,0,6,0,0]

 

초록색은 도대체 어떻게 하면 칠해질까??

 

문제 기준에서 초록색이 될려면, 좌우 2칸이 비어야한다고 했다

 

비어있는 칸은 어떻게 하면 알 수 있을까? 그냥 단순히 두 건물의 길이를 빼면 될것이다

 

 

먼저 가능한 A가 써진 건물을 보면, 좌우로 건물 길이 차이를 구해보면.. 놀라운 특징을 볼 수 있다

 

좌우 2칸 각각 건물 길이가 5,2,3,1

 

바로 이들중에서 최솟값이 초록색으로 칠해진 개수가 된다. 이런 규칙을 발견했다면 다른것도 그럴까?

 

바로 검증에 들어가면 된다

 

 

 

실제로 B부분도 7,5,9,3에서 최솟값 3이 초록색으로 칠해진다.

 

마찬가지로 다음 부분도 2,6,6,6으로 2가 최솟값이고 그만큼 색칠해진다.

 

이런 알고리즘 규칙을 찾았다면 그대로 구현하면 된다.

 

어떻게하면 가능할까..?

 

문제의 입력에 맞게 먼저 구성을 하고

 

T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    
    n = int(input())
    
    h_list = list(map(int,input().split()))

 

이제 자연스럽게 왼쪽부터 오른쪽으로 순회할건데, 문제는 인덱스 0,1에서는 어차피 건물의 길이가 0이니까 검사할 필요가 없다. 

 

그렇다면 인덱스가 i가 2부터 마지막 2개도 필요없으니까 n-3까지 순회하면 될 것이다.

 

습관적으로 h_list의 길이를 구해서 n으로 사용하는데

 

우리는 가로의 길이를 n으로 받았으므로 이를 그냥 활용하면 된다

 

T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    
    n = int(input())
    
    h_list = list(map(int,input().split()))
    
    for i in range(2,n-2):
        
        if h_list[i] <= h_list[i+1] or h_list[i] <= h_list[i+2]:
            
            pass

 

근데 이제 자연스럽게, 왼쪽부터 오른쪽으로 순회할건데, 현재 위치 i에서 건물의 길이가 바로 오른쪽 2개의 건물의 길이 i+1, i+2와 비교해서,

 

단 하나라도 오른쪽 건물이 더 길면 모든 세대가 조망권을 확보할수없으므로 바로 패스하고 다음 i로 넘어가면 된다

 

T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    
    n = int(input())
    
    h_list = list(map(int,input().split()))
    
    answer = 0
    
    for i in range(2,n-2):
        
        if h_list[i] <= h_list[i+1] or h_list[i] <= h_list[i+2]:
            
            pass
            
        else:
        
            min_right_h = min([(h_list[i] - h_list[i+1]), (h_list[i]-h_list[i+2])])

            min_left_h = min([(h_list[i]-h_list[i-2]), (h_list[i]-h_list[i-1])])

            answer += min([min_right_h,min_left_h])

 

그러면 우리가 만든 규칙에 맞게 좌우 건물 길이 차이를 구하고 이들의 최솟값이 바로 조망권이 확보된 건물의 개수이고

 

이를 answer에 계속 더해가면 된다

 

여기서 abs()를 써야할까? h_list[i]가 가장 길다고 전제되어있으므로 abs를 쓸 이유가 없다

 

근데 이렇게 하면 아쉬운 점이 굳이 검사할필요가 없는 부분도 검사하게 된다는 점이다.

 

 

현재 위치 i에서 좌우 2칸 조망권이 확보된 건물이 존재한다면, 그 바로 좌우 2칸 건물들은 무조건 조망권을 확보할수가 없다.

 

그래서 현재 위치 i에서 바로 i+3으로 넘어가는게 더 효율적이지 않을까?

 

그것을 위해서 반복문을 while로 바꿔준다

 

최종 인덱스는 i가 n-2까지 가야하므로 

 

 

T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    
    n = int(input())
    
    h_list = list(map(int,input().split()))
    
    answer = 0
    
    i = 2
    
    while i <= n-2:
        
        if h_list[i] <= h_list[i+1] or h_list[i] <= h_list[i+2]:
        
            i+=1
            
            pass
            
        else:
        
            min_right_h = min([(h_list[i] - h_list[i+1]), (h_list[i]-h_list[i+2])])

            min_left_h = min([(h_list[i]-h_list[i-2]), (h_list[i]-h_list[i-1])])

            answer += min([min_right_h,min_left_h])
            
            i += 3

 

 

여기까지 해서 맞춘줄 알고 냈지만 오답이다. 왜냐하면 우측 2개의 건물을 조사해서 통과했다고 해서,

 

바로 길이 차이를 계산했다는게 문제다.

 

우측 2개의 건물을 조사해서 통과했다고 해도 좌측 2개의 건물이 현재 건물의 길이보다 더 길수도 있기때문이다.

 

 

 

이러한 부분을 수정하여 마지막 최종 코드는..

 

T = 10
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for t in range(1, T + 1):
    # ///////////////////////////////////////////////////////////////////////////////////
    
    n = int(input())
    
    h_list = list(map(int,input().split()))
    
    answer = 0

    i = 2

    while i <= n-2:

        #우측확인

        if h_list[i] <= h_list[i+1] or h_list[i] <= h_list[i+2]:

            i += 1

            pass

        else:
            
            if h_list[i] <= h_list[i-1] or h_list[i] <= h_list[i-2]:
            
                i += 1
            
                pass
            
            else:

                min_right_h = min([(h_list[i] - h_list[i+1]), (h_list[i]-h_list[i+2])])

                min_left_h = min([(h_list[i]-h_list[i-2]), (h_list[i]-h_list[i-1])])

                answer += min([min_right_h,min_left_h])

                i += 3
    
    print('#'+str(t),answer,sep=' ')
    # ///////////////////////////////////////////////////////////////////////////////////

 

4. 되돌아보기

 

어떻게 풀어야하지?라고 멍때리다가 도망쳤었는데

 

다시한번 잘 생각해보고, 문제의 핵심이 무엇인지, 어떻게하면 간단하게 할 수 있는지 잘 고민하였고,

 

그에따라 핵심을 잘 파악했고, 그것을 정확히 구현했고,.. 잘 했다