링크

문제 링크

문제 설명

KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오른쪽 방향으로 차례로 세우고, 각 탑의 꼭대기에 레이저 송신기를 설치하였다. 모든 탑의 레이저 송신기는 레이저 신호를 지표면과 평행하게 수평 직선의 왼쪽 방향으로 발사하고, 탑의 기둥 모두에는 레이저 신호를 수신하는 장치가 설치되어 있다. 하나의 탑에서 발사된 레이저 신호는 가장 먼저 만나는 단 하나의 탑에서만 수신이 가능하다.

예를 들어 높이가 6, 9, 5, 7, 4인 다섯 개의 탑이 수평 직선에 일렬로 서 있고, 모든 탑에서는 주어진 탑 순서의 반대 방향(왼쪽 방향)으로 동시에 레이저 신호를 발사한다고 하자. 그러면, 높이가 4인 다섯 번째 탑에서 발사한 레이저 신호는 높이가 7인 네 번째 탑이 수신을 하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신을 한다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신을 하지 못한다.

탑들의 개수 N과 탑들의 높이가 주어질 때, 각각의 탑에서 발사한 레이저 신호를 어느 탑에서 수신하는지를 알아내는 프로그램을 작성하라.

입력

첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 이상 100,000,000 이하의 정수이다.

출력

첫째 줄에 주어진 탑들의 순서대로 각각의 탑들에서 발사한 레이저 신호를 수신한 탑들의 번호를 하나의 빈칸을 사이에 두고 출력한다. 만약 레이저 신호를 수신하는 탑이 존재하지 않으면 0을 출력한다.

입출력 예제

풀이

1. 탑의 height, index를 포함할 수 있는 클래스를 선언한다.
2. top이 세워지는 순서대로 담을 수 있는 스택을 선언한다. (스택 안쓰면 시간초과)
3. 세워지는 탑이 신호를 보냈을 때, 받을 수 있는 탑이 나올때까지 top을 pop한다.
4. pop을 하다보니 stack이 비었다면 금방 세워진 탑이 제일 높은거니까 0을 출력한다.
5. 방금 세워진 탑의 신호를 받을 수 있는 탑이 나온다면 (arr[i] < top.peek().height 일때) top.peek().index를 출력하면 된다.
6. 아 그리고 입력은 Scanner가 아닌, BufferedReader로 받아야함. 아니면 메모리 초과가 난다!

이 문제는 3번의 시간 초과와, 2번의 메모리 초과를 겪은 후에 겨우 통과했다.

코드 1 (첫번째 버전)

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		int[] ans = new int[N];
		boolean[] visited = new boolean[N];
		for(int i = 0; i < arr.length; i++) {
			arr[i] = sc.nextInt();
		}
		
		for(int i = arr.length - 1; i >= 0; i--) {
			if(!visited[i]) {
				int temp = i;
				for(int j = i - 1; j >= 0; j--) {
					if(arr[temp] < arr[j]) {					
						ans[temp] = j + 1;
						temp = j;
						visited[temp] = true;
					}
				}
			}
		}
		for(int i = 0; i < ans.length; i++) 
			System.out.print(ans[i] + " ");
	}
}

입력을 다 받은 후 오른쪽 끝에서부터 왼쪽으로 쭉 훑었다.

중간에 visited를 선언하면서 루프를 덜 돌게 하려는 노력이 보인다!

코드 2 (두번째 버전)

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N + 1];
		int[] ans = new int[N + 1];
		arr[0] = 500001;
		for(int i = 1; i < arr.length; i++) {
			arr[i] = sc.nextInt();
			if(arr[i] < arr[i - 1]) {
				ans[i] = i - 1;
			}
			else { //arr[i]가 더 클때
				int temp = i - 1;
				while(arr[i] > arr[temp]) {
					temp = ans[temp];
				}
				ans[i] = temp;
			}
		}
		for(int i = 1; i < arr.length; i++) {
			System.out.print(ans[i] + " ");
		}
	}
}

음 솔직히 시간 복잡도는 똑같은데 입력을 받으면서 실시간으로 처리한다는 점에서 기분이 달랐다. 하지만 똑같은 퍼센테이지 진도에서 땡!

코드3 (메모리 초과 with Stack)

import java.util.*;
class Info {
	int height;
	int index;
	Info(int height, int index) {
		this.height = height;
		this.index = index;
	}
}
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		Stack<Info> top = new Stack<>();
		for(int i = 0; i < arr.length; i++) {
			arr[i] = sc.nextInt();
			while(!top.isEmpty() && top.peek().height < arr[i]) {
				top.pop();
			}
			if(top.isEmpty())
			{
				System.out.print("0 ");
			}
			else
			{
				System.out.print(top.peek().index + " ");
			}
			top.push(new Info(arr[i], i + 1));
		}
	}
}

블로그에서 풀이를 보고 스택이라는 힌트를 얻은 뒤 스택을 사용해서 풀었다.

정답률이 쭉쭉 올라가다가 갑자기 메모리 초과가 떠버린다 엥?

코드 4 (PASS)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
class Info {
	int height;
	int index;
	Info(int height, int index) {
		this.height = height;
		this.index = index;
	}
}
public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(bf.readLine());
		int[] arr = new int[N];
		String s = bf.readLine();
		StringTokenizer st = new StringTokenizer(s, " ");
		Stack<Info> top = new Stack<>();
		for(int i = 0; i < arr.length; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			while(!top.isEmpty() && top.peek().height < arr[i]) {
				top.pop();
			}
			if(top.isEmpty())
			{
				System.out.print("0 ");
			}
			else
			{
				System.out.print(top.peek().index + " ");
			}
			top.push(new Info(arr[i], i + 1));
		}
	}
}

휴 겨우 통과했다...

Scanner를 50만번 돌리게 하면 메모리 초과가 난다고 한다.

그래서 BufferedReader를 사용하여서 이번 같은 경우에는 입력을 두 번 받는다.

int N = Integer.parseInt(bf.readLine())
String s = bf.readLine()

이거 총 두번인데 s를 대신 StringTokenizer로 쭈우우우우욱 분리해서 배열에다 담은 뒤 st.nextToken()으로 값에 접근하는 방식으로 해야 메모리 초과가 나지 않는다!

백준 사이트 푸는사람들 보면 보통 이런 식으로 입력을 받긴한데 나도 이제부터 이렇게 입력을 받아야겠다 ㅎㅎ