[JAVA/17298번] 오큰수

---

문제

---

입력 및 출력

---

풀이

import java.io.*;
import java.util.*;

class Main {
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 사용자로부터 입력받은 수 만큼 배열을 선언한다.
        int[] numArray = new int[Integer.parseInt(br.readLine())];

        // 공백 기준으로 받은 문자열을 자른다.
        StringTokenizer st = new StringTokenizer(br.readLine());

        // numArray의 길이만큼 반복문을 수행하여 입력받은 문자열의 값을 넣는다.
        for (int i = 0; i < numArray.length; i++) {
            numArray[i] = Integer.parseInt(st.nextToken());
        }

        // 후입선출 기능을 갖는 스택을 선언
        Stack < Integer > stack = new Stack < > ();

        // 출력문을 위한 StringBuilder 선언
        StringBuilder sb = new StringBuilder();

        // numArray의 길이만큼 반복문 수행
        for (int i = 0; i < numArray.length; i++) {
            // 스택이 비어있지 않고, numArray의 스택TOP 인덱스의 값이 numArray의 i번째보다 작을 경우
            while (!stack.isEmpty() && numArray[stack.peek()] < numArray[i]) {
                numArray[stack.pop()] = numArray[i];
            }
            // 스택에 i의 값을 넣는다.
            stack.push(i);
        }

        //스택이 비어있지 않았을 경우
        while (!stack.isEmpty()) {
            // numArray의 스택TOP 인덱스의 위치에 -1을 넣는다.
            numArray[stack.pop()] = -1;
        }

        // 결과 출력
        for (int i = 0; i < numArray.length; i++) {
            sb.append(numArray[i]).append(" ");
        }
        System.out.println(sb);
    }
}

---

결과 및 해결방법

[결과]

[정리]

<시행착오 1>

// 후입선출의 기능을 갖는 자료구조 스택 선언
Stack < Integer > stack = new Stack < > ();

// numArray의 길이만큼 반복문 수행
for (int i = 0; i < numArray.length; i++) {
    for (int j = i + 1; j < numArray.length; j++) {
        if (numArray[i] < numArray[j]) {
            stack.push(numArray[j]);
        }
    }
    if (!stack.isEmpty()) {
        while (stack.size() != 1) {
            stack.pop();
        }
        numArray[i] = stack.pop();
    } else {
        numArray[i] = -1;
    }
}

numArray[numArray.length - 1] = -1;

위 코드는 이중 반복문을 사용하여 모든 원소들을 비교한 후 값이 큰 경우에 한해 스택에 넣었다.

마지막 원소를 추출하기 위해 스택의 사이즈가 1이 아니라면 모든 원소를 팝 시키고 마지막 원소를 배열에 넣었다. 만약 스택이 비어있는 경우라면 -1을 넣었다.

오큰수의 조건 중 마지막 원소는 무조건 -1이라는 점을 착안하여 길이의 -1인덱스 지점에 -1의 값을 넣어주었다.

<시행착오 2>

// 선입선출의 기능을 갖는 자료구조 큐 선언
Queue < Integer > queue = new LinkedList < > ();

// numArray의 길이만큼 반복문 수행
for (int i = 0; i < numArray.length; i++) {
    for (int j = i + 1; j < numArray.length; j++) {
        if (numArray[i] < numArray[j]) {
            queue.add(numArray[j]);
            break;
        }
    }
    if (!queue.isEmpty()) {
        sb.append(queue.poll()).append(" ");
    } else {
        sb.append(-1).append(" ");
    }
}

위 코드에서 시간초과의 결과를 받았기 때문에 조금이라도 시간을 줄여보고자 선입선출의 구조를 갖는 자료구조 큐를 사용했다.

모든 동작방식은 동일하지만 위의 코드는 스택의 마지막 원소 전까지 뽑아내야하는 과정이 있었기 때문에 이를 생략하고자 큐를 사용하였다.

하지만 결과는 동일하게 시간초과

해결방법

• 위 코드의 가장 큰 문제점은 이중 반복문을 사용했다는 점이다. 위 코드는 최악의 경우 모든 원소를 탐색하기 때문에 O(n^2)의 시간이 걸렸다.

  또한 문제의 알고리즘 분류가 스택이였기 때문에, 스택을 사용하여 문제를 해결하려 노력했다.

• 스택이 비어있지 않거나, numArray의 stack.peek()인덱스 부분이 numArray의 i번째 인덱스보다 작을 경우, numArray의 stack.pop()의 인덱스에 numArray의 i번째 인덱스의 값을 넣는다.

  그 외의 경우, 스택에 i를 넣는다.

  스택이 비어있지 않았을 경우, stack.pop()을 통해 numArray의 값에 -1을 넣는다.

• 위와같이 수행할 경우 스택에는 반복문의 변수인 i의 값이 저장되고, 스택의 최상단의 값과 i 인덱스 값을 비교하여 클 경우 갱신하고 그렇지 않을 경우 -1을 넣어주는 방식으로 동작된다.

  또한 반복문 내부에 반복문을 사용했더라도 스택이 비어있지 않다는 조건과 numArray의 i인덱스의 값이 커야한다는 조건이 있기 때문에 통과할 수 있었다.