0x0F 강 - 문제. 좌표 정렬하기, 역원소 정렬, 빈도정렬, 먹을 것인가 먹힐 것인가

JUN·2024년 7월 15일

11650 2910 5648 7795

codingTest

목록 보기

22/23

📌 서론.

정렬 문제를 딸깍 하고 싶은 마음이 크다. 특히 이번에 병합정렬을 구현하는 과정이 너무 힘들었다.

📚 오늘의 문제.

📝 문제 1. 좌표 정렬하기

링크 : https://www.acmicpc.net/problem/11650

문제 설명

2차원 평면 위의 점 N개가 주어진다. 좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬한 다음 출력하는 프로그램을 작성하시오.

문제 풀이

첫번째로 버블정렬을 사용해서 풀어봤다.

package 정렬;

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

//좌표 정렬하기 11650
public class boj_11650 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //input
    int n = Integer.parseInt(br.readLine());
    int[][] arr = new int[n][2];
    for (int i = 0; i < n; i++) {
      arr[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
    for (int i = 0; i < n - 1; i++) {
      for (int j = 0; j < n - i - 1; j++) {
        if (arr[j][0] > arr[j + 1][0]) {
          int[] temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        } else if (arr[j][0] == arr[j + 1][0]) {
          if (arr[j][1] > arr[j + 1][1]) {
            int[] temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
          }
        }
      }
    }

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

당연히 시간초과가 난다. O(n^2) 이고 주어진 n 이 10^5 이므로 아주 해당 알고리즘은 효율적이지 않다.

강의에서 배운 합병 정렬을 응용해서 풀어봤다.

package 정렬;

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

//좌표 정렬하기 11650
public class boj_11650 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    //input
    int n = Integer.parseInt(br.readLine());
    int[][] arr = new int[n][2];
    for (int i = 0; i < n; i++) {
      String[] input = br.readLine().split(" ");
      arr[i][0] = Integer.parseInt(input[0]);
      arr[i][1] = Integer.parseInt(input[1]);
    }

    // 합병 정렬을 사용.
    mergeSort(arr, 0, n - 1);

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

  public static void mergeSort(int[][] arr, int left, int right) {
    if (left < right) {
      int mid = (left + right) / 2;
      mergeSort(arr, left, mid);
      mergeSort(arr, mid + 1, right);
      merge(arr, left, mid, right);
    }
  }

  public static void merge(int[][] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int[][] leftArr = new int[n1][2];
    int[][] rightArr = new int[n2][2];

    for (int i = 0; i < n1; ++i) {
      leftArr[i][0] = arr[left + i][0];
      leftArr[i][1] = arr[left + i][1];
    }
    for (int j = 0; j < n2; ++j) {
      rightArr[j][0] = arr[mid + 1 + j][0];
      rightArr[j][1] = arr[mid + 1 + j][1];
    }

    int i = 0, j = 0;
    int k = left;
    while (i < n1 && j < n2) {
      if (leftArr[i][0] < rightArr[j][0] || (leftArr[i][0] == rightArr[j][0] && leftArr[i][1] <= rightArr[j][1])) {
        arr[k][0] = leftArr[i][0];
        arr[k][1] = leftArr[i][1];
        i++;
      } else {
        arr[k][0] = rightArr[j][0];
        arr[k][1] = rightArr[j][1];
        j++;
      }
      k++;
    }

    while (i < n1) {
      arr[k][0] = leftArr[i][0];
      arr[k][1] = leftArr[i][1];
      i++;
      k++;
    }

    while (j < n2) {
      arr[k][0] = rightArr[j][0];
      arr[k][1] = rightArr[j][1];
      j++;
      k++;
    }
  }
}

🔑 키워드.

합병 정렬은 배열을 분할하고 병합하는 방식으로 정렬하는 알고리즘에서 주어진 mergeSort와 merge 함수를 이용하여 배열을 정렬하는 과정을 아래 기술했다.

`mergeSort` 함수

분할 단계:
- mergeSort 함수는 배열을 재귀적으로 분할한다. 먼저, 배열을 절반으로 나누어 각각을 정렬한다.
- left가 right보다 작을 때, 배열을 분할한다. 중간 인덱스 mid를 계산하여 왼쪽 부분(left부터 mid)과 오른쪽 부분(mid + 1부터 right)으로 나눈다.
- 각각의 부분 배열에 대해 mergeSort를 재귀적으로 호출한다.
```
public static void mergeSort(int[][] arr, int left, int right) {
  if (left < right) {
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }
}
```

`merge` 함수

병합 단계:

merge 함수는 두 개의 정렬된 부분 배열을 하나의 정렬된 배열로 병합한다.
왼쪽 배열(leftArr)과 오른쪽 배열(rightArr)을 생성하고, 각각의 요소들을 복사한다.
두 부분 배열을 비교하면서 작은 값을 원래 배열(arr)에 넣는다. 이 과정은 두 배열 중 하나가 완료될 때까지 계속된다.
남아있는 요소들은 직접 원래 배열에 복사된다.

public static void merge(int[][] arr, int left, int mid, int right) {
  int n1 = mid - left + 1;
  int n2 = right - mid;

  int[][] leftArr = new int[n1][2];
  int[][] rightArr = new int[n2][2];

  for (int i = 0; i < n1; ++i) {
    leftArr[i][0] = arr[left + i][0];
    leftArr[i][1] = arr[left + i][1];
  }
  for (int j = 0; j < n2; ++j) {
    rightArr[j][0] = arr[mid + 1 + j][0];
    rightArr[j][1] = arr[mid + 1 + j][1];
  }

  int i = 0, j = 0;
  int k = left;
  while (i < n1 && j < n2) {
    if (leftArr[i][0] < rightArr[j][0] || (leftArr[i][0] == rightArr[j][0] && leftArr[i][1] <= rightArr[j][1])) {
      arr[k][0] = leftArr[i][0];
      arr[k][1] = leftArr[i][1];
      i++;
    } else {
      arr[k][0] = rightArr[j][0];
      arr[k][1] = rightArr[j][1];
      j++;
    }
    k++;
  }

  while (i < n1) {
    arr[k][0] = leftArr[i][0];
    arr[k][1] = leftArr[i][1];
    i++;
    k++;
  }

  while (j < n2) {
    arr[k][0] = rightArr[j][0];
    arr[k][1] = rightArr[j][1];
    j++;
    k++;
  }
}

이 병합 정렬 방식은 배열의 크기에 상관없이 O(n log n)의 시간 복잡도로 효율적으로 정렬할 수 있다.

📝 문제 2. 역원소 정렬

링크 : https://www.acmicpc.net/problem/5648

문제 설명

밑처럼 입력 줄에 여러 원소값이 들어갈 수있기에 까다롭다.

문제 풀이

첫번째 풀이

일단 입력값을 파싱한다.

파싱한 값을 arr에 넣는다.

sort 할때 함수를 정렬한다.

package 정렬;

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

// 역원소 정렬 5648

public class boj_5648 {

  public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");

    List<Integer> arr = new ArrayList<>();

    int n = Integer.parseInt(st.nextToken());

    // arr input
    while (arr.size() != n) {
      while (st.hasMoreTokens()) {
        arr.add(Integer.parseInt(st.nextToken()));
      }
      st = new StringTokenizer(br.readLine());
    }

    Integer[] arrArray = arr.toArray(new Integer[0]);

    Arrays.sort(arrArray, new Comparator<Integer>(){
      @Override
      public int compare(Integer i1, Integer i2){
        String s1 = new StringBuilder(i1.toString()).reverse().toString();
        String s2 = new StringBuilder(i2.toString()).reverse().toString();
        return Long.compare(Long.parseLong(s1), Long.parseLong(s2));
      }
    });

    for (Integer num : arrArray) {
      sb.append(num).append("\n");
    }
    System.out.print(sb);

    br.close();
  }
}

