본문 바로가기

Stack1

[백준] 2493. 탑 문제 풀이 처음에는 배열의 끝에서부터 탐색을 시작해서 자신보다 큰 값을 만날 때까지의 모든 요소들을 같이 초기화하는 방식을 생각했다. 하지만 이 경우에는 아래 방향의 화살표 모양(ex. 5 2 1 3 4) 경우를 커버하지 못해서 다른 방법을 생각해봤다. 최종적으로는 스택 두개를 사용해서 하나의 스택(A)은 입력 순서대로 들어가 있고 나머지(B)는 꺼낸 값을 저장했다. 꺼낸 값을 B 스택에 넣기 전에 B스택의 top이 더 작은 경우에는 꺼낸 값의 인덱스가 top의 결과가 된다. 인덱스를 찾는 방법에 대해서는 Map을 통해서 초기 입력시 해당 값을 key로 인덱스를 value로 저장해서 O(1)로 찾을 수 있도록 했다. Map을 통한 구현 import java.io.BufferedReader; import .. 2021. 2. 4.

이전 1 다음

티스토리툴바