/ BOJ

BOJ_17298_오큰수_JAVA

문제 : 오큰수

링크 : BOJ_17298_오큰수

접근 방식

오큰수는 오른쪽에 있으면서 해당 수보다 큰 수 중에, 가장 왼쪽에 있는 수를 의미한다.

스택을 이용해서 문제를 해결해보자.

예를 들어, 3,5,2,7 이라는 수열이 있다고 가정해보자. 각 수열의 요소에 오큰수를 가져오는 로직을 스택을 이용해 구현한다.

17298_1

  1. (3,5,2,7) 에 대응되는 빈 수열 (0,0,0,0)을 만든다. (-1,-1,-1,-1)이어도 상관없다. 빈 수열에는 오큰수를 할당한다.

  2. 처음에 3이 push된다. 3보다 작은 수는 현재 스택에 없다.

  3. 2번째 값은 5이다. 현재 스택의 top인 3은 5보다 작으므로, 3을 pop한다.

  4. 스택은 3이 pop 되어 비어 있으므로 더 이상 비교하지 않는다. 5를 push한다.

  5. 3이 pop되었으므로, 원래 3이 있던 수열의 자리에 5를 할당한다.

  6. 3번째 값은 2이다. 현재 스택의 top는 5, 2보다 큰 수이므로 5는 그대로 둔 채 2를 push한다.

  7. 4번째 값은 7이다. 현재 스택의 top는 2, 7보다 작은 수이므로 2를 pop한다.

  8. 2가 pop되었으므로, 원래 2가 있던 수열의 자리에 7을 할당한다.

  9. 다음 스택의 top는 5, 7보다 작은 수이므로 5를 pop한다.

  10. 5가 pop되었으므로, 원래 5가 있던 수열의 자리에 7을 할당한다.

  11. 모든 수를 탐색한 뒤 현재까지 할당된 오큰수의 수열은 다음과 같다. (5,7,7,0) or (5,7,7,-1).

9,5,4,8 이라는 수열을 통해 또 하나 예를 들어보았다.

17298_2

  1. 처음에 9가 push된다. 9보다 작은 수는 현재 스택에 없다.

  2. 2번째 값은 5이다. 현재 스택의 top인 9은 5보다 큰 수이므로, pop 하지 않고 5를 push한다.

  3. 3번째 값은 4이다. 현재 스택의 top인 5는 4보다 큰 수이므로, pop 하지 않고 4를 push한다.

  4. 4번째 값은 8이다. 현재 스택의 top인 4는 8보다 작은 수이므로, 4를 pop한다.

  5. 4가 pop되었으므로, 원래의 4가 있던 수열의 자리에 8을 할당한다.

  6. 다음 스택의 top은 5, 8보다 작은 수이므로 5를 pop한다.

  7. 5가 pop되었으므로, 원래의 5가 있던 수열의 자리에 8을 할당한다.

  8. 다음 스택의 top는 9, 8보다 큰 수이므로 pop 하지 않고 8을 push한다.

  9. 모든 수를 탐색한 뒤 현재까지 할당된 오큰수의 수열은 다음과 같다. (0,8,8,0) or (-1,8,8,-1)

두 개의 경우 모두 빈 수열을 0으로 초기화 했다면, 반복문을 돌려 빈 수열의 값이 0일 경우에는 -1로 바꿔준다.

풀이 방법

  1. Stack 클래스를 사용해서 Integer 스택을 생성한다. 변수 N에 수열 개수를 읽어와 저장한다.

  2. 오큰수를 저장할 빈 수열을 배열 B로 선언해서 초기화한다.

  3. 수열의 개수만큼 반복한다.(i= 0~N)

  4. int 변수 cnt를 선언하고, i를 저장한다.

  5. int 변수 K에 수열의 값을 읽어온다.

  6. 중첩 반복문으로, 스택이 비어있거나 수열의 값보다 스택의 최상위 값이 작으면 stack를 pop하고 cnt를 감소시켜가면서 B[cnt]의 값이 0일 때만 K를 할당한다.

  7. stack이 비어있거나, 수열의 값보다 스택의 최상위 값이 더 크면 중첩 반복문을 종료한다.

  8. 반복문 종료 후에 K를 stack에 push한다.

  9. 모든 반복문을 종료한 후 오큰수를 저장한 수열 B를 출력한다. (초기화를 0으로 했다면, 0일 경우 -1로 바꿔주도록 하자.)

소스 코드


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Stack;

public class BOJ_17298_오큰수 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(in.readLine());
		String[] str = in.readLine().split(" ");
		Stack<Integer> stack = new Stack<>();
		// Map으로 하니 중복일 때 덮어씌워버리는 문제 발생
		Map<Integer, Integer> map = new HashMap<>();
		int[] B = new int[N];
		// 스택으로 풀어보기
		for (int i = 0; i < N; i++) {
			int K = Integer.parseInt(str[i]);
			int cnt = i;

			while (true) {
				if (!stack.empty() && stack.peek() < K) {
					// 해당 조건문이 없다면 이미 값이 들어있는 경우에도 덮어쓰기가 되어버린다.
					// 2 1 2 3
					// 0 2 0 0 // 2 2
					// 2 1 2 3 // 2 2 3
					// 0 2 3 0
					if (B[--cnt] != 0) {
						continue;
					} else {
						B[cnt] = K;
					}

					stack.pop();
				} else {

					break;
				}
			}
			stack.push(K);
		}
// 스택 안쓰고 풀어보기 - 시간초과		
//		go:for(int i=0;i<N;i++) {
//			for(int j=i;j<N;j++) {
//				if(A[i] < A[j]) {
//					arr.add(A[j]);
//					continue go;
//				}
//			}
//			arr.add(-1);
//		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; i++) {
			if (B[i] == 0) {
				B[i] = -1;
			}
			sb.append(B[i]).append(" ");
		}
		System.out.print(sb);

	}

}