목록3015 (1)

코딩성장스토리

백준 3015번 :오아시스 재결합

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