문제

BOJ 2493 탑

https://www.acmicpc.net/problem/2493

오랜만에 골드문제를 풀었다. 아마두..?
사실 그 동안 푼 문제들의 난이도를 굳이 기억하지 않기 때문에 아닐 수도
암튼 시행착오를 겪었다는 얘기를 하는 것이다ㅏ.
한창 알고테스트를 준비할 때는 기본적으로 골드 4,5를 풀어재꼈는데 퇴화됐다. 힝구 핑구

코드

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;


public class boj_2494_스택 {
	static class node{
		int idx,val;
		
		node(int idx,int val) {
			this.idx=idx;
			this.val=val;
		}
		
	}
	
	public static void main(String []args) throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		
		Stack<node>stack=new Stack<node>();
		
		int n=Integer.parseInt(br.readLine());
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		for(int i=1;i<n+1;i++) {
			int cur=Integer.parseInt(st.nextToken());
		
			while(!stack.isEmpty()) {
				if(cur>stack.peek().val) {
					stack.pop();
				}else {
					break;
				}
			}
			
			if(stack.isEmpty())sb.append(0).append(' ');
			else sb.append(stack.peek().idx).append(' ');
			
			stack.push(new node(i,cur));
			
		}
		
		System.out.println(sb);
	
	}

}

😥시행착오😥

1. MEMORY

처음으로 문제를 풀었을때 메모리를 너무 많이 써 통과하지 못했다.
1. 그럴만도 한 게 입력을 받을 때마다 origStack에 push를 하고
2. 그리고 pop을 하며 처음으로 부딪히는 탑을 찾기 위해 새로운 nStack을 만들어 nStack.addAll(origStack)을 해댔다.

다음 코드가 처음으로 작성한 코드이다.

package BOJ;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;


public class boj_2493 {
	public static void main(String []args) throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb=new StringBuilder();
		
		Stack<Integer>origStack=new Stack<Integer>();
		
		int n=Integer.parseInt(br.readLine());
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		for(int i=0;i<n;i++) {
			origStack.add(Integer.parseInt(st.nextToken()));
		
			Stack<Integer> nStack=new Stack<Integer>();
			nStack.addAll(origStack);
			
			//자기자신 빼기
			int curTop=nStack.pop();
			
			//초기값 0
			int cnt=0;
			
			//탑 여부
			boolean isSuccess=false;
			
			while(!nStack.isEmpty()) {
				int nTop=nStack.pop();
				
				cnt++;
				
				if(nTop>=curTop) {
					isSuccess=true;
					break;
				}
			}
			
			int answer;
			
			if(!isSuccess)answer=0;
			else answer=i+1-cnt;
			
			sb.append(String.valueOf(answer)+' ');
		}
		
		System.out.println(sb);
	
	}

}

이러니 메모리가 남아돌겠냐구..
일단 500000개의 원소가 들어가는 것도 벅찬데 계속 stack을 할당시켜주니 난리가 났다.

그래서 생각한 방법이 가장 위에 있는 코드이다.
어차피 모든 탑이 필요하지 않다.
뒤에 오는 탑이 앞의 탑보다 크거나 같을 경우 다음 입력들에서 답으로 나올 확률은 없기때문에 과감하게 삭제하도록 변경해주었다.

말로는 쉽게 말하지만 생각하기까지 정말 오래걸린 문제...
늘 구현만 하다가 이렇게 자료구조를 사용해 대가리를 굴리는 문제를 푸니 좀 어렵게 느껴졌다.