알고리즘 공부 27일차

오늘은 ai tech 2차 테스트가 있는 날이었다. 테스트는 오후 7~9시에 치뤄져서 그 전까지 이때까지 블로그에 올렸던 문제를 복습하고 프로그래머스에서 풀었던 문제를 다시 한번씩 봐보았다. 그 중엔 풀이 방법이 잘 생각 안나는 것도 있었고 지금 풀면 좀 더 간결하게 풀 수 있을 것들이 보였다. 그렇게 공부하다 프로그래머스 2단게에 새로운 문제가 올라와서 그 중 한문제를 풀고 테스트를 치뤘다. 

테스트 난이도는 생각보다 어려웠다. 나름 매일 6~8문제를 풀면서 준비했다고 생각했는데 한 문제는 아예 손도 못댔었고 한 문제는 끝날 때 쯤 돼서 풀이 방법이 생각났다. 재귀로 풀면 되겠다!! 라고 떠올랐을 때 시간이 2분인가 남았었다. 그래도 공부한 덕인지 어느 정도 손은 댈 수 있었던 것 같다. 확실히 테스트가 끝나고 느꼈던 것은 기초가 많이 부족하다는 것이다. 어떤 공부든 기초가 중요한데 나는 무작정 코딩 테스트 문제만 풀었던 것 같다. 당장 중요한 시험이 이제 끝났으니 내일 부터는 CS 공부, 자료구조 공부도 해보려고 한다.

테스트가 끝나고 초밥도 먹고 친구들과 게임도 하고 놀았지만 하루에 코딩테스트 3문제는 풀자는 생각에 다시 컴퓨터를 켰다. 마음 먹은대로 3문제는 풀지 못했지만 나름 열심히 푼 문제를 포스팅 하고싶다.

문제는 따끈따끈하게 올라온 프로그래머스 2단계 문제인 '뒤에 있는 큰 수 찾기' 이다.

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

풀이 아이디어: 처음에는 단순하게 각각의 배열 원소 별로 뒤에 있는 큰 수를 직접 찾으려고 했다. 그런데 그렇게 푸니 시간 복잡도 문제가 발생했다. 생각해보니 최악의 경우 시간 복잡도가 O(N^2)만큼 발생한다는 것을 깨달았다. 그래서 그보다 간단하게 풀 방법이 없을까 생각했다. 그렇게 생각한 것이 deque와 heapq를 이용하는 것이었다. 구현은 이렇게 했다.

import heapq
from collections import deque
def solution(numbers):
    answer = [-1]*len(numbers)
    q=[]
    heapq.heappush(q,(numbers[0],0))
    num_que=deque(numbers)
    num_que.popleft()
    i=1
    while num_que:
        i1=num_que.popleft()
        while True:
            if len(q)==0:
                break
            i0,idx=heapq.heappop(q)
            if i0<i1:
                answer[idx]=i1
            else:
                heapq.heappush(q,(i0,idx))
                break
        if answer[i]==-1:
            heapq.heappush(q,(i1,i))
        i+=1
    return answer

풀고나니 든 생각은 그냥 stack을 이용해도 됐겠다는 생각이 들었다. 자료구조를 아직 100% 이용 못하는 것 같다. 여러 경우의 문제를 많이 풀어보아야겠다.

오늘은 그래도 코딩테스트 문제 6개, 프로그래머스 문제 2개, 총 8문제를 나름 풀었다. 내일부터는 코딩 테스트 말고도 다른 공부도 해보고 싶다. 내일도 화이팅!!