본문 바로가기
코딩테스트

[JAVA] 정렬

you__me 2024. 1. 30. 19:07

2750 수 정렬하기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
import java.util.Arrays;


public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int n = Integer.parseInt(br.readLine());
    int[] num= new int[n];

    for (int i=0; i<n; i++){
      int a = Integer.parseInt(br.readLine());
      num[i]=a;
    }

    Arrays.sort(num);
    for(int val : num) {
      System.out.println(val);
    }
  
  }
}

평범하게 하나하나 비교하면 O(n^2)이 걸린다.

java에서 제공하는 sort 메소드는 O(nlogn)이 걸림(dual pivot algorithm)

 

2587 대표값2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
import java.util.Arrays;


public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int[] num= new int[5];

    for (int i=0; i<5; i++){
      int a = Integer.parseInt(br.readLine());
      num[i]=a;
    }

    Arrays.sort(num);
    int n = (int)Arrays.stream(num).average().orElse(-1);
    System.out.println(n);
    System.out.println(num[2]);
  
  }
}

sort() 메소드와 Arrays 라이브러리에 있는 stream을 이용해서 풀어주었다.

average()는 orElse가 없으면 안됨.

또, JAVA는 int형 변환 과정에서 수의 손실 위험이 있으면 possible lossy conversion from double to int error를 낸다.

강제 형변환을 해주자.

 

25305 커트라인

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;


public class Main {

  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 a = Integer.parseInt(st.nextToken());
    int[] num= new int[n];

    st = new StringTokenizer(br.readLine(), " ");
    for (int i=0; i<n; i++){
      int k = Integer.parseInt(st.nextToken());
      num[i]=k;
    }

    Arrays.sort(num);
    System.out.println(num[n-a]);
  
  }
}

JAVA에서는 내림차순 정렬을 위해서는 따로 import해서 reverseOrder()를 명시해야 한다.

게다가 이게 객체형 변수만 취급해서 int형 배열을 Integer 배열로 바꿔주어야 했는데.. 귀찮아서 그냥 안해줌

 

2751 수 정렬하기 2

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;


public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Integer.parseInt(br.readLine());
    int[] num= new int[n];

    for (int i=0; i<n; i++){
      int a = Integer.parseInt(br.readLine());
      num[i]=a;
    }

    Arrays.sort(num);
    for(int val : num) {
      bw.write(val + "\n");
    }

    bw.flush();
    bw.close();
    br.close();

  }
}

 N은 < 1,000,000이라는 조건이 있어 더 빠른 br, bw를 이용해야 하는 문제

 

10989 수 정렬하기 3

이전 문제와 동일하게 풀어도 아슬아슬하게 통과된다. 

하지만 더 효율적으로 푸는 방법이 있다. 바로 카운팅정렬(위상 정렬)

수가 10,000보다 작다는 조건이 있으므로 이 크기만큼 리스트를 선언하고 +1해준뒤 그만큼 print해주면된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws IOException {
        // 수의 범위 (0 ~ 10000) 사실상 0은 제외
        int[] cnt = new int[10001];
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < N; i++) {
            // 해당 인덱스의 값을 1 증가
            cnt[Integer.parseInt(br.readLine())] ++;
        }
 
        br.close();
 
        StringBuilder sb = new StringBuilder();
 
        // 0은 입력범위에서 없으므로 1부터 시작
        for(int i = 1; i < 10001; i++){
            // i 값이 개수가 0 이 될 때 까지 출력 (빈도수를 의미)
            while(cnt[i] > 0){
                sb.append(i).append('\n');
                cnt[i]--;
            }
        }
        System.out.println(sb);
    }
}

bw 대신 sb를 사용하는 다른 풀이를 가져왔다.

 

1427 소트인사이드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;


public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    String n = br.readLine();
    int[] num= new int[10];

    for (int i=0; i<n.length(); i++){
      num[n.charAt(i)-48]++;
    }

    //System.out.println( Arrays.toString(num));

    for(int i=9;i>=0;i--){
      for(int j=0;j<num[i];j++){
        if (num[i]!=0) System.out.print(i);
      }
    }

    bw.close();
    br.close();

  }
}

위상정렬 이용

 

11650 좌표 정렬하기

Array.sort 정렬을 오버라이딩 해서 재정의해야한다.

sort()는 정렬할 인자의 타입(이 문제는 T[])과 Comperator를 인자로 받는다. 이 Comperator 안에 있는 compare 함수를 재정의 해주어야 하는데, 이 부분은 람다식으로 간단하게 재정의할 수 있다.

즉, Comperator에 대하여 익명 클래스를 생성할 때 int형 배열 T[] 타입을 가진 매개변수를 람다식으로 바꾸어 쓸 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());

    int[][] arr = new int[N][2];

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

    Arrays.sort(arr, (e1, e2) -> {
      if(e1[0] == e2[0]) {
        return e1[1] - e2[1];
      } else {
        return e1[0] - e2[0];
      }
    });

    StringBuilder sb = new StringBuilder();
    for(int i = 0 ; i< N ; i++) {
      sb.append(arr[i][0] + " " + arr[i][1]).append('\n');
    }
    System.out.println(sb);
  }


}

 

