[자료구조] 스택 - 백준 2493, 2812

백준 2493번

각 탑에서 발생하는 레이저 신호를 수신하는 탑의 인덱스를 출력하는 문제이다.
시간제한을 보면 1.5초인만큼 다음과 같은 풀이는 시간초과가 발생한다

잘못된 풀이

모든 탑의 리스트를 이중 반복하기 때문에 시간복잡도가 O(n2)이 되기 떄문이다.

해당 풀이는 다음과 같이 진행했다

1. 모든 타워들을 담아줄 스택A과 수신받는 타워의 인덱스를 담아줄 스택B 2개를 만듬
2. 타워들을 스택에 하나씩 넣으면서 비교한다는 느낌으로 생각하면 됨 (백준 - 9012)
3. 큰 타워보다 먼저 들어간 작은 타워는 신호를 더이상 받을 수 없기 때문에 pop을 시켜야함.
4. 맨 처음에는 비교할 타워가 없으므로 일단 append함.
5. 수신받는 타워의 인덱스만 출력해야 하는데 스택A는 신호를 받지 못하는 타워는 pop을 시키기 때문에 별도로 인덱스를 저장할 스택이 하나 더 필요함.

다음문제

백준 2812번

N개의 입력받은 숫자에서 K개를 지워 가장 큰 값을 출력하는 문제이다.

해당 문제의 풀이는 다음과 같이 진행되었다.

1. 숫자들을 받아줄 스택과 삭제 횟수를 저장할 변수를 선언한다.
2. 삭제 횟수가 남아있고 스택이 비어있지 않을 때까지 반복문을 진행한다.
   해당 반복문은 숫자를 입력받았을때 큰 숫자를 앞자리수로 만들고 작은 숫자는 지우기 위함이다.
3. 새로 들어올 숫자가 스택에 있던 숫자보다 더 클 경우 기존 숫자는 필요가 없기 때문에 해당 숫자를 pop하고 삭제 횟수를 1 감소한다.
4. 반대로 새로 들어올 숫자가 더 작거나 같은 경우 반복문을 탈출함.

위와 같이 진행하면 삭제 횟수가 존재하는 한 앞자리의 작은 숫자들은 새로 들어올 숫자들 보다 작을 경우 계속해서 pop되게 됨.

잘못된 풀이

해당 풀이는 맨 마지막 숫자가 스택에 남아있는 숫자보다 작을 경우 스택의 변동 없이 바로 append하는 문제가 발생한다.
예를 들어

입력받을 숫자가 2개, 지워야할 숫자가 1개
입력 받을 숫자는 2, 1
맨 처음 입력받은 2는 당연히 반복문 조건에 해당되지 않아 바로 append되어야 한다.
문제는 다음에 입력받을 숫자 1인데, 1의 경우 stk의 top보다 작기 때문에 바로 반복문을 탈출하여 append되게 된다.
그러면 출력할 때 맨 뒤에 있는 숫자가 더 작을 경우를 해결할 수 있는 방법이 필요하다.

위와 같이 삭제변수를 별도로 선언하여 삭제 횟수에 따라 반복문이 진행되도록 하고
추후 출력할 때에는 정해진 자릿수만큼 출력할 수 있도록 하였다.