이렇게 정렬할 경우 출력은 뒤집힌 원소가 아니라 원래 원소가 나온다. 다시 뒤집어줘야하는데 비효율적인 것 같아 처음 파싱할때 바꿔주는 것으로 바꿨다.

package 정렬;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;

// 역원소 정렬 5648
public class boj_5648 {

  public static void main(String[] args) throws IOException {
    StringBuilder sb = new StringBuilder();
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");

    List<Long> arr = new ArrayList<>();

    int n = Integer.parseInt(st.nextToken());

    // arr input
    while (arr.size() != n) {
      while (st.hasMoreTokens()) {
        String original = st.nextToken();
        String reversed = new StringBuilder(original).reverse().toString();
        arr.add(Long.parseLong(reversed));
      }
      if (arr.size() < n) {
        st = new StringTokenizer(br.readLine());
      }
    }

    arr.sort(Comparator.naturalOrder());

    for (Long num : arr) {
      sb.append(num).append("\n");
    }
    System.out.print(sb);

    br.close();
  }
}

🔑 키워드.

// arr input
while (arr.size() != n) {
    while (st.hasMoreTokens()) {
        String original = st.nextToken();
        String reversed = new StringBuilder(original).reverse().toString();
        arr.add(Long.parseLong(reversed));
    }
    if (arr.size() < n) {
        st = new StringTokenizer(br.readLine());
    }
}

