[백준]17298 오큰수 - 자바/Java

17298번: 오큰수

🌱풀이

알고리즘

1. stack에는 정답 배열의 인덱스를 저장한다.
2. 최초 0번 인덱스는 stack에 저장되고, 변수 i가 1 → N인 반복문을 선언한다.
3. 만약 입력된 숫자를 기준으로 i번 인덱스의 값이 stack 내 top에 위치한 인덱스에 해당하는 배열의 값(…)보다 크면 최초의 오큰수의 해당한다.
4. 3번에 해당하는 경우 stack에서 pop을 사용해 top을 꺼내고, 애초에 인덱스를 넣어뒀으므로 정답 배열의 인덱스로, 입력될 값은 number[i]로 저장한다.
5. 3-4번을 stack을 계속 꺼내면서 조건을 충족하지 않을때까지 반복한다.
6. N번까지 반복되었음에도 stack에 남아있는 값은 오큰수가 없으므로 -1을 넣어준다.

회고

Stack은 후입선출의 자료구조다. 해당 문제에서는 후입선출이 무슨 용도로 쓰이는지 잘 와닿지 않았다. 위의 알고리즘이 성립하면 Stack에 쌓여있는 인덱스들은 오큰수를 만나지 못했다는 명제가 성립해야한다. 하지만 하나 하나 까본 것도 아닌데 어떻게 그걸 알 수 있었을까?

numbers[stack.peek()] < numbers[i] 이 조건이 성립할때만 오큰수가 있는 걸로 판명한다. 헷갈렸던 부분은, stack의 최상단 값에게는 오큰수가 아니더라도 이전 값들에게는 오큰수일 수 있다는 것이다. 그런데 4 3 1 7 5 같은 경우를 생각해보면 순회 값이 7에 해당할 때 stack에는 4,3,1이 쌓여있을 것이고, 이 때 하나씩 꺼내지면서 정답 배열에 입력될 것이다.

솔직히 잘 정리가 안되는데, 정리를 해보자면 이렇다.

numbers[stack.peek()] < numbers[i] 이 조건에 해당하지 않는 값들은 push 메소드를 통해 stack에 입력되므로, 지속적으로 오큰수가 발견되지 않는다고 하면 i번째와 i-1번째의 값의 비교가 일어나고 있는 것이다. 그러면서 위 조건이 만족한다는 것은, 입력된 값이 지속적으로 작아지고 있음을 의미한다. 그러다 한 번 오큰수가 발견되면 그동안 작아지기만 했던 값이 커졌다는 것이다. 그럼 일부에게 그 값은 오큰수가 되고, 아니라면 남은 값들과 다음 배열의 값을 비교하면서 나아간다. 이로서 위 알고리즘의 정당성이 입증되었다.

💡 메모리 : 317516KB, 시간 1108ms

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		int[] numbers = new int[N];
		int[] ans = new int[N];
		for(int i = 0; i<N; i++) numbers[i] = Integer.parseInt(st.nextToken());
		Stack<Integer> stack = new Stack<>();
		stack.push(0);
		
		//알고리즘
		for(int i = 1; i<N; i++) {
			while(!stack.isEmpty() && numbers[stack.peek()] < numbers[i]) {
				ans[stack.pop()] = numbers[i];
			}
			stack.push(i);
		}
		
		//스택에 남아있는 index에 해당하는 값들은 -1로 처리
		while(!stack.isEmpty()) ans[stack.pop()] = -1;
		for(int i = 0; i<N; i++) sb.append(ans[i]+" ");
		System.out.print(sb.toString());
		
		br.close();
	}
}

---

🪴코드 리뷰

🌿

Stack에 인덱스가 아니라 배열을 집어넣었다. 음, 이렇게 해서 좋은 점이 있나?

💡 풀이자 : rla0347, 메모리 : 375128KB, 시간 2060ms

import java.util.Arrays;
import java.util.Scanner;
import java.util.Stack;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // n개배열
		Stack<Integer[]> stack = new Stack<>();
		int[] arr = new int[n]; // 정답이 될 배열
		Arrays.fill(arr, -1); // -1로 채움
		for (int i = 0; i < n; i++) {
			int Ai = sc.nextInt();
			while (stack.size() > 0 && stack.peek()[0] < Ai) {
				arr[stack.pop()[1]] = Ai;
			} // 현재 들어온애보다 작은애까지 pop하고 그 인덱스에 현재값 넣어줌
			stack.push(new Integer[] { Ai, i });
		}

		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; i++) {
			sb.append(arr[i]).append(' ');
		}
		System.out.println(sb.toString());
	}
}

🌿

스택 수열에서 신기한 코드를 짰던 그 사람이다.

이번에도 마찬가지로 stack 객체를 선언하지 않고 정수형 배열을 선언하여 stack처럼 다루고 있다. 이제 조금 아래 코드가 보인다. 아래 코드를 이해하려면 stack 내에 저장되고 배출되는 값(인덱스)가 조건에 따라 어떻게 변화되는지를 꿰고 있어야한다. 역으로 말하면 아래 코드를 소화할 수 있으면 해결 알고리즘을 잘 이해한거라고도 할 수 있겠다.

출력을 할 때도 조금 번거로울 수 있지만 형식을 엄격하게 지키고 있다. 디테일이 살아있는 코드다.

💡 풀이자 : jeuk817 메모리 : 77716KB, 시간 480ms

public class Main {

	public static void main(String[] args) throws Exception {
		int N = nextInt();
		int[] A = new int[N];
		for(int i = 0; i < N; i++) {
			A[i] = nextInt();
		}

		int[] nge = new int[N];
		int[] stack = new int[N];
		stack[0] = 0;
		int top = 0, num;
		for(int i = 1; i < N; i++) {
			num = A[i];
			while(top > -1 && num > A[stack[top]]) nge[stack[top--]] = num;
			stack[++top] = i;
		}
		while(top > -1) nge[stack[top--]] = -1;
		
		StringBuilder sb = new StringBuilder();
		sb.append(nge[0]);
		for(int i = 1; i < N; i++) {
			sb.append(" ").append(nge[i]);
		}
		System.out.println(sb);
	}
	
	static final int SIZE = 1 << 13;
	static byte[] buffer = new byte[SIZE];
	static int index, size;
	static int nextInt() throws Exception {
		int sign = 0;
    	int n = 0;
    	byte c;
    	while ((c = read()) <= 32);
    	if(c == 45) {
    		sign = 1;
    		c = read();
    	}
    	do n = (n << 3) + (n << 1) + (c & 15);
    	while ((c = read()) > 47 && c < 58);
    	return sign == 0 ? n : ~n + 1;
    }
	static byte read() throws Exception {
        if (index == size) {
            size = System.in.read(buffer, index = 0, SIZE);
            if (size < 0) buffer[0] = -1;
        }
        return buffer[index++];
    }
}

---

Conclusion

• Stack이 아직 좀 어렵다..