삼성 SDS 대학생 알고리즘 특강 2일차 - 정렬

Compare 함수의 이해

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {

    public static void main(String[] args) {
        Item item1 = new Item(1,3,1);
        Item item2 = new Item(1,2,3);
        Item item3 = new Item(1,1,2);

        List<Item> list = new ArrayList<>();
        list.add(item1);
        list.add(item2);
        list.add(item3);

        System.out.println(list);
        Collections.sort(list);
        System.out.println(list);

    }
}

class  Item implements Comparable<Item> {
    int a;
    int b;
    int c;

    public Item(int a, int b, int c){
        this.a = a;
        this.b =b;
        this.c = c;
    }

    @Override
    public String toString() {
        return "{" +
                "a=" + a +
                ", b=" + b +
                ", c=" + c +
                '}';
    }

    @Override
    public int compareTo(Item o) {
        //음수 -> 원래 순서
        //0
        //양수 -> SWAP
        if(b < o.b){
            return -1;
        } else if(b==o.b){
            return 0;
        } else {
            return 1;
        }
        //return o.b - b;
        //내림차순시 b - o.b;
    }
}


//실행 결과
// [{a=1, b=3, c=1}, {a=1, b=2, c=3}, {a=1, b=1, c=2}]
// [{a=1, b=1, c=2}, {a=1, b=2, c=3}, {a=1, b=3, c=1}]

but 순서가 헷갈릴 수 있다.

따라서 아래의 compare을 쓰면 수월.

//기본은 오름차순
return Integer.compare(o.b, b);

//내림차순
return Integer.compare(b, o.b);

 

 

Comparator 사용시 기존의 compareTo 덮어씌움.

 Comparator<Item> comp = new Comparator<Item>() {
            @Override
            public int compare(Item o1, Item o2) {
                return o1.c - o2.c;
            }
        };

        Collections.sort(list, comp);
        System.out.println(list);

 

getter 추가 후 Comparator.comparingInt(o::get~) 형식으로 해도 정렬 가능.

Collections.sort(list, Comparator.comparingInt(Item::getB));
System.out.println(list);


class  Item implements Comparable<Item> {
    int a;
    int b;
    int c;

    public int getA() {
        return a;
    }

    public int getB() {
        return b;
    }

    public int getC() {
        return c;
    }

    public Item(int a, int b, int c){
        this.a = a;
        this.b =b;
        this.c = c;
    }

    @Override
    public String toString() {
        return "{" +
                "a=" + a +
                ", b=" + b +
                ", c=" + c +
                '}';
    }
}

 

그러면 Comparable과 Comparator의 역할은 비슷한 것 같은데 무슨 차이인 것일까?

왜 Comparable의 compareTo(T o) 메소드는 파라미터(매개변수)가 한 개이고, Comparator의 compare(T o1, T o2) 메소드는 파라미터가 왜 두 개인 것일까?

 

일단, 두 인터페이스를 구체적으로 알아보기에 앞서 먼저 정답부터 말하자면, Comparable은 "자기 자신과 매개변수 객체를 비교"하는 것이고, Comparator는 "두 매개변수 객체를 비교"한다는 것이다.

 

쉽게 말하자면, Comparable은 자기 자신과 파라미터로 들어오는 객체를 비교하는 것이고, Comparator는 자기 자신의 상태가 어떻던 상관없이 파라미터로 들어오는 두 객체를 비교하는 것이다. 즉, 본질적으로 비교한다는 것 자체는 같지만, 비교 대상이 다르다는 것이다.

 

 

 

1713: 후보 추천하기

import java.util.*;

public class Main {
    static class Student implements Comparable<Student> {
        int num;
        int time;
        int like;
        boolean isIn;  //사진틀에 이 사람이 있는지 없는지 확인

        public Student(int num, int like, int time, boolean isIn){
            this.time = time;
            this.like = like;
            this.num = num;
            this.isIn = isIn;
        }

        public int compareTo(Student s){
            //1. 추천수, 2. 시간
            int comp = Integer.compare(like, s.like);
            if(comp == 0){
                return Integer.compare(time, s.time);
            } else
                return comp;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Student[] students = new Student[101];

        int n = sc.nextInt();
        int allLike = sc.nextInt();

        //1.학생들이 추천을 시작하기 전에 모든 사진틀은 비어있다.
        ArrayList<Student> picture = new ArrayList<>();

        //2.어떤 학생이 특정 학생을 추천하면, 추천받은 학생의 사진이 반드시 사진틀에 게시되어야 한다.
        for(int i=0; i<allLike; i++){
            int num = sc.nextInt();
            //해당 후보가 최초 호출 시
            if(students[num] ==null){
                students[num] = new Student(num, 0, 0, false);
            }
            //해당 후보가 사진틀에 있을 경우
            if(students[num].isIn == true){
                students[num].like++;
            }
            //해당 후보가 사진 틀에 없음
            else {
                //사진들이 가득 찬 경우
                if(picture.size() == n){
                    //정렬, 지울 후보 선정, 제거
                    Collections.sort(picture);
                    picture.get(0).isIn = false;
                    picture.remove(0);
                }
                //사진틀에 여유가 있는 경우
                //students[num].num = num;
                students[num].like = 1;
                students[num].isIn = true;
                students[num].time = i;
                picture.add(students[num]);
            }
        }
        Collections.sort(picture, new Comparator<Student>() {
            public int compare(Student s1, Student s2){
                return Integer.compare(s1.num, s2.num);
            }
        });
        for(int i=0; i<picture.size(); i++){
            System.out.print(picture.get(i).num+" ");
        }
    }
}

 

 

2003: 수들의 합 2

슬라이딩 윈도우 - 연속된 수들의 합 구할 때.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] nums = new int[N+1];

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

        int low = 0, high = 0, sum = nums[0], count = 0;
      while (true){
          // sum == M -> 답 low++
          if(sum==M){
              count++;
              sum -= nums[low++];
          }
          // sum > M -> low++
          else if (sum > M){
              sum -= nums[low++];
          }
          // sum < M -> high++
          else {
              sum += nums[++high];
          }
          if(high == N){
              break;
          }
      }
      System.out.println(count);
    }
}

 

 

