목록2024/11/05 (1)
걸음마부터 달리기
[24/11/05] 스택
감도 안잡혀서 빠르게 답 봤다.처음엔 List로 대충 구현하면 될거같은데 싶었다가 시간제한 보니 자바는 2초길래 명령어 개수가 최대 500,000개이면 O(NlogN)에서 무조건 끊어야되는데 싶었다. 그럴려면 List로 하는 순간 ArrayList는 삽입하는 순간 뒷 데이터 전부 밀어야해서 O(N), LinkedList는 찾는 과정에서 O(N)이라 이것을 각각 반복하면 O(N^2) 으로 타임아웃이 불 보듯 뻔했다. 커서고 뭐고 일단 처음 들어간게 가장 먼저 나오길래 큐인가 싶었는데 그러면 커서부분을 어떻게 해야되지? 큐 중간에 넣어야하는데? 에서 문제가 발생했다. 큐 중간에 넣어버릴수가 없으니 (스택도 마찬가지고) 커서 있는걸 기준으로 서로 다르게 쪼갰어야 했다. 쪼개기만 하면 큐로는 구현이 안되고 ..
카테고리 없음
2024. 11. 5. 22:41