6건의 항목
실버4 : 스택 문제이다. Code // // main.cpp // algorithm_prac // // Created by 최완식 on 2021/04/05.
골드4 : stack 문제이다. 풀이 아, 정말 아쉬운 문제였다. 하지만 배운 것이 있었다. Stack을 기본적으로 사용하는 이유은 어떤 복잡도 문제를 해결하기 위함이다. 이 부분은 뒤에 다시 살펴보도록 하자.
골드5 : 스택 문제이다. 풀이 비슷한 문제를 한 3번 봤다. 근데 그 때는 heap을 사용해서 뒤에서 가장 큰 문자를 계속해서 뽑는 것으로 문제를 해결했다. 풍선 터트리기 그런 방식으로 해당 문제를 다시 풀려했으나, 밑에 알고리즘 분류를 봤는데 stack…이더라.
실버? : stack 문제이다. 풀이 처음에 op과 ()를 담는걸 별도로 생각했다가 낭패를 보았다. 생각하다보니 이 두개가 엮인다는 것을 알았고, 쉽게 규칙을 파악해서 풀 수 있었다.
풀이1 이게 보면, 전화번호 개수가 백만개라 단순히 비교로 풀면 n^2이라 박살난다. 그렇기 떄문에 다른 방법을 고민해야한다. 이 문제의 핵심은 결국 특정 단어가 접두어로 있는지에 대한 문제이다. 그렇기 때문에 startswith를 생각하는 것이 편하다.
풀이 prices의 길이가 100,000이라 n^2으로 짜면 터질 것 같아 stack으로 구현했다. 그런데 이때, 특정 원소가 조사해야 하는 부분은 i+1부터 끝까지의 요소이다. 그 과정에서 중복이 발생하기 때문에 반대로 정렬한뒤 값을 구해주었다.