백준 17298, 오큰수

 

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

17298번: 오큰수

 

 

문제

 

---

알고리즘(접근방법)

처음 이 문제를 해결하기 위해서 접근했던 방법은 스택 자료구조를 사용하지 않고 이중 for문을 사용하였습니다. 하지만, 코드 제출 결과 시간 초과를 받았습니다. 제 코드의 테스트 결과 n=1,000,000으로 설정하였을 경우 165초정도 소요되었었습니다. 

 

따라서 이 문제를 해결하기 위해서 스택 자료구조를 사용하였습니다. 스택의 간단한 원리는 "후입선출(Last-In-First-Out)"입니다. 즉, 마지막에 들어온 데이터가 먼저 나가는 구조입니다. 

 

문제에서 요구하는 오큰수(NEG)는 수열에서 i번째 값보다 오른쪽에 있으면서 i번째 값보다 큰 수중 가장 왼쪽에 있는 수를 의미합니다. 만약 그러한 수가 없다면 -1로 표현합니다. 이를 정리하면 아래와 같습니다.

오큰수의 조건

1. 수열에서 i번째 값의 오큰수는 오른쪽에 존재해야함
2. i번째 값보다 커야함
3. i번째 값보다 큰수 중 제일 왼쪽에 위치한 값

 

{3,5,2,7}이라는 수열이 존재한다고 가정합니다.

3보다 큰수(5,7) 중 가장 왼쪽에 있는 수는 5입니다.

5보다 큰수(7) 중 가장 왼쪽에 있는 수는 7입니다.

2보다 큰수(2) 중 가장 왼쪽에 있는 수는 7입니다.

7보다 큰수(Ø) 중 가장 왼쪽에 있는 수는 존재하지 않으므로 -1입니다.

위 과정을 수행하면 오큰수의 수열은 {5,7,7,-1}가 됩니다.

 

위와 같이 어떤 수열에 대한 오큰수의 수열을 생성하기 위해서는 스택을 사용합니다. 스택의 저장되는 요소들은 현재의 원소와 비교할 이전 원소들의 인덱스입니다. 알고리즘의 수행 과정은 아래와 같습니다.

1. 수열을 탐색하면서 현재의 원소가 스택의 top이 가리키는 원소보다 작다면 현재의 원소가 오른쪽에는 있지만 이전 원소가 더 크다는 의미이므로 오큰수에는 만족하지 않습니다. 따라서 현재의 인덱스를 스택에 추가(push)합니다.
2. 만약 현재의 원소가 스택의 top이 가리키는 원소보다 크다면 현재의 원소는 이전 원소보다 오른쪽에 존재하고 값도 크고 제일 왼쪽에 위치한 것이므로 이전 원소를 현재의 원소값으로 초기화가 가능합니다. 따라서 스택의 top 원소를 제거(pop)하고 반환받은 인덱스 위치의 이전 원소값을 현재 원소 값으로 초기화합니다. 단, 이 과정은 한번으로 그치는 것이 아닌 반복과정입니다. 따라서 다시 현재의 원소와 스택의 top이 가리키는 이전 원소의 값과 비교합니다. 만약 이전 원소가 더 작다면 똑같이 스택에서 제거(pop)하고 현재 원소로 초기화합니다. 그러나 이전 원소가 더 크다면 1번 과정과 같이 현재 원소의 인덱스를 스택에 추가(push)합니다.
3. 1~2과정을 수행하고 스택에 요소가 남아있다면, 이 요소들의 수열의 원소값들은 너무 크거나 비교할 대상이 없는 경우이기 때문에 스택의 남아있는 인덱스 위치의 원소값들을 -1로 초기화합니다.

 

예를 들어 수열 {3,5,2,7}의 수행 과정은 다음과 같습니다.

 

위의 알고리즘 수행과정을 코드로 표현하면 다음과 같습니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;


public class Main {
		
	public static String solution(int[] seq, int n)
	{
		StringBuilder sb = new StringBuilder();
		Stack<Integer> stack = new Stack<Integer>();
		
		stack.push(0);	// 수열에서 0번째 값은 stack에서 꺼낼것이 없으므로 현재 인덱스 추가
		
		for(int i=1;i<n;i++)
		{
			// seq[i]와 seq[이전 인덱스] 비교 수행
			while(!stack.isEmpty() && seq[stack.peek()]<seq[i])
			{
				seq[stack.pop()] = seq[i];
			}
			// stack이 비었거나 seq[i]보다 크므로 i를 stack에 추가
			stack.push(i);
		}
		
		// 위 반복문이 끝났음에도 불구하고 남은 stack의 인덱스 값들은 
		// 자신보다 큰 값이 없거나 비교할 요소가 없는 경우임
		// 스택에 남아있는 인덱스 위치의 값들은 -1로 저장
		while(!stack.isEmpty())
		{
			seq[stack.pop()] = -1;
		}

		// 출력문 저장
		Arrays.stream(seq)
				.forEach(item->sb.append(item+" "));
		String result = sb.toString().trim();
		
		return result;
	}
	
	public static void main(String args[]) throws IOException
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		// String Array to Integer Array
		int[] seq = Arrays.stream(
						br.readLine()
							.split(" "))
								.mapToInt(Integer::parseInt)
									.toArray();
		
		System.out.println(solution(seq, n));
		
	}
}

 

 

 

References

백준 17298 오큰수
https://st-lab.tistory.com/196