글 읽기 - 정렬~!

fdjk2000 5년 전 0

자바언어로 문제를 풀고 잇습니다.

시간초과가 나서 질문들을 봣는데 정렬을 하라는 풀이가 잇어 버블로 정렬을 했는데도 시간초과가 나네요 혹시 정렬을 합병정렬로 해야하는건가요??

주석처리한건 정렬하기전에 푼거고 주석처리안된건 정렬을 하고 풀엇습니다...시간초과나서 당황스럽네용;;

package Olympiad;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class ele_2015_colorball {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int num = Integer.parseInt(br.readLine());

		int[][] n = new int[num][3];
		int[] result = new int[num];
		for (int i = 0; i < num; i++) {
			String[] str = br.readLine().split(" ");
			for (int j = 0; j < 2; j++) {
				n[i][j] = Integer.parseInt(str[j]);
			}
			n[i][2] = i;
		}
		// for(int i=0;i<num;i++) {
		// for(int j=0;j<num;j++) {
		// if(i==j) continue;
		// if(n[i][0]!=n[j][0]&&n[i][1]>n[j][1]) result[i]+=n[j][1];
		// }
		// }
		// for(int s:result) System.out.println(s);
		for (int i = 0; i < num - 1; i++) {
			for (int j = 0; j < num - 1 - i; j++) {
				if (n[j][1] > n[j + 1][1]) {
					int temp1 = n[j][0];
					int temp2 = n[j][1];
					int temp3 = n[j][2];
					n[j][0] = n[j + 1][0];
					n[j][1] = n[j + 1][1];
					n[j][2] = n[j + 1][2];
					n[j + 1][0] = temp1;
					n[j + 1][1] = temp2;
					n[j + 1][2] = temp3;
				}
			}
		}

		for(int i=num-1;i>=0;i--) {
			for(int j=i-1;j>=0;j--) {
				if(n[i][0]!=n[j][0]&&n[i][1]>n[j][1]) result[n[i][2]]+=n[j][1];
			}
		}
		for(int i:result) System.out.println(i);

	}

}

sky1357 5년 전 0

버블정렬은 시간복잡도가 O(n^2)이라 시간초과나요.

그래서 합병정렬같은 O(nlogn) 알고리즘이 필요한데, 일일이 구현하는건 힘드므로..

자바에 있는 Arrays.sort() 메소드를 이용하면 될 것 같아요.

(Arrays.sort() 메소드는 퀵정렬로 시간복잡도가 평균 O(nlogn)이에요.)

fdjk2000 5년 전 0

이차원배열은 Arrays.sort가안되지안나요??

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

문제

문제

출처

ICPC

정렬~!

fdjk2000 5년 전 0

sky1357 5년 전 0

fdjk2000 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말