[백준] 2075.N번째 큰 수 (java) / 시뮬레이션?

@시뮬레이션? / 26m

시간과 메모리가 터지지 않을까 걱정돼서

그냥 무작정 풀면 안 될 것 같아서 고민 좀 하고 풀었다.

무난한 문제였음!

 

 

문제 링크

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

2075번: N번째 큰 수

 

 

생각의 흐름

1. 중복되는 값이 없으므로, 처음에는 그냥 int형 배열을 만들어서 거기 index에 맞게 넣고,

끝부터 탐색하면서 0이 아닌 수 중 N번째 값을 찾아볼까 했는데 (사실 애초에 말도 안되지만)

값 범위가 20억이길래 바로 포기

 

2. 한 줄씩 읽어오면서 정렬하는건 어떨까? 생각해봤으나

최악의 경우는 N번째로 큰 값이 첫번째 행에 있는건데, 그럼 sort하다가 터질 것 같아서 포기

 

 

풀이 방법

1. 일단 맨 끝줄에서 가장 큰 값을 찾는다 -> 여기서는 52(0열의 값)

 

2. 가장 큰 값을 찾고 나서는, 찾은 값의 위칸의 값(48)과 나머지 값들을 비교해서 그 다음으로 큰 값을 찾는다. ->49

3. 그 다음에는 파란색으로 칠한 곳에서 최대값을 찾는다.

 

4. 이 과정을 N번 반복한다.

 

 

쉬운 탐색을 위해 찾을 높이를 저장할 int형 배열을 만들었다.

 

팁

시간이 꽤 빠르게 나온 편이었는데(오늘 기준 6등)

더 줄여보고 싶어서

입력을 N-1행부터 거꾸로 받고, max값을 찾으면 배열 값을 --가 아니라 ++해줬다.

이렇게 하면 h배열의 초기값을 N-1로 줄 필요 없이, 그냥 0인 상태로 써도 된다.

시간 차이가 크지는 않은데(그래도 3등했다 ㅎㅎ),

이렇게 생각해 보는것도 좋을 것 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

private static int N, arr[][], h[];

public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;

N = Integer.parseInt(br.readLine());
arr = new int[N][N];
h = new int[N];

for (int i = N - 1; i >= 0; i--) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++)
arr[i][j] = Integer.parseInt(st.nextToken());
}
System.out.println(findMaxVal());
}

private static int findMaxVal() {
int max = 0, idx;

for (int step = 0; step < N; step++) {
max = arr[h[0]][0];
idx = 0;

for (int j = 0; j < N; j++) {
if (max < arr[h[j]][j]) {
max = arr[h[j]][j];
idx = j;
}
}
h[idx]++;
}
return max;
}
}

 

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	private static int N, arr[][], h[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		h = new int[N];
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++)
				arr[i][j] = Integer.parseInt(st.nextToken());
		}
		Arrays.fill(h, N - 1);
		
		System.out.println(findMaxVal());
	}

	private static int findMaxVal() {
		int max = 0, idx;
		
		for (int step = 0; step < N; step++) {
			max = arr[h[0]][0];
			idx = 0;
			
			for (int j = 0; j < N; j++) {
				if (max < arr[h[j]][j]) {
					max = arr[h[j]][j];
					idx = j;
				}
			}
			h[idx]--;
		}
		
		return max;
	}
}

 

재밌는 문제였다.

 

끝!