FrontEnd
Javascript
Diary
ML
CS
Django
Algorithm
AWS
Co-Work
HTML
CSS
Python
React
ReactNative

#49 알고리즘 연습 - 탑(Python)

수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다.

송신 탑(높이) 수신 탑(높이)
5(4) 4(7)
4(7) 2(9)
3(5) 2(9)
2(9) -
1(6) -

맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하도록 solution 함수를 작성해주세요.

제한 사항

  • heights는 길이 2 이상 100 이하인 정수 배열입니다.
  • 모든 탑의 높이는 1 이상 100 이하입니다.
  • 신호를 수신하는 탑이 없으면 0으로 표시합니다.

입출력 예

heights return
[6,9,5,7,4] [0,0,2,2,4]
[3,9,9,3,5,7,2] [0,0,0,3,3,3,6]
[1,5,3,6,7,6,5] [0,0,2,0,0,5,6]

입출력 예 설명

  • 입출력 예 #1 앞서 설명한 예와 같습니다.
  • 입출력 예 #2 [1,2,3] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다. [4,5,6] 번째 탑이 쏜 신호는 3번째 탑이 수신합니다. [7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.
  • 입출력 예 #3 [1,2,4,5] 번째 탑이 쏜 신호는 아무도 수신하지 않습니다. [3] 번째 탑이 쏜 신호는 2번째 탑이 수신합니다. [6] 번째 탑이 쏜 신호는 5번째 탑이 수신합니다. [7] 번째 탑이 쏜 신호는 6번째 탑이 수신합니다.

문제풀이
(예전생각)입력받는 list의 앞에서부터가 아닌 뒤에서 부터 돌아오기때문에 reverse로 뒤집어서 각 index별로 다음 index와의 크기비교를 이용한 cnt방식을 사용했다. (지금생각)문제의 카테고리가 스택 큐인것도 있지만 list의 뒤에서부터 가져오기때문에 list의 pop으로 뽑고 뽑은 값들을 순서대로 비교해서 체크해주면 훨씬더 효율적으로 코드를 짤수 있을것 같다.

내 풀이 🏆

def solution(heights):
    heights.reverse()
    answer = []
    for i in range(len(heights)):
        cnt = 1
        if i == len(heights)-1:
            answer.append(0)
        for j in range(i+1,len(heights)):
            if j == len(heights)-1 and heights[i]>heights[j]:
                answer.append(0)
            if heights[i]==heights[j]:
                answer.append(0)
                break
                
            if heights[i]>heights[j]:
                cnt +=1
            else:
                answer.append(len(heights)-(i+cnt))
                break
    answer.reverse()
    return answer

다른 풀이 🏆

def solution(h):
    ans = [0] * len(h)
    for i in range(len(h)-1, 0, -1):
        for j in range(i-1, -1, -1):
            if h[i] < h[j]:
                ans[i] = j+1
                break
    return ans

다른 풀이를 보면 range의 세번째 arg로 -1을 주면서 역으로 list를 볼수있는데 pythonic한 코드라는 측면에서 깔끔한 코드인것 같다. 하지만 위에 언급했던것 처럼 pop을 이용하면 같은 구조로 코드를 짜는데 도움이 될것 같고, 매번 쓰는 것만 쓰기보다는 알고있는 method중에서 적용해볼만한 method가 없는지 생각을 열어두는게 중요한것 같다.