글 읽기 - 1517번 버블 정렬 swap 횟수 구하기 질문입니다.

huseong2 6년 전 0

버블정렬로 풀었다가 시간 초과가 나와서 병합 정렬로 풀었는데

제가 돌려본 테스트 프로그램에서는 모두 swap 횟수가 같다고 나오는데

왜 9%에서 틀리다고 나올까요

using System;

namespace _1517
{
    class Program
    {
        static int answer = 0;
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            string[] input = Console.ReadLine().Split(' ');
            int[] inputs = new int[n];
            for(int i=0; i<n; i++) {
                inputs[i] = int.Parse(input[i]);
            }
            mergeSort(inputs);
            Console.WriteLine(answer);
        }

        static int[] copyArray(int[] arr, int startIndex, int size) {
            int[] array = new int[size];
            for(int i=0; i<size; i++) {
                array[i] = arr[startIndex + i];
            }
            return array;
        }

        static int[] merge(int[] arr1, int[] arr2) {
            int i = 0;
            int j = 0;
            int[] returnArray = new int[arr1.Length + arr2.Length];
            int count = 0;
            while(true) {
                if (arr2.Length == j) {
                    for (; i < arr1.Length; i++) {
                        returnArray[count++] = arr1[i];
                    }
                    break;
                }
                if (arr1.Length == i) {
                    for (; j<arr2.Length; j++) {
                        returnArray[count++] = arr2[j];
                    }
                    break;
                }
                if (arr1[i] <= arr2[j]) {
                    returnArray[count++] = arr1[i++];
                } else { 
                    answer += arr1.Length - i;
                    returnArray[count++] = arr2[j++];
                }
            }
            return returnArray;
        }

        static int[] mergeSort(int[] arr) {
            if(arr.Length > 1) {
                int mid = arr.Length/2;
                return merge(mergeSort(copyArray(arr, 0, mid)), mergeSort(copyArray(arr, mid, arr.Length-mid)));
            }
            return arr;
        }
    }
}

jwvg0425 6년 전 0

답이 32비트 정수형 범위를 넘어가서 그래요~ 저도 9%에서 틀렸는데 그거 수정하니까 통과됐습니당

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

문제

문제

출처

ICPC

1517번 버블 정렬 swap 횟수 구하기 질문입니다.

huseong2 6년 전 0

jwvg0425 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말