2022 02 06

2022-02-05

알고리즘 문제풀이 - Sorting and Searching

• LinkedList remove() 주의사항

  LinkedList<Integer> cache = new LinkedList<>();
  cache.addFirst(3);
  
  // 해당 경우 예외 발생 -> Primitive Type은 index로 고려함
  int element = 3;
  cache.remove(element);
  
  // 원소를 삭제하고 싶다면 Reference Type으로 만들어 줄 것!
  Integer element = 3;
  cache.remove(element);
  

• 정렬을 했을 때 쉽게 풀리는 문제들이 있음
  • 원래 정렬되었는데 두개의 원소가 자리를 바꿨음
  • 그냥 정렬다시시켜서 비교하는 방식을 생각해보자

• 좌표 정렬 문제는 Comparable 인터페이스 구현하기
  • Comparable 인터페이스에서 compareTo를 구현해주자
  • [this -- o] 순서대로 정렬하려면, 음수를 리턴해주면됨
    • 오름차순이라면 this = 10, o = 20이니 this - o 해주면 [this - o] 순서로 정렬이 되겠지?
    • 내림차순이라면 this = 20, o = 10이니 o - this 해주면 [this - o] 순서로 정렬이 될거야

      import java.util.*;
      
      public class Main {
          class Point implements Comparable<Point> {
              public int x;
              public int y;
      
              public Point(int x, int y) {
                  this.x = x;
                  this.y = y;
              }
      
              @Override
              public int compareTo(Point o) {
                  if (this.x == o.x) {
                      // 음수가 리턴되면 this - o 순서
                      return this.y - o.y;
                  }
                  return this.x - o.x;
              }
          }
      
          private void solution(int[][] array, int number) {
              List<Point> points = new ArrayList<>();
              for (int[] ints : array) {
                  points.add(new Point(ints[0], ints[1]));
              }
              points.sort(Comparator.naturalOrder());
              for (Point point : points) {
                  System.out.println(point.x + " " + point.y);
              }
          }
      
          public static void main(String[] args) {
              Main main = new Main();
              Scanner in = new Scanner(System.in);
              int number = in.nextInt();
              int[][] array = new int[number][2];
              for (int i = 0; i < number; i++) {
                  for (int j = 0; j < 2; j++) {
                      array[i][j] = in.nextInt();
                  }
              }
              main.solution(array, number);
          }
      }
      

• 이분 탐색
  • O(logN)으로 뚝딱 탐색하자
  • lt, rt, mid로 뚝딱

    private int solution(int[] array, int target) {
        Arrays.sort(array);
        int arrayLength = array.length;
        int lt = 0;
        int rt = arrayLength - 1;
        int half = (lt + rt) / 2;
        while(true) {
            if (array[half] == target) {
                return half + 1;
            } else if (array[half] > target) {
                rt = half - 1;
                half = (lt + rt) / 2;
            } else {
                lt = half + 1;
                half = (lt + rt) / 2;
            }
        }
    }
    

• Stream을 사용해 최댓값/합을 구하기

  int lt = Arrays.stream(array).max().getAsInt();
  int rt = Arrays.stream(array).sum();
  

• 결정 알고리즘
  • 범위 내의 답을 찾아나는 과정 (문제가 요구하는 답안으로 좁혀나가자!)
    • 해당 답(mid) 이 정답이 될 수 있는가?
  • 답의 범위가 lt ~ rt 사이에 있음이 확실시 될 때 고려해볼것!