📝 문제 3. 빈도 정렬

링크 : https://www.acmicpc.net/problem/2910

문제 설명

문제 풀이

카운팅 소트를 구현하는 문제는 아니다. C 가 10억이기 때문.

→ 계수행렬을 딕셔너리로 구현하면 되지 않을까?

package 정렬;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

// 빈도 정렬 2910
// 카운팅 소트를 구현하는 문제가 아니다. C 가 10억이기 때문.
// 계수행렬을 딕셔너리로 구현하면 되지 않을까?
public class boj_2910 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int c = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    HashMap<Integer, Integer> freArr = new HashMap<>(); // key : 해당 수, value : 빈도

    // 계수 딕셔너리 초기화
    while (st.hasMoreTokens()) {
      int cur = Integer.parseInt(st.nextToken());
      freArr.put(cur, freArr.getOrDefault(cur, 0) + 1);
    }

    // c를 준 이유가 있을 듯. HashMap은 정렬이 되지 않으니 c~1 까지 한번 돌리면서 값이 있으면 해당 수를 출력하는 식으로 진행하면 될듯. 그러면 시간복잡도 O(2n) = O(n)
    StringBuilder sb = new StringBuilder();
    for (int i = c; i > 0; i--) {
      for (int j = 0; j < freArr.getOrDefault(i,0); j++) { // 빈도 수 만큼 반복
        sb.append(i).append(' ');
      }
    }
    System.out.println(sb.toString());
    br.close();
  }
}

흠 뭔가 이상하다.

알고보니 dictionary에 들어간 수들의 빈도를 기준을 정렬하는거였다.ㅎㅎㅎ;;

package 정렬;

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

public class boj_2910 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        // 입력받은 수와 그 빈도를 저장할 맵
        LinkedHashMap<Integer, Integer> frequencyMap = new LinkedHashMap<>();

        // 입력받은 순서대로 리스트에 추가
        List<Integer> numbers = new ArrayList<>();

        // 빈도 계산 및 입력 순서 유지
        st = new StringTokenizer(br.readLine());
        while (st.hasMoreTokens()) {
            int num = Integer.parseInt(st.nextToken());
            numbers.add(num);
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // 리스트 정렬
        numbers.sort((a, b) -> {
            int freqCompare = frequencyMap.get(b).compareTo(frequencyMap.get(a));
            if (freqCompare == 0) {
                return numbers.indexOf(a) - numbers.indexOf(b);
            }
            return freqCompare;
        });

        // 출력
        StringBuilder sb = new StringBuilder();
        for (int num : numbers) {
            sb.append(num).append(' ');
        }
        System.out.println(sb.toString().trim());
        br.close();
    }
}

input 을 ArrayList 에 초기화시켜준 sort함수를 사용했다.

sort의 comparator 는 다음 1차로 빈도 기준으로 정리하고 빈도가 같을 경우 처음 들어온 시점을

🔑 키워드.

// 계수 딕셔너리 초기화
while (st.hasMoreTokens()) {
    int cur = Integer.parseInt(st.nextToken());
    freArr.put(cur, freArr.getOrDefault(cur, 0) + 1);
}

📝 문제 4. 먹을것인가 먹힐것인가

링크 : https://www.acmicpc.net/problem/7795

문제 설명

두 집합 A, B가 주어졌을 때 A→B에서 a가 b 보다 큰 개수를 구하는 문제.

문제 풀이

이렇게 두 쌍의 배열의 주어졌을 때

A : 8 1 7 3 1
B : 3 6 1

A, B를 정렬한 이후 A를 순차적으로 비교하기 시작해보자.

A : 8 7 3 1 1
B : 6 3 1

