2609번, 2693번 - hashSet, QuickSort

브론즈 문제를 한두개 더 풀어보다가 실버 문제를 풀어보기로 했다.

먼저 최대공약수와 최소공배수라는 문제를 풀어보았다.

• 2609번 최대공약수와 최소공배수
  

  import java.util.*;
  
  public class Main {
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
  
          int fir = sc.nextInt();
          int sec = sc.nextInt();
          int min = Math.min(fir, sec);
          int max = Math.max(fir, sec);
  
          Set<Integer> hashSet = new HashSet<>();
          for (int i = 1; i <= min/2; i++) {
              if (min % i == 0) {
                  hashSet.add(i);
              }
          }
          hashSet.add(min);
  
          for (int i = min; i >= 1; i--) {
              int size = hashSet.size();
              if (max % i == 0) {
                  hashSet.add(i);
                  if (size == hashSet.size()) {
                      System.out.println(i);
                      break;
                  }
              }
          }
  
          long lcm = max;
          while (lcm % min != 0) {
              lcm += max;
          }
          System.out.println(lcm);
      }
  }

  최대공약수를 구할 때는 hashSet의 성질을 이용했다.
  hashSet은 동일한 요소를 포함하지 않는다.
  고로 먼저 min의 약수를 모두 구해놓고 max의 약수를 구하며 hashSet이 커지는지 검사했다.
  max의 약수는 min 부터 구해보면 시간이 더더욱 단축된다.
  
  최소공배수는 더욱 쉬운데 max에 max값을 하나씩 더해보며,
  min 값으로 나눴을 때 나머지가 0이 나오는 수를 구하면 된다.
  
  
• 2693번 N번째 큰 수
  

  import java.util.*;
  
  public class Main {
      public static void main(String[] args) {
          Scanner sc = new Scanner(System.in);
          int T = sc.nextInt();
          Queue<Integer> queue = new LinkedList<>();
  
          for (int i = 0; i < T; i++) {
              int[] tenNum = new int[10];
              for (int j = 0; j < 10; j++) {
                  tenNum[j] = sc.nextInt();
              }
              queue.add(quickSort(tenNum,0,9));
          }
  
          while (!queue.isEmpty()) {
              System.out.println(queue.poll());
          }
      }
  
      static int quickSort(int[] num, int left, int right) {
          int le = left;
          int ri = right;
          int pivot = num[(le + ri) / 2];
  
          do {
              while (num[le] < pivot) {
                  le++;
              }
              while (num[ri] > pivot) {
                  ri--;
              }
              if (le <= ri) {
                  swap(num, le++, ri--);
              }
          } while (le <= ri);
  
          if (left < ri) {
              quickSort(num, left, ri);
          }
          if (le < right) {
              quickSort(num, le, right);
          }
          return num[7];
      }
  
      static void swap(int[] num, int le, int ri) {
          int temp = num[le];
          num[le] = num[ri];
          num[ri] = temp;
      }
  }

  
  quickSort에 대한 기억을 간만에 되살려보았다.
  재귀를 이용한 정렬 방식인데, 가장 빠른 정렬 방법이라고 알고 있다.
  중간에 기준인 pivot을 잡아놓고, 해당 수보다 작으면 왼쪽으로 크면 오른쪽으로 넘기면 된다.
  왼쪽과 오른쪽이 오다가 만나면 재귀가 일어난다.
  정렬이 끝나면 3번째 큰 수인 num[7]이 반환된다.
  queue는 지금보니 굳이 쓸 필요 없고 바로 출력 해주면 된다.

이렇게 간만에 백준 실버 문제들을 풀어보았다.
실버 저티어 문제들이나, 자료구조에 대한 지식을 문제에서 조금씩 요구하는 것 같다.