Arrays.sort()를 람다식을 사용하지 않으면 아래와 같다.

Arrays.sort(arr, new Comparator<int[]>() {		
	@Override
	public int compare(int[] e1, int[] e2) {
		if(e1[0] == e2[0]) {		// 첫번째 원소가 같다면 두 번째 원소끼리 비교
			return e1[1] - e2[1];
		}
		else {
			return e1[0] - e2[0];
		}
	}
});

 

11651 좌표 정렬하기 2

위 코드에서 x좌표(index 0)와 y좌표(index 1)를 바꾸면 된다

 

1181 단어 정렬

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());

    String[] arr = new String[N];

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

    Arrays.sort(arr, (e1, e2) -> {
      if(e1.length() == e2.length()) {
        return e1.compareTo(e2);
      } else {
        return e1.length()-e2.length();
      }
    });

    StringBuilder sb = new StringBuilder();

    sb.append(arr[0]).append('\n');

    for (int i = 1; i < N; i++) {
      // 중복되지 않는 단어만 출력
      if (!arr[i].equals(arr[i - 1])) {
        sb.append(arr[i]).append('\n');
      }
    }
    System.out.println(sb);
  }
}

단어순 정렬은 compareTo() 를 이용하면 된당

 

10814 나이순 정렬

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;
//import java.io.BufferedWriter;
//import java.io.OutputStreamWriter;
import java.util.Arrays;


public class Main {
  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());

    String[][] arr = new String[N][2];

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

    Arrays.sort(arr, (e1, e2) -> {
      if(Integer.parseInt(e1[0]) != Integer.parseInt(e2[0])) {
        return Integer.parseInt(e1[0]) - Integer.parseInt(e2[0]); 
      } else {
        return 0;
      }
    });

    StringBuilder sb = new StringBuilder();
    for(int i = 0 ; i< N ; i++) {
      sb.append(arr[i][0] + " " + arr[i][1]).append('\n');
    }
    System.out.println(sb);
  }
}

정렬을 하고싶지 않으면 return 0을 하면 된다. 그냥 순서대로 정렬됨.

 

18870 좌표 압축

단순히 정렬 후 계산할 수 없다. 좌표가 중복될 수 있고, 이럴 경우 하나로 계산해야 한다.

따라서 평범하게 정렬한 배열과 이를 이용하여 <원소, rank> 로 된 HashMap을 만든다.

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

import java.util.StringTokenizer;
import java.util.HashMap;
import java.util.Arrays;


public class Main {

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    int N = Integer.parseInt(br.readLine());

    int[] origin = new int[N];	
    int[] sorted = new int[N];	
    HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();	
    
    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    for(int i = 0; i < N; i++) {
      sorted[i] = origin[i] = Integer.parseInt(st.nextToken());
    }

    Arrays.sort(sorted);


    // 정렬 된 배열을 순회하면서 map에 넣어준다.
    int rank = 0;
    for(int v : sorted) {
      if(!rankingMap.containsKey(v)) { // map에 없으면
        rankingMap.put(v, rank);
        rank++;		// map에 넣고나면 다음 순위를 가리킬 수 있도록 1을 더해준다.
      }
    }

    StringBuilder sb = new StringBuilder();
    for(int key : origin) {
      int ranking = rankingMap.get(key);
      sb.append(ranking).append(' ');
    }

    System.out.println(sb);

  }
}

containsKey()를 이용해 HashMap에 중복되는 key값이 있는지 확인하고, 없으면 put() 한다.

이때 정렬한 대로 넣고 rank++ 을 진행하므로 원본 배열 값을 key로 하여 HashMap의 Value를 찾으면 그 key값에 좌표를 압축한 결과가 나온다.

 

# 회고

 

최근 취준하는 언니랑 얘기를 하면서 코테 언어에 대한 고민이 있었다.

이번 정렬을 하면서 Python으로 가자고 느꼈다. 오버라이딩 나오니까 좀 하기 싫어짐..ㅎ

그래도 백엔하려면 기본적인 문법정도는 알고 있어야 하니까 딱 여러 자료구조를 다루는 16번 단계까지만 진행하고

Python으로 다시 가야지^!^

'코딩테스트' 카테고리의 다른 글

[JAVA] 약수, 배수와 소수 2  (1) 2024.02.04
[JAVA] 집합과 맵  (2) 2024.02.01
[JAVA] 브루트 포스  (1) 2024.01.25
[JAVA] 시간 복잡도 단계  (0) 2024.01.24
[JAVA] 기하: 직사각형과 삼각형  (1) 2024.01.23

'코딩테스트' Related Articles

티스토리툴바