문제 문제 바로가기> BOJ 9935번: 문자열 폭발 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 풀이 문자열을 폭발시킬 때는 LIFO, 남은 문자열을 합칠때는 FIFO 자료구조가 용이하기에 deque를 사용했다. 문자열 폭발시 LIFO 자료구조를 이용하여 시간을 단축시킬 수 있는데, 그 이유는 가장 최신 폭발 문자열 개수만 보고 판단할 수 있고, stack 덕분에 문자열의 순서가 유지되기 때문이다. ( + stack 같은 자료구조의 유용성을 알 수 있는 좋은 문제같아서, 한번 풀어보면 좋을..

문제 문제 바로가기> 정올 1141번: 불쾌한 날 JUNGOL history 최근 본 문제 jungol.co.kr 풀이 N이 최대 80,000이므로 각 소에 대해서 이중 for문을 돌면서 확인할 경우 시간초과가 발생한다. 내가 볼 수 있는 소의 수를 세는 것이 아니라, 나를 볼 수 있는 소의 수를 센다면, O(N)으로 문제를 해결할 수 있다. 다음과 같이 스택 안에 나(H[i])를 볼 수 있는 소들만 들어 있도록 유지하면 된다. (1번 소가 3번 소를 볼 수 있고, 3번 소가 4번 소를 볼 수있으면, 1번 소는 4번 소를 볼 수있다.) #include #include #define MAX 80001 using namespace std; int N; int H[MAX]; void input(){ cin >..