코딩성장스토리

https://www.acmicpc.net/problem/3015 3015번: 오아시스 재결합 첫째 줄에 줄에서 기다리고 있는 사람의 수 N이 주어진다. (1 ≤ N ≤ 500,000) 둘째 줄부터 N개의 줄에는 각 사람의 키가 나노미터 단위로 주어진다. 모든 사람의 키는 231 나노미터 보다 작다. 사람 www.acmicpc.net 이 문제는 처음에 그냥 다 세면 되지 않을 까 라고 쉽게 생각했으나 시간복잡도가 어마무시해지는걸 깨닫고 바로 패스했다. 즉 반복문은 한번 써 한바퀴만 돌면서 값을 알아내야 했다. 스택의 개념을 적용 해서 값을 스택에 넣고 다음 값이 스택 값보다 클 경우에 스택에 있는 값은 다음 값보다 뒤에 있는 것은 아예 볼 수 없으므로 스택에서 빼주며 1을 더해준다. 이렇게 구현을 하다보..

https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 이 문제를 풀 때 문자열을 반복으로 계속 반복하면서 빼기에는 시간초과가 나온다. 그래서 스택을 이용해서 폭발 문자열이랑 같으면 빼주는 방식으로 간다. 여기서 주의 할것은 1. 스택에 들어간 수가 폭발 문자열 수보다 클떄 폭발 문자열을 빼야한다 2.폭발 문자열이랑 다르면 스택을 다시 돌려 놓아야한다. 이 두 개의 조건과 폭발 문자열과 기본 문자열 비교를 위해서 임시 스택 저장소를 구현..