[백준 2751번, 백준 10814번, LeetCode 179번] 정렬 문제 풀이

[백준 2751번] 수 정렬하기 2

https://www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

 

접근 방법

N개의 수가 주어졌을 때, 오름차순 정렬하는 문제입니다.

1. 문자열로 입력받은 부분을 Integer.parseInt() 메서드를 통해 정수로 바꿔줍니다.

2. 배열을 만든 후 for문을 돌면서 입력받은 문자열 ➡ 정수를 차례로 넣습니다.

3. 정렬 후 출력합니다. 

 

코드 구현

1. 실패 코드

import java.util.*;        
import java.io.*;  

public class Main {
    public static void main(String[] ars) 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[] arr = new int[n];

        for(int i=0; i<arr.length; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        for(int j=0; j< arr.length; j++){
            bw.write(arr[j]);
            bw.newLine();
        }
        bw.flush();
    }
}

 

원인:

Java에서 bw.write(int) 메소드는 정수를 문자열로 변환하지 않고 해당 정수의 문자 코드(유니코드 문자)를 출력합니다.

 

해결 방법:

정수를 문자열로 변환한 후에 write 메소드를 사용합니다.

bw.write(String.valueOf(arr[j])) 또는

bw.write(Integer.toString(arr[j]))

 

2. 성공 코드

import java.util.*;        
import java.io.*;   

public class Main {
    public static void main(String[] ars) 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[] arr = new int[n];

        for(int i=0; i<arr.length; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        for(int j=0; j< arr.length; j++){
            bw.write(Integer.toString(arr[j]));
            bw.newLine();
        }
        bw.flush();
    }
}

 

---

[백준 10814번] 나이순 정렬

https://www.acmicpc.net/problem/10814

10814번: 나이순 정렬

 

접근 방법

나이 순으로 출력하되, 나이가 같으면 가입한 순으로 출력합니다.

1. 해시맵으로 나이, 이름을 입력받습니다.

2. Collections.sort 정렬을 통해 키로 정렬하고, 키(나이)가 같으면 값으로 정렬합니다.

  하지만 HashMap은 정렬을 지원하지 않는 데이터 구조로 리스트로 변환 후 정렬합니다.

 

코드 구현

1. 실패 코드

import java.util.*;         
import java.io.*; 

public class Main {
    public static void main(String[] ars) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        Map<Integer, String> hashMap = new HashMap<>();

        for(int i=0; i<N; i++){
            String[] input = br.readLine().split(" ");
            int key = Integer.parseInt(input[0]);
            String value = input[1];
            hashMap.put(key, value);
        }
        
        List<Map.Entry<Integer, String>> list = new ArrayList<>(hashMap.entrySet());
        Collections.sort(list, new Comparator<Map.Entry<Integer, String>>() {
            @Override
            public int compare(Map.Entry<Integer, String> o1, Map.Entry<Integer, String> o2) {
                int ageCompare = o1.getKey().compareTo(o2.getKey());
                return ageCompare == 0 ? o1.getValue().compareTo(o2.getValue()) : ageCompare;
            }
        });
        
        for(Map.Entry<Integer, String> entry : list){
            bw.write(entry.getKey() + " " + entry.getValue());
            bw.newLine();
        }
        bw.flush();
    }
}

 

원인:

테스트 케이스 입력에 따른 출력을 살펴보겠습니다.

// [ 입력 ]
3
21 Junkyu
21 Dohyun
20 Sunyoung

// [ 출력 ]
20 Sunyoung
21 Dohyun

 

나이가 같을 때, 입력 순으로 출력하는 게 아닌  알파벳순으로 출력되었습니다.

나이가 같아도 데이터를 다 출력해야 하는데 하나만 출력되었습니다.

 

2. 해결 - 성공코드

해시맵을 리스트로 변환하는 방법이 아닌 String[][] 사용해서 풀이했습니다.

import java.util.*;         
import java.io.*; 

public class Main {
    public static void main(String[] ars) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        String[][] members = new String[N][2];

        for (int i = 0; i < N; i++) {
            String[] input = br.readLine().split(" ");
            members[i][0] = input[0];
            members[i][1] = input[1];
        }

        Arrays.sort(members, new Comparator<String[]>() {
            @Override
            public int compare(String[] s1, String[] s2) {
                return Integer.parseInt(s1[0]) - Integer.parseInt(s2[0]);
            }

        });

