[Gold 4] 오큰수 구하기

문제출처

---

💡IDEA

• 배열로 구현한 Stack ( 클래스로 구현 )

class MyStack{
	//정해진 크기
	private int[] arr;
	private int top = -1;
    
	MyStack(int size){
		arr = new int[size];
	}
    //스택이 가득 찼는가? (Stack 배열 한정)
  	boolean isFull(){
		if(top == (arr.length-1))
			return true;
		return false;
	}
	
    //스택이 비었는가?
	boolean isEmpty(){
		if(top == -1)
			return true;
		return false;
	}

	void push(int data){
		//Stack이 다 찼는지 확인
		if(!isFull()){
			top++;
			arr[top] = data;
		}
	}

	int pop(){
		if(!isEmpty()){
				int data = arr[top];
				top--;
				return data; 
		}
		//스택이 비었을때
		return -1;
	}

	int peek(){
		if(!isEmpty()){
			return arr[top];
		}
		return -1;
	}
}

---

⚙️Build

public class App8 {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());		

		//수열 A
		int[] A = new int[N];

		//정답을 저장할 배열 answer
		int[] answer = new int[N];
		int index = 0;
        
		//수열 A 값 입력
		String[] data = br.readLine().split(" ");	//공백으로 나눠서 값 받음
		for(int i=0; i<N; i++){
			A[i] = Integer.parseInt(data[i]);
		}
		
        //스택 생성
		MyStack stackManager = new MyStack(N);

		//마지막 원소까지 push 됐을때 끝내는 While
		while(index < N){

			//스택이 안비었을때 각 수의 오큰수 정하기
			while(!(stackManager.isEmpty()) && (A[stackManager.peek()] < A[index])){
				answer[stackManager.peek()] = A[index];
				stackManager.pop();
			}

			//index push
			stackManager.push(index);
			index++;
		
		}

		//오큰수가 없으면 스택에 남는다
		while(!stackManager.isEmpty()){
			answer[stackManager.peek()] = -1;
			stackManager.pop();
		}
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		for(int i=0; i<N; i++)
			bw.write(answer[i] + " ");
		bw.flush();
	}
}


(myStack Class)

🤔🤔 왜 복잡하게 값을 스택에 넣고 비교 안하고 값의 인덱스를 스택에 넣고 비교하나?

단순한 수의 비교가 아니라 큰 수 중 가장 왼쪽의 값이 무엇인지 찾는것인데, 값을 가리키는 top으로 하기에는 스택은 pop했다 push했다 위치변화가 일어나므로 answer 배열에 모든 정답이 들어 갈 순 없다. 그렇기에 스택에는 정확히 주어진 N개의 값만 왔다가 들어가야 한다는 논리를 이용했음.

🤔🤔 왜 배열로 했는가?

N의 크기가 정해져 있었고, 삽입 및 삭제 과정이 빈번하게 일어나기 때문에 그런 과정이 있을때마다 동적 할당 및 해제 하는 List보다 속도가 빠르기 때문이다.

ps)
java에서 제공하는 Stack을 사용해도 되지만 스택에 대한 더 깊은 이해를 위해 직접 구현