[백준] 정렬(1026, 1946, 18870, 1181)

자동목차

보물(1026)

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

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

        int[] a = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        Integer[] b = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).boxed().toArray(Integer[]::new);

                // 가장 큰 숫자와 가장 작은 숫자를 곱하는 것으로 값을 최소화 시키기 위해 각각 오름차순, 내림차순으로 정렬
        Arrays.sort(a);
        Arrays.sort(b, Collections.reverseOrder());

        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i] * b[i];
        }
        System.out.println(sum);
    }
}

메모리	시간
14612	108

신입사원(1946)

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        int n, res, min;
        List<Person> list;
        StringBuilder sb = new StringBuilder();

        while (t-- > 0) {
            n = Integer.parseInt(br.readLine());
            list = new ArrayList<>();
            res = 1; // 서류점수가 1위인 사람은 무조건 합격이므로 1로 지정
            min = 0;

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                list.add(new Person(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
            }
            list.sort(Comparator.comparingInt(p -> p.documentScore)); // 서류 점수 기준으로 오름차순 정렬

            min = list.get(0).interviewScore; // 서류 점수가 가장 높은사람의 인터뷰 점수로 설정하여 비교시작함

            for (int i = 1; i < list.size(); i++) {
                if (list.get(i).interviewScore < min) { // 그 다음으로 서류점수 순위가 높은사람의 인터뷰 스코어가 앞 순위 사람보다 순위가 높다면, 하나라도 더 높은 것이기에 res 증가하고 min 갱신
                    res++;
                    min = list.get(i).interviewScore;
                }
            }
            sb.append(res).append("\n");
        }
        System.out.println(sb);
    }

    static class Person {
        int documentScore;
        int interviewScore;

        public Person(int documentScore, int interviewScore) {
            this.documentScore = documentScore;
            this.interviewScore = interviewScore;
        }
    }
}

메모리	시간
300372	1556

좌표 압축(18870)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.security.spec.RSAOtherPrimeInfo;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n]; // 원본 배열
        int[] sorted = new int[n]; // 정렬된 배열
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0 ; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sorted[i] = arr[i];
        }

        // 배열 오름차순으로 정렬하고 중복제거
        int[] unique = Arrays.stream(sorted).sorted().distinct().toArray();
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            int idx = Arrays.binarySearch(unique, arr[i]); // 원본배열의 첫번째부터 해당 값을 유니크배열에서 이분탐색하여 인덱스를 찾음
            sb.append(idx + " ");
        }
        System.out.println(sb);
    }
}

메모리	시간
210016	1636

단어 정렬(1181)

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

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

        for (int i = 0; i < n; i++) arr[i] = br.readLine();

        Arrays.sort(arr, (o1, o2) -> {
            // 문자열 길이가 같은경우 사전순 으로 정렬
            if (o1.length() == o2.length()) return o1.compareTo(o2);
            // 문자열 길이수 오름차순 정렬
            return o1.length() - o2.length();
        });
        StringBuilder sb = new StringBuilder();
        sb.append(arr[0]).append("\n");

        for (int i = 1; i < n; i++) {
            if (!arr[i].equals(arr[i-1])) { // 동일한 문자열은 출력하지 않음
                sb.append(arr[i]).append("\n");
            }
        }

        System.out.println(sb);
    }
}

메모리	시간
26308	292