        for (int i = 0; i < N; i++) {
            bw.write(members[i][0] + " " + members[i][1]);
            bw.newLine();
        }

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

 

- s1[0]이 s2[0]보다 작으면 음수를 리턴하고 s1이 s2보다 앞에 위치하게 됩니다.

- 두 요소가 같으면 결과가 0을 리턴하고 그 순서는 변경되지 않습니다. = 들어온 순서대로 저장됨

- s1[0]이 s2[0]보다 크다면 양수를 리턴하고 s1이 s2보다 뒤에 위치하게 됩니다.

 

 

배우게 된 점

1. 입력이 이런 형태로 오면 HashMap코드를 어떻게 짜야할까? ➡ 키, 밸류 형태로 온다고 무조건 해시맵으로 한정지어서 생각하는 습관 버리기.

// 입력
21 Junkyu
21 Dohyun
20 Sunyoung

Map<Integer, String> hashMap = new HashMap<>();

for(int i=0; i<N; i++){
    String[] input = br.readLine().split(" ");
    int key = Integer.parseInt(input[0]);
    String value = input[1];
    hashMap.put(key, value);
}

 

2-1. 컬렉션을 정렬하기 

키를 기준으로 정렬, 만약 키가 같으면 이름으로 정렬하고자 합니다. 

😂 Java에서 HashMap은 정렬을 지원하지 않는 데이터 구조로 HashMap은 키-값 쌍을 저장하는 데에 최적화되어 있으며, 키의 순서는 고려되지 않습니다.

 

리스트로 변환 후 정렬하기: 키-값 쌍을 리스트로 변환한 후, Collections.sort를 사용하여 정렬할 수 있습니다. 이때 Comparator를 사용하여 정렬 기준을 정의할 수 있습니다.

Map<Integer, String> hashMap = new HashMap<>();

// 해시맵 -> 리스트로 변환
List<Map.Entry<Integer, String>> entries = new ArrayList<>(hashMap.entrySet());

// 리스트 정렬
Collections.sort(entries, new Comparator<Map.Entry<Integer, String>>() {
    @Override
    public int compare(Map.Entry<Integer, String> o1, Map.Entry<Integer, String> o2) {
        // 먼저 키를 비교
        int ageCompare = o1.getKey().compareTo(o2.getKey());
        // 키가 같다면 값을 비교
        return ageCompare == 0 ? o1.getValue().compareTo(o2.getValue()) : ageCompare;
    }
});

 

2-2. 출력

BufferedWriter를 사용하여 출력할 때, write메서드는 문자열을 인자로 받기 때문에 Map.Entry 객체를 문자열로 변환해야 합니다. getKey()와 getValue() 메서드를 사용하여 키와 값을 가져옵니다.

for(Map.Entry<Integer, String> entry : list){
    bw.write(entry.getKey() + " " + entry.getValue());
    bw.newLine();
}

bw.flush();

 

3. HashMap과 LinkedHashMap 차이: 내부 데이터 구조와 순서 보장

HashMap

• HashMap은 키-값 쌍을 저장하는 데 사용되는 맵 구현입니다.
• 이 구현은 해시 테이블을 사용하여 요소를 저장합니다.
• HashMap의 주요 장점은 put, get, containsKey 같은 기본 연산들이 평균적으로 O(1) 시간 복잡도로 매우 빠릅니다.
• 그러나 HashMap은 요소들을 순서 없이 저장합니다. (순서 보장x)

LinkedHashMap

• LinkedHashMap 역시 HashMap과 마찬가지로 키-값 쌍을 저장하지만, 추가된 순서를 유지합니다.
• 이 구현은 내부적으로 해시 테이블과 연결 리스트를 사용하여 요소를 저장하며, 이로 인해 요소들이 추가된 순서대로 반복될 수 있습니다.

언제 사용하는가?

• HashMap:
  • 순서가 중요하지 않고, 키-값 쌍을 빠르게 저장하고 검색할 필요가 있는 경우 사용합니다.
  • 메모리 사용량이 중요한 경우, LinkedHashMap보다 약간 더 효율적입니다.
• LinkedHashMap:
  • 키-값 쌍을 추가한 순서대로 반복하거나 접근해야 할 때 사용합니다.
  • 캐시 구현(LRU 캐시 등)과 같이 순서가 중요한 시나리오에서 유용합니다.

 

4. 적절한 자료구조를 사용하자! 너무 어렵게 생각하지 말자, String[][]을 사용했으면 더 간단하게 끝났을 문제..

---

[LeetCode] 179. Largest Number

https://leetcode.com/problems/largest-number/description/

LeetCode - The World's Leading Online Programming Learning Platform

 

접근 방법

1. 정렬을 할 때 ab와 ba를 모두 비교해서 큰 쪽으로 정렬합니다.
2. 1번처럼 비교하기 위해서는 문자열로 조합해야  'ab', 'ba' 이런식으로 비교가 가능합니다.

 

접근 방법

성공 코드

import java.util.*;

class Solution {
    public String largestNumber(int[] nums) { 
        String res = "";
        String[] str = new String[nums.length];

        for(int i=0; i<str.length; i++){
            str[i] = String.valueOf(nums[i]);
        }

        Arrays.sort(str, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                return (o2+o1).compareTo(o1+o2);
            }
        });

        if(str[0].equals("0")) {
            return "0";
        }

        for(String data : str){
            res+=data;
        }

        return res;
    }

}

 

배우게 된 점

1. 'ab', 'ba' 이런 식으로 비교한다는 아이디어는 어떻게 생각해내야 하는 걸까.. 더 다양한 문제를 풀어야 함을 알게 되었습니다.