[프로그래머스][stack/queue] 탑 python (201104)

1. 문제 설명

 

수평 직선에 탑 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으로 표시합니다.

 

입출력 예

height             sreturn

[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번째 탑이 수신합니다.

 

 

 

2. 풀이 

1) 2중 포문과 deque 를 활용 (내풀이, 통과는 했으나 공간 복잡도 면에서 비효율)

from collections import deque

def solution(heights):
    total_len = len(heights)
    result_list = deque([])
    
    for _ in range(total_len -1):
        key_num = heights.pop()
        h_list = heights.copy()
        
        result = len(h_list)
        while h_list:
            com_num = h_list.pop()
            if com_num > key_num:
                break
            else:
                result-=1
                pass
                
        result_list.appendleft(result)
    result_list.appendleft(0)
    return list(result_list)

 

a. 우선 비교 기준이 되는 숫자를 하나씩 뽑은 다음에 

b. 나머지 비교 대상인 숫자들로 h_list를 만들고 얘네를 pop으로 하나씩 뽑아서 비교했다. 

c. 초기 result 값을  h_list의 길이로 정해두고,

기준 숫자 보다 작거나 같은 값이 나오면 하나씩 빼주면서 (탐색인덱스의 역할)

만약 기준 숫자보다 큰 값이 나오면 해당 인덱스를 result list 에 담기게 했다. 

d. 이때 deque 자료형의 append left 를 활용해서 좌측에서부터 데이터가 쌓이게끔 만들었다. 

 

 

나의 실수와 문제점 :

list의 인덱스를 통해 값을 빼내는 가령 height[4] 의 time complexity 가 o(n)  선형탐색 시간일거라 생각했따...

아니었다.. o(1) 이었다. 단순히 리스트 인덱스 만 가지고도 쉽게 풀수 있었던것 

나아가 list.copy() 가 o(n) 이었다.

 

https://wayhome25.github.io/python/2017/06/14/time-complexity/

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그

진짜 이건 외워둬야겠다...

list 에서 o(1) 에 해당되는 메소드는 

list[index] / list[index] = num

 

# 리스트 시간 복잡도 내 방식으로 정리 

o (1)		o(n) *** 알고리즘 문제에서 쓰지마..
list[index]	인덱스로 값 찾기	list(a)	리스트화 시키는 것
list[index] = num	인덱스로 값 할당	list1 == list2	리스트 비교
len(list)	리스트 길이 구하기	del list(num)	삭제. num을 찾아야하니까
list.append(num)	리스트 요소 추가	list.remove	삭제. num을 찾아야하니까
list.pop()	리스트 맨 마지막요소 pop	list.pop(i) 는 o(n) 이다.!!!!	특정 인덱스 값 추출해내기
list.clear()		list.insert(index, num)	특정인덱스에 값 삽입 인덱스마다 탐색해야하니까..!
		list.revese()	거꾸로만들기
		list.copy()	복사/
		list.sort()	정렬
		min max	최대최소
해당 경우 딕셔너리에서는 o (1) 이다. <====		a in list	있는지 확인
		[0] * 4	리스트 concat

 

 

** 리스트에서 삭제 메소드는 o(n) 이다.

따라서 알고리즘 문제 중 특정 값(최소값 혹은 최대값) 을 삭제해야하는 문제들이 있는데, 

그런 경우 해당 값들을 끝으로 몰아, pop을 이용하도록 머리를 써야함 

==> 이때 사용하는 것이 힙정렬 알고리즘임 최대힙 혹은 최소힙으로 구성해서 heap.heappop 써버리면 우선 순위 큐 가능.

 

힙정렬 링크 

 

 

# 딕셔너리 경우 :  거의 다 o(1) 이다 for 문을 쓰지 않는 이상.

특히 containment (포함여부) 를 묻는 num in dict 의 경우에도, 시간 복잡도가 o(1) 이다. !!!!

 

 

2) 인덱스 만을 가지고 풀기 + 여전히 deque 사용 

from collections import deque
def solution(heights):

    result_list = deque([])
    for i in range(len(heights)-1,0,-1): #기준이 되는 숫자들 인덱스
        for j in range(i-1,-2,-1): # 비교대상 숫자 인덱스
            if heights[i] < heights[j]:
                break
            else: pass
        result_list.appendleft(j+1)
    result_list.appendleft(0)
    return list(result_list)

 

for j in range(i-1,-2,-1) 을 한 이유는 

기준이 되는 숫자 뒤에 나오는 숫자들을 하나씩 탐색하는데,

만약 다 탐색하고도 더 큰숫자가 나오지 않는다면 2번째 포문을 끝났을때 j 의 값은 -1 이다. 

만약 3번째에 더 큰 숫자가 있었더라면 j의 값은 3이고 

 

result_list는 1인덱스 (1부터 인덱스 시작)기 때문에 j의 값에 +1을 해주며 넣어야하니까

만약 다 탐색하고도 더 큰숫자가 나오지 않는경우의 j 는 0이 아니라 -1이 되게끔 만들기 위해서 range(i-1,-2,-1) 로 만들었다. 

 

--> 근데 굳이 디큐를 사용할 필요가 없는게, 마지막 반환하는 과정에서 list() 화를 한번 더 시켜주고 

      이때 시간 복잡도가 o(n) 이 걸린다..

 

 

2) 코드의 시간 복잡도는 

o(n^2) -->이중포문

o(n)--> deque 리스트화

 

 

3) 인덱스 만을 가지고 풀기  디큐 미사용.

def solution(heights):

    result_list = [0] * len(heights)
    for i in range(len(heights)-1,0,-1):
        for j in range(i-1,-1,-1):
            if heights[i] < heights[j]:
                result_list[i] = j+1
                break
    return result_list

 

else 를 할필요 없이 기본 리스트를 0 으로 채워놓고, 만약 비교 숫자중 기준 숫자보다 큰 값이 있다면 

해당 비교 인덱스+1 이 결과 리스트에 바로 할당한다. 

리스트에 값을 할당하는건 o(1) 이니까 디큐의 appendleft()와 수행속도는 같고. 

 

여기서 시간이 걸리는건 result_list 를 만드는 과정에서 o(n) 이 걸린다.

 

3) 코드의 시간 복잡도는 

o(n) --> [0] * len(height) 

o(n^2) -->이중포문

 

 

결국 2),3) 의 시간 복잡도는 같다. 

 

 

 

 

3. 정리 

뼈에 새기자.. 리스트 메소드들의... 시간복잡도....