[JAVA] 알고리즘 문제풀이 입문 6-7, 6-8

강의: https://inf.run/w779

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의

 

6-7번

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

class Point implements Comparable<Point>{
  public int x, y;
  Point(int x, int y){
    this.x = x;
    this.y = y;
  }

  @Override
  public int compareTo(Point o) {
    if(this.x == o.x){
      return this.y - o.y;
    }else return this.x - o.x;
  }  
}

public class Main {
  public static void main(String[] args){
    //Main t = new Main();
    Scanner in = new Scanner(System.in);
    ArrayList<Point> arr = new ArrayList<>();

    int n = in.nextInt();
    for(int i = 0; i < n; i++){
      int x = in.nextInt();
      int y = in.nextInt();
      arr.add(new Point(x, y));
    }
    in.close();
    Collections.sort(arr);

    for(Point o : arr) System.out.println(o.x+" "+o.y);
  }
}

 

 

6-8번

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

class Main{
  public int solution(int n, int m, int[] arr){
    int lt = 0;
    int rt = n;
    int middle = n/2;
    while(true){
      if(arr[middle] == m){
        return middle +1;
      }else if(arr[middle] > m){
        rt = middle;
        middle = (lt+rt)/2;
      }else{
        lt = middle;
        middle = (lt+rt)/2;
      }
    }
  }
  public static void main(String[] args){
    Main T = new Main();
    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int m = in.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n; i++){
      arr[i] = in.nextInt();
    }
    in.close();

    Arrays.sort(arr);

    System.out.print(T.solution(n, m, arr));
  }
}

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

class Main{
  public int solution(int n, int m, int[] arr){
    int lt = 0;
    int rt = n-1;
    int answer = 0;
    while(lt<=rt){
      int mid = (lt+rt)/2;
      if(arr[mid] == m){
        answer = mid + 1;
        break;
      }else if(arr[mid] > m) rt = mid-1;
      else lt = mid;
    }
      return answer;
    }
  }

  public static void main(String[] args){
    Main T = new Main();
    Scanner in = new Scanner(System.in);

    int n = in.nextInt();
    int m = in.nextInt();
    int[] arr = new int[n];
    for(int i = 0; i < n; i++){
      arr[i] = in.nextInt();
    }
    in.close();

    Arrays.sort(arr);

    System.out.print(T.solution(n, m, arr));
  }
}