[BOJ] 2493 Tower 스택을 이용한 풀이

2493번: 탑 (acmicpc.net)

오늘 알고리즘 시간에 순열, 조합, 부분집합, 스택, 큐에대해서 배웠다.
과제로 백준 문제가 나왔는데, 2시간동안 막혀있다가 마감 직전에 간신히 풀어서 제출했다.

처음에 아무생각없이 배열로 접근했다가 시간초과가 났다.
조건에 맞추려면 O(n)정도는 되는 알고리즘을 사용해야하는데 O(n^2) 정도 되는 방식을 사용했으니 당연한 결과였다.

그다음부터는 스택을 이용해야겠다는 생각이 들었다.
그런데 스택을 사용해야겠다는 아이디어 말고 다른 생각들이 잘 안떠올랐다.
인덱스와 높이를 모두 저장했어야 했는데, 이걸 배열이나 두가지 값을 저장하는 객체를 만들지 않고 하려고 했더니, 로직이 꼬여버렸다.
어떻게해서 테스트케이스 1개는 맞췄는데 제출하고보니 틀렸다.

그래서 다시 좋게 배열을 이용해서 스택에 높이와 인덱스를 동시에 저장하기로 했다.
이렇게 하고나니깐 훨씬 수월했고, 코드도 간단해졌다.
이 문제의 핵심은 스택에 앞선 빌딩들을 넣고, 현재 높이와 비교해서 바로 앞 타워가 높이가 더 높은 경우에는 바로 앞 인덱스를 저장하고, 바로 앞이 작다면 스택에서 계속해서 꺼내서 비교하는데, 큰 값이 없는 경우에는 0을 저장하고, 현재 타워를 스택에 푸쉬한다.

그렇게 했는데도 메모리 초과가 발생했다.
처음에 스캐너를 이용해서 입력을 받은게 원인이었다. 이번 기회를 통해서 BufferedReader와 Tokenizer 사용법에 대해서 익히게 되었다. 그리고 덤으로 스트링 빌더 까지.