백준[17298]번: 오큰수 ( Java )

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

17298번: 오큰수

개발환경은 eclipse를 사용했습니다.

 

 

 

Code

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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		StringTokenizer st;
		
		Stack<Integer> stack = new Stack<>();
		
		int n = Integer.parseInt(br.readLine()); // n의 개수
		
		st = new StringTokenizer(br.readLine()," "); // 문자열 받기
		
		int[] arr = new int[n];
		
		for(int i=0;i<n;i++) // 배열에 저장
		{
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		for(int i=n-1;i>=0;i--) // 역순열로 계산
		{
			
			if(stack.isEmpty()) // 스택이 비어있다면 그값을 넣어주고 문자열 자리에 -1 저장
			{
				stack.push(arr[i]);
				arr[i] = -1;
			}
			
			else // 스택이 비어있지 않은 경우
			{
				if(arr[i] < stack.peek()) // 가장 최근의 스택(가장 왼쪽)이 더 큰 경우 문자열에 저장하고 스택에 push
				{
					int temp = stack.peek();
					stack.push(arr[i]);
					arr[i] = temp;
				}
				
				else // 가장 최근의 스택(가장 왼쪽)이 작은 경우
				{
					while(!stack.isEmpty()) // 반복(break로 빠져나올것)
 					{
						stack.pop(); // 제거해서 가장왼쪽이 아닌 그 다음 수를 비교한다
						if(stack.isEmpty()) // 다 제거해서 스택이 빈 경우 -1저장 후 break
						{
							stack.push(arr[i]);
							arr[i] = -1;
							break;
						}
						
						else if(arr[i] < stack.peek()) // 크다면 위와 동일하게 바꾼 후 break
						{
							int temp = stack.peek();
							stack.push(arr[i]);
							arr[i] = temp;
							break;
						}
					}
					
				}
			}
		}
		
		for(int i=0;i<n;i++) // 출력
		{
			bw.write(arr[i]+" ");
		}
		
		bw.close();
		
	}
}

---

밑에 틀린 코드를 보면 알겠지만 시간초과가 계속 나서 풀이방식을 바꿔야 했다. 

 

풀이방법을 모르겠어서 구글링을 통해서 다른 분의 해결방법을 참고했다.

다른 분들이 푼 방식 보면 어떻게 저렇게 아이디어가 생각날 수 있는 거지?라고 느껴진다...

 

풀이 방법을 알고 노트로 순서대로 쓰면서 풀었더니 해결되었다.

 

 

 

틀린 코드

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));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		Stack<Integer> stack = new Stack<>();
		Stack<Integer> NewStack = new Stack<>();
		
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine()); // 수열크기 입력받기
		int[] arr = new int[n];
		
		st = new StringTokenizer(br.readLine()," "); // 수열 입력받기
		
		for(int i=0;i<n;i++) // 스택에 추가
		{
			stack.push(Integer.parseInt(st.nextToken()));
		}
		
		for(int i=0;i<n;i++)
		{
			int max = -1;
			
			arr[i] = stack.peek(); // 뒤에서 부터 뽑기
			stack.pop();
			
			for(int j=i-1;j>=0;j--) // 이전의 수들 중 최댓값 찾기
			{
				if(max < arr[j])
				{
					if(arr[i] < arr[j])
					{
						max = arr[j];
						break;
					}
					else
					{
						max = -1;
					}
				}
			}
				
			NewStack.push(max);
		}
		
		for(int i=0;i<n;i++)
		{
			bw.write(NewStack.peek()+" ");
			NewStack.pop();
		}
		
		bw.close();
	}
}

---

처음에 이렇게 풀었는데 시간초과가 났다.

애초에 스택을 활용한 풀이가 아니고 입력값을 봤을 때 시간초과가 날 수밖에 없던 것 같다.

 

문제 풀이 아이디어가 잡힌다면 쉽게 풀 수 있었던 것 같다.