a[0] : 8 과 b[0] 6 비교 → A 가 더 큼 (뒤에 있는 수들은 모두 6보다 작으므로 result += b.length - b.index 인 3을 더해준다.)
a[1] : 7 과 b[0] 6 비교 → A 가 더 큼 (뒤에 있는 수들은 모두 6보다 작으므로 result += b.length - b.index 인 3을 더해준다.)
a[2] : 3 과 b[0] 6 비교 → B 가 더 큼 (b.index++)

a[2] : 3 과 b[1] 3 비교 → 같음 (b.index++)

a[2] : 3 과 b[2] 1 비교 → A 가 더 큼 (뒤에 있는 수들은 모두 1보다 작으므로 result += b.length - b.index 인 1을 더해준다.)

흠 이제 원리는 알았따.

배열 A와 B를 오름차순으로 정렬
A의 모든 요소에 대해 아래 과정을 반복
1. 만약 A의 요소가 B의 요소보다 크다면 bIndex를 증가
2. 작다면 bIndex가 가리키는 인덱스까지의 B 배열의 요소 개수를 result에 더함.
최종 result 값을 출력


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class boj_7795 {

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringBuilder sb = new StringBuilder();
    int tc = Integer.parseInt(br.readLine());
    StringTokenizer st;

    for (int i = 0; i < tc; i++) {
      st = new StringTokenizer(br.readLine());

      // a, b 초기화
      int lengthOfA = Integer.parseInt(st.nextToken());
      int lengthOfB = Integer.parseInt(st.nextToken());

      List<Integer> a = new ArrayList<>();
      List<Integer> b = new ArrayList<>();

      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < lengthOfA; j++) {
        a.add(Integer.parseInt(st.nextToken()));
      }

      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < lengthOfB; j++) {
        b.add(Integer.parseInt(st.nextToken()));
      }

      Collections.sort(a, Collections.reverseOrder());
      Collections.sort(b, Collections.reverseOrder());

      int result = 0;
      int bIndex = 0;

      for (int j = 0; j < lengthOfA; j++) {
        while (bIndex < lengthOfB && a.get(j) <= b.get(bIndex)) { // 만약 A의 요소가 B의 요소보다 크다면 bIndex를 증가
          bIndex++;
        }
        if (bIndex < lengthOfB) { // 작다면 bIndex가 가리키는 인덱스까지의 B 배열의 요소 개수를 result에 더함.
          result += (lengthOfB - bIndex);
        }
      }

      sb.append(result).append('\n');
    }

    System.out.println(sb.toString());
    br.close();
  }
}

🎯 결론.

문제를 한번에 적으니 조금 보기 힘든 감이 있다. 나눌 필요가 있는듯...

JUN

순간은 기록하고 반복은 단순화하자 🚀

이전 포스트

0x0A 강 - 문제. 별찍기 - 10

다음 포스트

0x0F 강 - 문제. 좌표 정렬하기, 역원소 정렬, 빈도정렬, 먹을 것인가 먹힐 것인가

codingTest

📌 서론.

📚 오늘의 문제.

📝 문제 1. 좌표 정렬하기

🔑 키워드.

`mergeSort` 함수

`merge` 함수

📝 문제 2. 역원소 정렬

첫번째 풀이

🔑 키워드.

📝 문제 3. 빈도 정렬

🔑 키워드.

📝 문제 4. 먹을것인가 먹힐것인가

🎯 결론.

0x0A 강 - 문제. 별찍기 - 10

바킹독 0x0F 강 - 정렬 알고리즘 (JAVA)

0개의 댓글

0x0F 강 - 문제. 좌표 정렬하기, 역원소 정렬, 빈도정렬, 먹을 것인가 먹힐 것인가

codingTest

📌 서론.

📚 오늘의 문제.

📝 문제 1. 좌표 정렬하기

🔑 키워드.

mergeSort 함수

merge 함수

📝 문제 2. 역원소 정렬

첫번째 풀이

🔑 키워드.

📝 문제 3. 빈도 정렬

🔑 키워드.

📝 문제 4. 먹을것인가 먹힐것인가

🎯 결론.

0x0A 강 - 문제. 별찍기 - 10

바킹독 0x0F 강 - 정렬 알고리즘 (JAVA)

0개의 댓글

`mergeSort` 함수

`merge` 함수