글 읽기 - 제가 아는 모든 방법으로 풀어 봤는데 안되서 올립니다..

tjdwlsdl 8년 전 0

이것 저것 찾아서 해봤는데 안되내요....

다른분들이 성공한거 보면 java로 성공한건 없던데....

java로는 이 문제 못푸는건가요?......

푸는 방법있으면 방법좀 알려주세요...

저는 전부 시간초과 나오내요 ......

힌트라도...,.,.,.,......

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		StringTokenizer token = new StringTokenizer(str, " ");
		List<Integer> list = new ArrayList<Integer>(5000000);

		token.nextToken();
		int num = Integer.parseInt(token.nextToken());

		str = sc.nextLine();
		token = new StringTokenizer(str, " ");
		while(token.hasMoreTokens()) {
			list.add(Integer.parseInt(token.nextToken()));
		}
		list = mergeSort(list);
		System.out.println(list.get(num - 1));
	}
	
	public static List<Integer> mergeSort(List<Integer> values){
		if(values.size() < 2){
			return values;
		}
		
		List<Integer> leftHalf = values.subList(0, values.size() / 2);
		List<Integer> rightHalf = values.subList(values.size() / 2, values.size());
		
		return merge(mergeSort(leftHalf), mergeSort(rightHalf));
	}
	
	public static List<Integer> merge(List<Integer> left, List<Integer> right){
		int leftPtr = 0;
		int rightPtr = 0;
		
		List<Integer> merged = new ArrayList<>(left.size() + right.size());
		
		while(leftPtr < left.size() && rightPtr < right.size()){
			if(left.get(leftPtr) < right.get(rightPtr)){
				merged.add(left.get(leftPtr));
				leftPtr++;
			} else {
				merged.add(right.get(rightPtr));
				rightPtr++;
			}
		}
		
		while(leftPtr < left.size()){
			merged.add(left.get(leftPtr));
			leftPtr++;
		}
		
		while(rightPtr < right.size()){
			merged.add(right.get(rightPtr));
			rightPtr++;
		}
		
		return merged;
	}
}

algoshipda 8년 전 1

https://en.wikipedia.org/wiki/Quickselect 이걸 기반으로 하는데 pivot 잡는걸 https://en.wikipedia.org/wiki/Median_of_medians 로 해보세요

tjdwlsdl 7년 전 0

알려주신 사이트가 영어범벅이라 포기했다가......

요번에 하루 잡고 알려주신 내용을 토대로 열쒸미 검색해서 풀었습니다.........

캄사합니다 ㅠ.ㅠ

그리고 답변 늦어서 죄송합니다.. @ㅅ@.....

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

제가 아는 모든 방법으로 풀어 봤는데 안되서 올립니다..

tjdwlsdl 8년 전 0

algoshipda 8년 전 1

tjdwlsdl 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말