글 읽기 - JAVA로 시간초과가 나는데 어떤 부분을 수정해야 할까요..?

realsorin 4년 전 0

제출하면 바로 시간초과가 떠버리는데 어디에서 유독 시간을 잡아먹고 있는건지 잘 모르겠네요..

어느 부분을 개선하면 좋을지요ㅜㅜ

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	static int n, tn;
	static P[] p;
	static int[] segTree;
	
	public static void main(String[] args) throws IOException {
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.valueOf(st.nextToken());//테스트 케이스
		for(int t=1; t<=T; t++){
			st = new StringTokenizer(br.readLine());
			n = Integer.valueOf(st.nextToken());
			p = new P[n];
			int x, y;
			//N개의 섬 좌표 정보 입력
			for(int i=0; i<n; i++){
				st = new StringTokenizer(br.readLine());
				x = Integer.valueOf(st.nextToken());
				y = Integer.valueOf(st.nextToken());
				p[i] = new P(x, y);
			}
			//y좌표 오름차순으로 정렬
			Arrays.sort(p, new Comparator<P>() {
				@Override
				public int compare(P o1, P o2) {
					return o1.y - o2.y;
				}
			});
			
			//좌표압축(입력 개수에 비해 좌표 범위가 크기 때문에 y좌표값을 순위로 갈음)
			int rank = 1;
			p[0].r = rank;
			for(int i=1; i<n; i++){
				if(p[i-1].y != p[i].y) rank++;
				p[i].r = rank;
			}
			
			//리프 노드 하나가 y좌표 하나를 표현하게 됨
			tn = 1;
			while(tn < rank){
				tn = tn << 1;
			}
			segTree = new int[tn*2];
			
			Arrays.sort(p);//x좌표 오름차순, y좌표 내림차순(rank로 대체)
			
			long ans = 0;
			for(int i=0; i<n; i++){
				ans += search(p[i].r, rank);//내 앞에 있는 섬들중 y좌표값이 내 y좌표값과 같거나 큰 것들
				update(p[i].r, 1);
			}
			bw.write(ans+"");;
			bw.flush();
		}
	}
	
	private static void update(int pos, int val){
		pos = pos + tn - 1;
		while(pos > 0){
			segTree[pos] += 1;
			pos /= 2;
		}
	}
	
	private static long search(int s, int e){
		long ans = 0;
		s = s + tn - 1;
		e = e + tn - 1;
		while(s<=e){
			if(s%2==1) ans += segTree[s++];
			if(e%2==0) ans += segTree[e--];
			s /= 2;
			e /= 2;
		}
		return ans;
	}
	
	private static class P implements Comparable<P>{
		int x, y, r;
		public P (int x, int y){
			this.x = x;
			this.y = y;
		}
		@Override
		public int compareTo(P o) {
			if(x == o.x){
				return o.r - r;
			}else{
				return x - o.x;
			}
		}
	}

}

chogahui05 4년 전 3

(1) Arrays.sort

그런데 이건 그냥 Object를 정렬하는 것이니. 잠시만요. 함 봐볼게요.

호출 경로를 쭉 따라들어가니, Timsort나 MergeSort를 호출하네요.

이 둘은 상당히 빠른 정렬입니다. 그런데 여기에서는 어떤 식으로 호출하는지는 모르겠군요.

만약에 이게 아니라면 다른 문제인데..

(2) bw.flush() 함수를 테케마다 호출하시지 마시고

한꺼번에 해 보세요. 그러니까, 테케 다 끝나고 마지막에 bw.flush()를 한 번만 호출해 보세요.

(3) 그런데 (2)를 적용했는데도 시간 초과라면

(1)이 문제겠지요..?

그러면 Array.sort를 Collections.sort로 바꿔봅시다.

이는 point를 Array가 아닌, ArrayList를 써서 관리해 주시면 됩니다.

realsorin 4년 전 0

감사합니다ㅜㅜ!

안 그래도 지금 계속 풀고 있었는데 말씀하신 대로 ArrayList로 바꾸니 시간 초과는 해결이 되었구요.

