백준 17298번 자바 ☆

문제

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

17298번: 오큰수

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

	static int N;
	static int[] sequence;
	static int[] NGE;
	static Stack<Integer> stack;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		sequence = new int[N];
		NGE = new int[N];
		stack = new Stack<Integer>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for (int i=0; i<N; i++) {
			sequence[i] = Integer.parseInt(st.nextToken());
		}
		
		stack.push(0); // 현재 원소와 스택의 top값을 비교해야하는데 0번째 원소는 스택이 비어있는 상태이기 때문이다.
		for (int i=1; i<N; i++) {
			if (sequence[i] <= sequence[stack.peek()]) {
				stack.push(i);
				continue;
			}
			
			if (sequence[i] > sequence[stack.peek()]) {
				while (sequence[i] > sequence[stack.peek()]) {
					
					NGE[stack.pop()] = sequence[i];
					if (stack.isEmpty()) {
						break;
					}
				}
				
				stack.push(i);
			}
		}
		
		while (!stack.isEmpty()) {
			NGE[stack.pop()] = -1;
		}
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		for (int i=0; i<N; i++) {
			bw.write(NGE[i] + " ");
		}
		bw.write("\n");
		bw.flush();;
	}
}

1. Stack을 이용해 풀어야하는 문제다. 포인트는 Stack에 push되는 값이 sequence[i]가 아닌 인덱스 i가 push되는것이다.

 

2. 먼저 비어있는 스택에 첫번째 인덱스 0을 넣어줘야한다. 현재원소와 스택의 top값을 비교해야하는데 첫번째 인덱스 일때는 스택이 비어있기 때문이다.

 

그 다음, for문을 통해 sequence 배열을 다음 원소로 하나씩 이동한다. 

현재 sequence원소가 스택 top을 인덱스로 하는 sequence보다 작거나 같을 때 스택에 현재 원소의 인덱스를 넣어준다.

 

 

현재 sequence원소가 스택 top을 인덱스로 하는 sequence보다 클 때는

스택의 top을 인덱스로 하는 sequence가 현재 sequence원소보다 클 때까지 pop을 한다.

-> NGE[stack.pop()] = sequence[i];

-> 스택에 저장되어있는 인덱스의 원소들이 오큰수(현재 원소)를 만나면서 NGE배열 해당 인덱스에 현재 원소 값이 저장된다.

 

이때 만약 스택이 완전히 비워 진다면 while문을 탈출한다. 

-> 스택이 다 비워졌음에도 while문의 조건을 만족 못하는 경우가 있기 때문이다.

 

위 과정을 마친 후 현재원소의 인덱스를 다시 스택에 push해준다.

-> 해당 인덱스부터 다시 오큰수를 찾아야하기 때문이다.

 

sequence배열을 모두 탐색한 뒤 스택에 남아있는 요소들을 pop해주면서 값을 -1로 해준다.

-> 스택에 남아있는 원소들은 오큰수가 없기 때문이다.

 

 

정리 : 스택의 개념을 이해는 하지만 문제에 적용시키는건 또 다른 문제인듯하다. 스택에 당연히 값을 넣어야 한다고 생각했는데 인덱스를 넣는다는게 아직 갈길이 많이 멀구나 생각이 든다. 그리고 stack으로 푸는 것 뿐 아니라 입출력도 BufferedReader, BufferedWriter를 둘중 하나는 활용해야 시간이 통과 된다. 

 

마지막으로 내 코드보다 간결하고 명확한 코드가 있어서 첨부한다.

처음부터 좋은 코드를 작성하면 좋지만 일단은 직관적으로 작성하고 그 뒤에 내 코드를 어떻게 수정할 수 있을까 계속 고민해 보자. indent depth가 적을 수록 좋다. 예를들자면 반복문안에 조건문 작성하는 것이 대표적이다.

import java.util.*;
import java.io.*;
public class P17298_오큰수 {
  public static void main(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(bf.readLine());
    int[]A = new int[n];    // 수열 배열 생성
    int[]ans = new int[n]; // 정답 배열 생성
    String[] str = bf.readLine().split(" ");
    for (int i = 0; i < n; i++) {
        A[i] = Integer.parseInt(str[i]);
    }
    Stack<Integer> myStack = new Stack<>();
    myStack.push(0); // 처음에는 항상 스택이 비어있으므로 최초 값을 push하여 초기화
    for (int i = 1; i < n; i++) {
        //스택 비어있지 않고 현재 수열이 스택 TOP인덱스 가르키는 수열보다 크면
        while (!myStack.isEmpty() && A[myStack.peek()] < A[i]) {  
            ans[myStack.pop()] = A[i];  //정답 배열에 오큰수를 현재 수열로 저장하기
        }
        myStack.push(i); //신규데이터 push  
    }
    while (!myStack.empty()) {
        // 반복문을 다 돌고 나왔는데 스택이 비어있지 않다면 빌 때 까지
        ans[myStack.pop()] = -1;
        // stack에 쌓인 index에 -1을 넣고
    }
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    for (int i = 0; i < n; i++) {
        bw.write(ans[i] + " ");
        // 출력한다
    }
    bw.write("\n");
    bw.flush();
  }
}
//출처 : https://github.com/doitcodingtestjava/answer/blob/main/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0/P17298_%EC%98%A4%ED%81%B0%EC%88%98.java