개발자 아지트

안녕하세요. 지금 기분이 굉장히 좋습니다.!!!!! 자료구조를 공부하고 이렇게 통쾌하게 문제를 풀어본 경험은 오늘이 처음입니다!!! 세상 사람들아!! 내가 이 문제를 드디어 자료구조로 풀었다!!!!!!

문제설명

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

5
12 7 9 15 5
13 8 11 19 6
21 10 26 31 16
48 14 28 35 25
52 20 32 41 49

35

문제 해결 방법

우선 실버2를 푼다는 생각에 넘넘 긴장되고 겁이나서 페이지 하단에 있는 '알고리즘 분류'를 먼저 보고 참고하여 문제를 풀었다. 해당 문제는 우선순위 큐에 속한다. 따라서 파이썬의 heapq모듈을 활용하여 해당 문제를 풀고자 했다. 

코드 구현

import heapq

n = int(input())
#n개의 줄에 n개의 수가 주어짐 
#n개의 줄에 n개의 원소가 들어가게끔 만들어야함
list_list = []
total=[]
for i in range(n): # 이렇게 쓰면 딱 원소가 5개임
    #print('i', i)
    list_list.append(list(map(int, input().split())))
    
    
    for j in range(n):
        total.append(list_list[0][j])
    list_list=[]

    heapq.heapify(total)
    answer = heapq.nlargest(n,total)

    if i==0: 
        pass
    else:
        #print('i', i, 'prev total', total)
        for p in range(n):
            heapq.heappop(total)
    
    #print('i', i, 'total', total)
    #print('i', i, 'answer', answer)
    
   
# total=[]

print(answer[-1])

시간/공간 복잡도

????? 뭘적징

최적화 및 개선

처음에는 '메모리 초과'가 떴다. 엥 메모리초과가 뭐지? 설마 이것이 공간복잡도 인가?? 와우!! 처음 보는 결과다 ㅠㅠ

감격스러운 마음에 막 찾아봤다. 

메모리 초과란?

공간 복잡도를 초과한 경우를 말하고, 공간 복잡도란 프로그램을 실행시킨 후 완료하는 데 필요로 하는 자원 공간의 양을 말한다. 

과연내가 어디서 공간을 많이 잡아먹은거지... 첨엔 어떻게 이걸 찾아야 하는건지 잘 모르겠었다. 

그래서 무작정 코드를 다시 봤다.. 코드를 다시 보니까 첫 제출할때는 미처 발견하지 못한 에러들을 3개나 발견했다. !!

혹시나 이 에러를 해결하면 문제를 풀까 해서 다시 제출해봤는데 택도없었다! 

모든 입력을 배열에 저장하면 당연히 메모리 초과입니다. 문제의 메모리 제한은 겨우 8MB입니다. 아무리 작은 자료형으로 저장한다고 해도 short형 (2바이트) 천만 개면 약 20MB로 역시 메모리 초과입니다. 입력을 전부 저장하지 않고 푸는 방법을 생각해 보세요. 힌트는 입력되는 정수의 범위에 있습니다. (백준 가이드)

그래서 설마 내가 total 리스트에 모든 n개의 원소 n개 받은것을 풀어서 넣고 갖고 다닌것이 공간복잡도를 많이 잡아먹는건가 싶어서 그 부분을 좀 최적화 해봤다. 그랬더니 

느낀점

기분이 너무 좋다 진짜!!! 공부할 맛 난다. 오늘 큰거 깨달았다.

코테 준비 및 알고리즘 공부는 이런식으로 하면 되겠구나 

자료구조 및 알고리즘 미리 공부 후에 문제 풀이하기~

근데 한편으로는 아쉽다 이렇게 하면되는걸.. 그동안 맨땅의 헤딩을 즐겨했던 나..
그래서 사기가 많이 떨어졌던 과거의 나... 

나야 고생했고 앞으로 잘해보자~ ^^