그런데 그거 말고도 짜잘하게 잘못 짠 부분들이 있어서 고쳐서 아래 소스로 통과했습니다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	static int n, tn;
	static ArrayList<P> p = new ArrayList<P>();
	static int[] segTree;
	
	public static void main(String[] args) throws IOException {
		
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int T = Integer.valueOf(st.nextToken());//테스트 케이스
		for(int t=1; t<=T; t++){
			p.clear();
			st = new StringTokenizer(br.readLine());
			n = Integer.valueOf(st.nextToken());
			int x, y;
			//N개의 섬 좌표 정보 입력
			for(int i=0; i<n; i++){
				st = new StringTokenizer(br.readLine());
				x = Integer.valueOf(st.nextToken());
				y = Integer.valueOf(st.nextToken());
				p.add(new P(x, y));
			}
			//y좌표 오름차순으로 정렬
			Collections.sort(p, new Comparator<P>() {
				@Override
				public int compare(P o1, P o2) {
					return o1.y - o2.y;
				}
			});
			
			//좌표압축(입력 개수에 비해 좌표 범위가 크기 때문에 y좌표값을 순위로 갈음)
			int rank = 1;
			p.get(0).r = rank;
			for(int i=1; i<n; i++){
				if(p.get(i-1).y != p.get(i).y) rank++;
				p.get(i).r = rank;
			}
			
			//리프 노드 하나가 y좌표 하나를 표현하게 됨
			tn = 1;
			while(tn < rank){
				tn = tn << 1;
			}
			segTree = new int[tn*2];
			
			Collections.sort(p);//x좌표 오름차순, y좌표 내림차순(rank로 대체)
			
			long ans = 0;
			for(int i=0; i<n; i++){
				ans += search(p.get(i).r, rank);//내 앞에 있는 섬들중 y좌표값이 내 y좌표값과 같거나 큰 것들
				update(p.get(i).r, 1);
			}
			bw.write(ans+"\n");;
			bw.flush();
		}
	}
	
	private static void update(int pos, int val){
		pos = pos + tn - 1;
		while(pos > 0){
			segTree[pos] += 1;
			pos /= 2;
		}
	}
	
	private static long search(int s, int e){
		long ans = 0;
		s = s + tn - 1;
		e = e + tn - 1;
		while(s<=e){
			if(s%2==1) ans += segTree[s++];
			if(e%2==0) ans += segTree[e--];
			s /= 2;
			e /= 2;
		}
		return ans;
	}
	
	private static class P implements Comparable<P>{
		int x, y, r;
		public P (int x, int y){
			this.x = x;
			this.y = y;
		}
		@Override
		public int compareTo(P o) {
			if(x == o.x){
				return o.r - r;
			}else{
				return x - o.x;
			}
		}
	}

}

keunbum 4년 전 0

@chogahui05

저.. 지나가던 사람입니다만

잘 이해가 안되는게 왜 Collections.sort가 Arrays.sort 보다 빠른 건가요?

둘다 어차피 내부적으로는 팀소트나 머지소트를 똑같이 쓰는 것 아닌가요?

----------------------------------------------------------------------------------------------

검색해보니

https://www.acmicpc.net/blog/view/58

데이터의 특성에 따라 실행 속도 우위가 달라질 수 있네요..

(어떤 이유에선지 모르겠지만 그 차이를 인정한다면)

그러면 문제 데이터의 특성을 파악해서 적절한 정렬 메서드를 호출하는 것도

코더의 몫인 건가요?

chogahui05 4년 전 0

primitive type으로 배열을 선언하시고

Arrays.sort를 호출해 보세요. F5를 누르시면서 디버깅 해 보시면 아실 수 있을 듯 싶습니다.

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

문제

문제

출처

ICPC

JAVA로 시간초과가 나는데 어떤 부분을 수정해야 할까요..?

realsorin 4년 전 0

chogahui05 4년 전 3

realsorin 4년 전 0

keunbum 4년 전 0

chogahui05 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말