1806: 부분합

슬라이딩 윈도우

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] nums = new int[N+1];

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

        int low = 0, high = 0, sum = nums[0], min = Integer.MAX_VALUE;
        while (true){
            // sum >= M -> 답 low++
            if(sum>=M){
                min = Math.min(high-low+1,min);
                sum -= nums[low++];
            }
            else {
                sum += nums[++high];
            }
            if(high == N){
                break;
            }
        }
        if(min == Integer.MAX_VALUE){
            System.out.println(0);
        } else{
            System.out.println(min);
        }
    }
}

 

 

2805: 나무 자르기

투 포인터

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] trees = new int[N];

        long max = 0;
        st = new StringTokenizer(br.readLine());

        for(int i=0; i<N; i++){
            trees[i] = Integer.parseInt(st.nextToken());
            max = Math.max(trees[i],max);
        }

        long s = 0;
        long e=max;
        long mid=0;
        long result = 0;

        while(true){
            long sum = 0;
            mid = (s+e) /2;
            for(int i=0; i<trees.length; i++){
                if(trees[i]>mid){
                    sum+=trees[i] - mid;
                }
            }
            //sum == M -> 정답, 탈출
            if(sum == M){
                result = mid;
                break;
            }
            //sum < M -> mid -> end
            else if(sum<M){
                e = mid-1;
            }
            //sum > M -> mid -> s, 정답 후보
            else {
                result = mid;
                s = mid+1;
            }
            //시작점이 끝점보다 커지면
            if(s>e){
                break;
            }
        }
        System.out.println(result);
    }
}

 

 

2143: 두 배열의 합

투 포인터 (subA, subB 만들어서)

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

//1. SubA, SubB
//2. 정렬
//3. 2Pointer
public class Main {
    static long T;
    static int N, M;
    static long[] inputA, inputB;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
         T = Long.parseLong(st.nextToken());

         N = Integer.parseInt(br.readLine());
         inputA = new long[N];
         st = new StringTokenizer(br.readLine());
         for(int i=0; i<N; i++){
             inputA[i] = Long.parseLong(st.nextToken());
         }

         M = Integer.parseInt(br.readLine());
         inputB = new long[M];
         st = new StringTokenizer(br.readLine());
         for(int i=0; i<M;i++){
             inputB[i] = Long.parseLong(st.nextToken());
         }

         List<Long> subA = new ArrayList<>();
         List<Long> subB = new ArrayList<>();

         //subA 구하기
        for(int i=0; i<N; i++){
            long sum = inputA[i];
            subA.add(sum);
            for(int j= i+1; j<N; j++){
                sum += inputA[j];
                subA.add(sum);
            }
        }

        //subB 구하기
        for(int i=0; i<M; i++){
            long sum = inputB[i];
            subB.add(sum);
            for(int j= i+1; j<M; j++){
                sum += inputB[j];
                subB.add(sum);
            }
        }

        //subA, subB 정렬하기
        Collections.sort(subA);
        Collections.sort(subB, Comparator.reverseOrder());

        long result = 0;
        int ptA = 0;
        int ptB = 0;
        while(true){
            long currentA = subA.get(ptA);
            long target = T - currentA;
            //currentB == target -> subA, subB 같은 수 개수 체크 -> 답구하기.
            if(subB.get(ptB) == target){
                long countA = 0;
                long countB = 0;
                while(ptA < subA.size() && subA.get(ptA) == currentA){
                    countA++;
                    ptA++;
                }
                while(ptB < subB.size() && subB.get(ptB) == target){
                    countB++;
                    ptB++;
                }
                result += countA * countB;
            }
            //currentB > target -> ptB++
            else if(subB.get(ptB)>target){
                ptB++;
            }
            //currentB < target -> ptA++
            else {
                ptA++;
            }
            //탈출 조건
            if(ptA == subA.size() || ptB == subB.size()){
                break;
            }
        }
        System.out.println(result);
    }
}

 

 

1072: 게임

파라메트릭 서치

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

public class Main {
    static long X, Y;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
         X = Long.parseLong(st.nextToken());
         Y = Long.parseLong(st.nextToken());
         long Z = Y*100 / X;

         if(Z >= 99){
             System.out.println(-1);
         } else {
             long start = 0;
             //X를 최대값으로 넣어도 됨. 다만 X로 하면 효율화 최대.
             long end = X;
             while(start < end){
                 long mid = (start + end) / 2;
                 long newRate = (100 * (mid + Y) / (mid + X));
                 //승률이 그대로 인 경우
                 if(newRate == Z){
                     start = mid + 1;
                 }
                 //승률이 변한 경우
                 else {
                     end = mid;
                 }
             }
             System.out.println(end);
         }
    }
}