백준길라잡이(1-3) 탐색과 정렬 문제풀이

탐색과 정렬 문제풀이(2) 

아래 문제들은 java기준 Comparator 클래스를 implements 하는 클래스를 정의하고 compare 메서드를 @Override 하여 원하는 조건으로 정렬 할 수 있게 하는게 관건인 문제들이다.

이외의 공부할 사항은 없어보이는 쉬운 정렬 문제들이다.

 

 

A – 1026 보물 https://www.acmicpc.net/problem/1026

package baekjoon.part01_03;

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

import static java.util.Comparator.reverseOrder;

// 백준길라잡이 part01_03 탐색과 정렬 : 1026 보물
public class Num1026_보물 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] a = new int[n];
        Integer[] b = new Integer[n];
        for(int i=0; i<n; i++){
            a[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            b[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(a);
        Arrays.sort(b, (o1,o2)->o2-o1);

        int answer = 0;
        for(int i=0; i<n; i++){
            answer += a[i]*b[i];
        }

        System.out.println(answer);

    }

}

 

 

B – 1181 단어 정렬 https://www.acmicpc.net/problem/1181

package baekjoon.part01_03;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

// 백준길라잡이 1-3 탐색과 정렬 : 단어 정렬
public class Num1181_단어정렬 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Set<String> set = new HashSet<>();
        for(int i=0; i<n; i++){
            set.add(br.readLine());
        }

        String[] arr = set.toArray(new String[set.size()]);
        Arrays.sort(arr, new myComparator());

        for(int i=0; i<arr.length; i++){
            System.out.println(arr[i]);
        }

    }

}

class myComparator implements Comparator<String>{
    @Override
    public int compare(String s1, String s2){
        int temp = 0;

        if(s1.length() == s2.length()){
            for(int i=0; i<s1.length(); i++){
                if(s1.charAt(i) != s2.charAt(i)){
                    temp =  (int)s1.charAt(i) - (int)s2.charAt(i);
                    break;
                }
            }
        }else{
            temp =  s1.length()  - s2.length();
        }
        return temp;
    }
}

 

 

 

C – 11650 좌표 정렬하기 https://www.acmicpc.net/problem/11650

package baekjoon.part01_03;

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

public class Num11650_좌표정렬하기 {

    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][2];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }


        Arrays.sort(arr, new coordinateComparator());

        for(int i=0; i<n; i++){
            System.out.println(arr[i][0] + " " + arr[i][1]);
        }

    }

}
class coordinateComparator implements Comparator<int[]> {

    @Override
    public int compare(int[] o1, int[] o2){
        if(o1[0] != o2[0]){
            return o1[0] - o2[0];
        }else{
            return o1[1] - o2[1];
        }
    }

}

 

 

 

C* - 11651 좌표 정렬하기 2 https://www.acmicpc.net/problem/11651

package baekjoon.part01_03;

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

public class Num11651_좌표정렬하기2 {

    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][2];

        for(int i = 0; i < n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr, new coordinate2Comparator());
        for(int i=0; i<n; i++){
            System.out.println(arr[i][0] + " " + arr[i][1]);
        }

    }
}
class coordinate2Comparator implements Comparator<int[]>{

    @Override
    public int compare(int[] o1, int[] o2){
        if(o1[1] != o2[1]){
            return o1[1] - o2[1];
        }else{
            return o1[0] - o2[0];
        }
    }

}

 

 

 

 

D – 10867 중복 빼고 정렬하기 https://www.acmicpc.net/problem/10867

package baekjoon.part01_03;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.StringTokenizer;

public class Num10867_중복빼고정렬하기 {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        Set<Integer> set = new HashSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++){
            set.add(Integer.parseInt(st.nextToken(" ")));
        }

        Integer[] arr = set.toArray(new Integer[set.size()]);
        Arrays.sort(arr);
        for(int i=0; i<arr.length; i++){
            System.out.print(arr[i] + " ");
        }

    }

}