글 읽기 - 테스트 케이스는 다 맞는데, 틀렸습니다 라고 뜨는데 왜 틀린건깔요?

csm0626 4년 전 0

안녕하세요?

해당 버블소트 문제가 n제곱이면 시간초과나고

merge sort를 써서 풀어야 한다는 사실을 알아서

mergesort를 직접 작성해서

제풀했는데 틀렸습니다라고 뜨더라구요.

이해가 안가는건,

testCase들은 전부 맞았던거 같은데, 10이하 100이하로 돌렸을때 buble sort랑 같으면

그 이후 같도 같을거다란 논리로요.

근데 틀렸습니다라고 나오더라구요?

메모리나, 시간초과도 아니고 틀렸다라는데, 예외케이스가 무엇일지

왜 틀린건지 질문드립니다.

import java.util.Scanner;

public class Main{

	private static int count = 0;
	public static void main(String[] args){
		
		Scanner sc = new Scanner(System.in);
		int n = Integer.valueOf(sc.nextLine());
		int[] arrayData = new int[n];
		int[] sortData = new int[n];
		int i = 0;
		for(String data:sc.nextLine().split(" ")){
			arrayData[i++] = Integer.valueOf(data);
		}
		mergeSort(0,arrayData.length-1,arrayData,sortData);
		System.out.println(count);
	}
	
	private static void mergeSort(int start, int end, int[] data, int[] sortData){
		
		if(start==end)
			return;
		int mid = (start + end) /2;
		mergeSort(start,mid,data,sortData);
		mergeSort(mid+1,end,data,sortData);
		merge(start,end,data,sortData);
	}
	
	private static void merge(int start,int end,int[] data,int[] sortData){
		
		int mid = (start+end)/2;
		int i = start; 
		int j = mid+1;
		int k = start;
		while(i<=mid && j<=end){
			if(data[i]>data[j]){
				count += Math.abs(k-j);
				sortData[k++] = data[j++];
			}else{
				sortData[k++] = data[i++];
			}
		}
		//여기 는 둘중에 하나만 남는애들
		while(i<=mid){
			sortData[k++] = data[i++];
		}
		while(j<=end){
			sortData[k++] = data[j++];
		}
		/**
		 * 정렬된 sortData를 담은 순서에 data에 담지 않으면, 다음번 merge가 일어날때
		 * 정렬되지 않는다.
		 */
		for(int m=start; m<=end; m++){
			data[m] = sortData[m];
		}
	}
}

onjo0127 4년 전 0

64비트 정수형을 사용하지 않으면 오버플로우가 일어납니다!

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

문제

문제

출처

ICPC

테스트 케이스는 다 맞는데, 틀렸습니다 라고 뜨는데 왜 틀린건깔요?

csm0626 4년 전 0

onjo0127 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말