[백준] 17298번 오큰수 JAVA (자바) 풀이

문제 17298번

 :  크기가 N인 수열 A = A1, A2, ..., AN

 :  수열의 각 원소 Ai에 대해서 오큰수 NGE(i)를 구하기

 

 :   Ai의 오큰수는 오른쪽에 있으면서 Ai보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미

    그러한 수가 없는 경우에 오큰수는 -1

  (예시)

    A = [3, 5, 2, 7]인 경우 NGE(1) = 5, NGE(2) = 7, NGE(3) = 7, NGE(4) = -1
    A = [9, 5, 4, 8]인 경우 NGE(1) = -1, NGE(2) = 8, NGE(3) = 8, NGE(4) = -1이다.

 

 

 [입력]

 :  첫째 줄에 수열 A의 크기 N

 :  둘째 줄에 수열 A의 원소 A1, A2, ..., AN 

 

 [출력]

 :  총 N개의 수 NGE(1), NGE(2), ..., NGE(N)을 공백으로 구분해 출력

 

 [문제 이해]

 

 :  너무 헷갈리네요 .. 이해하는데 한참 걸린 것 같아요

 

 : 수열 {3, 7, 8} 이라면 3과 바로옆 7과 비교합니다 값이 더 크다면 오큰수가 됩니다

   왼쪽부터 오른쪽 ---> 방향으로 차근차근 해당하는 수보다 큰 수가 있는지 비교하는 원리입니다

   큰 수가 없다면 -1을 출력합니다

 

 : 하지만 코딩을 짤 때에는 해당하는 숫자의 오른편에 있는 모든 수들을 하나하나 맞는지 확인하려면 

   시간복잡도 때문에 수행 X

 

  - 해결방법 1) 각각의 값 대신에 Index 즉 일종의 번호표를 붙여 만든다

  - 해결방법 2) 하나씩 비교하지 말고 일단은 바로 옆의 수만 비교하고 넘어가기

 

 

  <그림설명>

 

수열	3	5	2	7
Index	0	1	2	3

이렇게 번호표인 Index 를 붙여서 풀거예요

스택에 수열대신에 index를 넣어서 풀기만 하면 됩니다

 

 

1단계	2단계	3단계	4단계	5단계	6단계
	1		2
0	0	1	1	1	3

 * 이 스택에 들어가는 수는 수열이 아닌 Index 이다  

단계 1)

처음에는 스택에 아무 것도 없어서 일단 Index 0 번의 수를 넣고 시작

0을 넣었지만 사실상 Index 0 을 가진 3이다

 

단계2)

스택의 peek인 Index 0이자 3을 바로 옆의 수 5와 비교한다 

비교해보고 더 큰 수라면 5를 오큰수로 지정한다

그리고는 다음 비교 대상인 Index 1 을 추가한다

 

단계3)

오큰수가 나왔기 때문에 비교한 이전 수 3은 더이상 비교할 일이 없다

3은 스택에서 pop 즉 Index 0 제거

그러면 스택의 peek는 5 즉 Index 1이 된다

 

단계4)

스택의 peek인 5와 그 다음수 2를 비교한다

오큰수가 아니기 때문에 더 이상 비교하지 X

비교한 수 2이자 Index 2를 스택에 추가한다 

그러면 스택의 peek는 2가 된다

 

단계5)

스택의 peek인 2와 그 다음수 7을 비교한다

오큰수이므로 peek인 2를 pop 한다

 

단계6)

스택의 peek가 다시 Index 1이자 5로 바뀌었다

그 peek와 7을 비교해본다 (단계4 에서 못 찾은거 다시 한 번 찾아보는 것)

7이 더 커서 오큰수가 되었다

이제 peek인 5를 더이상 쓸 일이 없어서 pop하기

그다음 비교대상인 Index 3 이자 7을 추가

 

오 큰 수    결   과
5	7	7	- 1
단계 2 참고	단계 5 참고	단계 6 참고	비교 대상 없어서

** 이론적인 부분은 유튜브 하루코딩 보고 공부했어요 하루코딩 참고하시면 좋을 것 같아요**

 

 

 [스택 연산]

 

push(e)	스택의 맨 위에 요소 e 추가
pop()	스택의 맨 위 요소를 삭제
peek(s)	스택의 맨 위 요소를 삭제하지 않고 반환
top()	스택 맨 위에 있는 데이터 값 반환
isEmpty()	스택에 원소가 없으면 'True', 있으면 'False' 값 반환
isFull()	스택에 원소가 없으면 'False', 있으면 'True' 값 반환

 

 [코드]

import java.util.*;
import java.io.*;
public class Main{
    public static void main(String[] args)throws IOException{	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Integer> stack = new Stack<>();
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		
        
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
 
		for(int i = 0; i < N; i++) {
			
			while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
				arr[stack.pop()] = arr[i];
			}
			
			stack.push(i);
		}
		
		while(!stack.isEmpty()) {
			arr[stack.pop()] = -1;
		}
		
		for(int i = 0; i < N; i++) {
			sb.append(arr[i]).append(' ');
		}
		
		System.out.println(sb);
	}
}

 

 [해설]

 :  Stack<Integer> stack = new Stack<>();  스택선언 숫자니까 Integer로

 :  int N = Integer.parseInt(br.readLine());  첫째줄 개수 입력

 :  int[] arr = new int[N];  크기 N의 배열 만들기

 :  StringBuilder sb = new StringBuilder(); 출력할때 필요하다

 :  StringTokenizer st = new StringTokenizer(br.readLine(), " ");  한줄을 읽어오는데 공백을 기준으로 숫자를 구분한다

 :  for(int i = 0; i < N; i++) {
             arr[i] = Integer.parseInt(st.nextToken()); 배열 arr 안에는 수열을 순서대로 넣어준다
    }
 

 :  for(int i = 0; i < N; i++) {
              while(!stack.isEmpty() && arr[stack.peek()] < arr[i]) { 스택 비어있지x, peek값이랑 다음수열 비교
                             arr[stack.pop()] = arr[i];  스택에서 Index 값 빼주고 배열은 해당 수열 오큰수로 변경하기
              }
             stack.push(i);  스택안에 넣는 것은 Index다 그래서 스택안에는 i만 넣는 것을 볼 수 있다
    }

   어렵게 생각할 것 없이 위의 [문제이해]에서 설명한 단계들을 보면 스택안의 peek값과 그다음 수들을

   비교하는 방식으로 연산이 이루어지는 것을 볼 수 있다  

   그래서 스택이 비어있지 않고 peek값의 Index에 해당하는 배열을 다음 배열의 수와 비교했을때

   peek인 수가 더 작다면 오큰수를 찾은것이므로 스택에서 peek값을 제거하고

   그 자리에 오큰수 (비교당했던 다음 수열) 을 집어넣는다

   그리고 스택에 오큰수의 Index 값을 push (이번엔 오큰수로 지정된 숫자가 기준이 되어 다음 수열과 비교)

 :  while(!stack.isEmpty()) {  이건 맨마지막 부분이다 Index가 비어있지 않은데 비교할 값이 존재x 경우
               arr[stack.pop()] = -1;  배열을 -1로 바꾼다
    }

 :  for(int i = 0; i < N; i++) {
              sb.append(arr[i]).append(' '); 공백과 같이 배열 출력하기
    }

 :  System.out.println(sb);  출력

  

 

이제 풀어보러 갈께요 :)

 

 

 

https://www.acmicpc.net/problem/17298

17298번: 오큰수

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *