algospot.com :: 질문과 답변: MEETING 문제 Java풀이 질문있습니다.

MEETING 문제 Java풀이 질문있습니다.

import java.util.ArrayList;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        int T = 0;
        int N;
        int maxMen, maxWom;
        int result;

        Scanner tc = new Scanner(System.in);

        T = tc.nextInt();

        ArrayList<Integer> intMen = new ArrayList<Integer>();
        ArrayList<Integer> intWom = new ArrayList<Integer>();

        for(int j = 0; j < T; j++) {
            result = 0;

            N = tc.nextInt();

            intMen = inputInteger(intMen, N);
            intWom = inputInteger(intWom, N);

            quickSort(intMen, 0, intMen.size() - 1);
            quickSort(intWom, 0, intWom.size() - 1);

            for(int k = 0; k < N; k++) {
                result = result + Math.abs(intMen.get(k) - intWom.get(k));
            }

            System.out.println(result);
        }
    }

    public static void quickSort(ArrayList<Integer> a, int leftmost, int rightmost) {
        if(rightmost - leftmost <= 0) {
            return;
        }
        else {
            int pivot = a.get(rightmost);

            int i = leftmost - 1;
            int j = rightmost;

            while(true) {
                while(a.get(++i) < pivot);

                while(j > leftmost && a.get(--j) > pivot);

                if(i >= j)
                    break;
                else
                    swap(a, i, j);
            }
            swap(a, i, rightmost);

            quickSort(a, leftmost, i - 1);

            quickSort(a, leftmost + 1, rightmost);
        }
    }

    public static void swap(ArrayList<Integer> a, int i, int j) {
        int temp;
        temp = a.get(i);
        a.set(i, a.get(j));
        a.set(j, temp);
    }

    public static ArrayList<Integer> inputInteger(ArrayList<Integer> inputArr, int memNum) {
        Scanner tci = new Scanner(System.in);

        for(int k = 0; k < memNum; k++) {
            inputArr.add(tci.nextInt());
        }

        return inputArr;
    }
}

MEETING
제가 판단했을때 남자쪽 정수중에서 가장 큰 수와 여자쪽 정수중에서 가장 큰 정수를 빼나가는 방법으로 푸는것이 최소정수를 구하는 방법이라고 생각했습니다.
퀵정렬 사용해서 남자와 여자 ArrayList를 정렬하고 각각 index에서 뺀다음 더하였는데요. 시간초과가 나서 정답 확인이 불가하네요ㅜㅜ
더 좋은 방법이 있을까요?

8년 전

6개의 댓글이 있습니다.

이밝음

Scanner 말고 BufferedReader로 입력을 받아보세요

8년 전 link
식빵남아

답변 감사드립니다
한번 적용해볼게요 ^^

8년 전 link
식빵남아

적용해보았으나 시간초과 확인했습니다ㅜㅜㅜㅜㅜㅜ

8년 전 link
이밝음

보니까 정렬을 직접하신거 같으신데 Collections.sort를 이용하시면 더빨라지지 않나요?

8년 전 link
songmw725
저도 scanner 쓰면 시간 초과 나고 bufferedreader 쓰면 500ms 로 통과 했네요 이렇게 시간차이 많이 나는지 몰랐네요.
스캐너 쓴 코드랑 bufferedReader 쓴코드입니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;

public class MainMeeting {
static int[] men = new int[10000];
static int[] women = new int[10000];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int cases = Integer.valueOf(br.readLine());
for (int i = 0; i < cases; i++) {
int totalCount = Integer.valueOf(br.readLine());
String[] split = (br.readLine()).split(" ");
for (int j = 0; j < totalCount; j++) {
men[j] = Integer.valueOf(split[j]);
}
split = (br.readLine()).split(" ");
for (int j = 0; j < totalCount; j++) {
women[j] = Integer.valueOf(split[j]);
}
```
Arrays.sort(men, 0, totalCount);
        Arrays.sort(women, 0 , totalCount);

        int sum = 0;
        for (int j = 0; j < totalCount; j++) {
            sum += Math.abs(women[j] - men[j]);
        }
        System.out.println(sum);
    }
}
```
}

import java.util.Arrays;
import java.util.Scanner;

public class MainMeeting {
static int[] men = new int[10000];
static int[] women = new int[10000];
```
public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int cases = sc.nextInt();
    for (int i = 0; i < cases; i++) {
        int totalCount = sc.nextInt();

        for (int j = 0; j < totalCount; j++) {
            men[j] = sc.nextInt();
        }
        for (int j = 0; j < totalCount; j++) {
            women[j] = sc.nextInt();
        }

        Arrays.sort(men, 0, totalCount);
        Arrays.sort(women, 0 , totalCount);

        int sum = 0;
        for (int j = 0; j < totalCount; j++) {
            sum += Math.abs(women[j] - men[j]);
        }
        System.out.println(sum);
    }
}
```
}
8년 전 link
식빵남아

#이밝음
그러네요
제 정렬은 쓰레기였나 ㄷㄷㄷ
답변 감사드립니다 ^^

#songmw725
저도 bufferedreader썼는데 sorting 직접했더니 시간초과나네요
답변 감사드립니다 :)

8년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

SINCE 2007

다가오는 이벤트들

MEETING 문제 Java풀이 질문있습니다.

6개의 댓글이 있습니다.