[백준] 단계별로 풀어보기(단계:18,스택,JAVA)17298번, 오큰수

문제 링크

17298번: 오큰수

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

기본적으로 스택이란 LIFO(후입 선출)의 자료구조입니다.

LIFO는 먼저 들어간 데이터들이 출력할 때 나중에 나온다는 이야기입니다.

예를 들어 3, 2, 1을 순서대로 스택에 저장한 뒤 하나씩 꺼내보겠습니다.

1. 스택에 3을 넣었을 때

3

2. 스택에 2을 넣었을 때

2

3

3. 스택에 1을 넣었을 때

1

2

3

4. 스택에 하나의 자료를 출력하라는 명령이 떨어졌을 때

1

2

3

5. 다시 자료를 출력하라는 명령이 떨어졌을 때

2

3

위에 표를 보면 간단히 돌탑을 생각하시고 돌을 뺄 때 나중에 올린 돌부터 빼는 것처럼 스택은 LIFO의 형태를 가진 자료구조입니다.

 

이 문제를 접근할 때 스택을 어떻게 사용해야 하는지 고민을 많이 하였습니다.

그래서 오큰수를 저장하는 방법도 사용해보았고, 입력값을 저장하는 방법도 사용해보았지만 실패하였습니다.

마지막으로 배열에 숫자를 저장하고 인덱스를 스택에 저장해보는 방법을 사용하였을 때 문제가 해결되었습니다.

코드가 진행되는 기본적인 구조는

예를들어 4 3 2 1 2 3 4가 입력되었을 때(빨간색 : 기준 되는 수, 초록색 : 오큰수 찾은 수)

각 숫자마다 앞에 나온 숫자에 대하여 자신이 오큰수가 되는지 확인하는 방법을 사용하였습니다.

4 3 2 1 2 3 4 => 4가 오큰수가 될 수 없으므로 그냥 넘어갑니다.

4 3 2 1 2 3 4 => 3은 왼쪽에 있는 4와 비교할 수 있지만 4보다 작으므로 그냥 넘어갑니다.

4 3 2 1 2 3 4 => 2는 왼쪽에 있는 4,3과 비교할 수 있지만 두 수보다 작으므로 그냥 넘어갑니다.

4 3 2 1 2 3 4 => 1은 왼쪽에 있는 4,3,2와 비교할 수 있지만 그 수보다 작으므로 그냥 넘어갑니다.

4 3 2 1 2 3 4 => 2은 왼쪽에 있는 4,3,2,1과 비교할 수 있으며 1보다는 크기 때문에 1의 오큰수는 2가 됩니다.

4 3 2 1 2 3 4 => 3은 왼쪽에 있는 4,3,2,2와 비교할 수 있으며 2보다는 크기 때문에 2의 오큰수는 3이 됩니다.

4 3 2 1 2 3 4 => 4는 왼쪽에 있는 4,3,3와 비교할 수 있으며 3보다 크기 때문에 3의 오큰수는 4가 됩니다.

4 3 2 1 2 3 4  => 오큰수를 찾지 못한 4는 문제에 내용처럼 -1로 표현됩니다.

결과적으로 오큰수  = -1 4 3 2 3 4 -1

 

이 알고리즘을 코드에 적용시키기 위해 스택에 배열 index를 저장하여 오큰수가 발견된 인덱스는 스택에서 pop을 진행하여 그에 대응하는 오큰수값들을 저장하는 배열에 저장하는 방식을 사용하였습니다.

num = 입력된 숫자들 저장하는 배열

ans = 오큰수 저장하는 배열

stack = 배열들의 인덱스 저장하는 스택(오큰수를 찾은 인덱스이면 pop진행)

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 통해 입력 값을 띄어쓰기 기준으로 나누었습니다.
• 반복을 통해 위에 알고리즘을 적용시켰습니다.
• 오큰수를 찾으면 스택에서 pop을 진행하고 다음수도 오큰수인지 확인하도록 while문을 통해 반복하였습니다.
• 반복이 끝나고 스택에 남아있는 인덱스는 오큰수를 찾지 못한 것으로 -1로 ans에 저장하였습니다.
• 오큰수 저장 배열 ans에 값들을 BufferedWriter에 저장하였습니다.
• BufferedWriter를 사용하여 저장된 결과를 출력하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static int size;	//입력 개수
	static Stack<Integer> stack = new Stack<Integer>();	//배열 index 저장 스택
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //BufferedWriter를 통해 결과 값 출력
        //--------배열 초기화----------
    	size = Integer.parseInt(br.readLine());
    	int[] num = new int[size];	//입력 값 저장 배열
    	int[] ans = new int[size];	//오큰수 저장 배열
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //--------입력 값 저장 및 함수 실행------------
    	for(int i=0;i<size;i++) {
    		num[i] = Integer.parseInt(st.nextToken());
            //오큰수 찾는 연산
    		while(!stack.empty() && num[i] > num[stack.peek()]) {
    			ans[stack.pop()] = num[i];
    		}
    		stack.push(i);	//배열 index push
    	}
    	while(!stack.empty()) {
    		ans[stack.pop()] = -1;	//오큰수 없는 경우
    	}
    	for(int i=0;i<size;i++) {
    		bw.write(ans[i] + " ");	//결과 BufferedWriter에 저장
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
	}
}