17298 자바 ] 오큰수(풀이)

※ 문제

닫기

출처 : (https://www.acmicpc.net/problem/17298)

---

(결과)

1. 실패

 1) 설계

  - 우선 정확성을 고려하여 어떻게 코딩할 것인지 생각했다. 내가 생각한 로직은 이러하다.

-----반례-----

4

3 5 2 7

완전 탐색으로 순서대로 하나하나 전부 비교하는 것이었다.

결과는 '시간 초과'가 발생하였다.

 

 2) 실패 코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static Queue<Integer> queue = new LinkedList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] arr = new int[N];
        for(int i=0; i<N; i++) {
            int num = Integer.valueOf(st.nextToken());
            queue.offer(num);
            arr[i] = num;
        }

        int i = 0;
        int repeatCnt = 1;
        while(!queue.isEmpty()) {
            int queNum = queue.poll();
            boolean minOneSe = true;

            i = repeatCnt;
            while(i < N) {
                if(queNum < arr[i]) {
                    bw.write(arr[i]+" ");
                    minOneSe = false;
                    break;
                }
                i++;
            }

            repeatCnt++;
            if(minOneSe) bw.write(-1+" ");
        }

        bw.flush();
        bw.close();
    }
}

 

2. 성공

 1) 설계

  - 완전 탐색으로 이중 for문을 사용하면 '시간 초과'가 발생하기 때문에 반복문 하나로 해결할 수 있는 방법을 생각했다.

    실패 로직과 반대로 뒤에서부터 비교해보려 했다.

 

전체 프로세스

 

스택 상세 프로세스

먼저,

가로 ①. 7은 가장 오른쪽에 있기 때문에 비교 값이 존재하지 않는다. 이 경우 결과 스택에 -1을 push 하고 임시 스택에 7을 push 한다.

가로 ②. 2는 임시 스택에 있는 7과 비교한 후 결과스택에 push 하고 임시 스택에 2를 push 한다.

가로 ③. 5는 임시 스택에 2보다 크기 때문에 2는 pop 해서 제거해준다.

가로 ④. 5와 7 비교 후 결과 스택에 push 하고 임시 스택에 5를 push 한다.

가로 ⑤. 3과 5 비교 후 결과 스택에 push 한다.

가로 ⑥. 결과를 다 구했으므로 break; 종료한다.

 

 2) 성공코드

import java.io.*;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    static Stack<Integer> stack = new Stack<>();
    static Stack<Integer> resultStack = new Stack<>();
    static Stack<Integer> tempStack = new Stack<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        while(N --> 0) {
            stack.push(Integer.valueOf(st.nextToken()));
        }

        int idx = 0;
        while(!stack.isEmpty()) {
            int temp = stack.pop();

            if(idx == 0) { // 우측에 값이 없기 때문에 -1
                tempStack.push(temp);
                resultStack.push(-1);
            } else if(!tempStack.isEmpty() && temp <= tempStack.peek()) {
                resultStack.push(tempStack.peek());
                tempStack.push(temp);
            } else {
                if(tempStack.isEmpty()) {
                    resultStack.push(-1);
                    tempStack.push(temp);
                } else {
                    tempStack.pop();
                    stack.push(temp);
                }
            }

            idx++;
        }

        while(!resultStack.isEmpty()) {
            bw.write(resultStack.pop() + " ");
        }
        bw.flush();
        bw.close();
    }
}

---

문제의 예제는 모두 통과하였으나 정확도의 이슈가 해결되지 않은 분은 아래 반례로 확인해보길 바란다.

※ 반례 모음

3
1 3 2
정답 : 3 -1 -1

3
2 1 2
정답 : -1 2 -1

 

3

1 2 3

정답 : 2 3 -1

 

3

3 2 1

정답 : -1 -1 -1