[2025 1학기 알고리즘 스터디] 남윤찬 #1주차

1주차는 정렬 문제 3개입니다.

10989 - 수 정렬하기 3

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

public class Main {
    public static void main(String[] args) throws IOException{
    	// 입력 받을 수 있는 값이 많기에 BufferedReader 사용
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        // 어떤 숫자가 몇 번 나왔는지 배열에 체크
        for (int i = 0; i < n; i++) {
            nums[Integer.parseInt(br.readLine())]++;
        }

        // 가장 작은 수부터 나온 개수만큼 출력
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10001; i++) {
            while (nums[i] > 0) {
                sb.append(i).append("\n");
                nums[i]--;
                n--;
            }
            if (n == 0) break;

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

정렬을 하되, 개수가 많아지면 입력 받는 시간이 늘어나 Scanner보다 BufferedReader를 이용하는 편이 실행 속도가 빠르다. 그리고 모든 입력 받은 숫자를 배열에 넣고 정렬하기보다, 주어지는 숫자가 제한되어 있으니 어떤 숫자가 몇 개 나왔는지를 체크하고 그 개수만큼 출력하면 정렬의 과정이 필요 없이(순서대로 0이 아닌 수만 출력하면 되기 때문에) 출력해낼 수 있다.

 

 

11652 - 카드

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

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());

        HashMap<Long, Integer> cards = new HashMap<>();

        for (int i = 0; i < n; i++) {
            Long c = Long.parseLong(br.readLine());
            // 나왔던 카드면 횟수+1, 아니면 카드와 횟수1로 맵에 추가
            cards.put(c, cards.getOrDefault(c, 0)+1);
        }
        
        int count = -1;
        long answer = 0;
        for (long l : cards.keySet()) {
            // 더 많이 나왔으면 카드와 횟수 변경
            if (cards.get(l) > count) {
                count = cards.get(l);
                answer = l;
            // 나온 횟수가 같으면 더 작은 카드로 변경
            } else if (cards.get(l) == count) {
                answer = Math.min(l, answer);
            }
        }

        System.out.println(answer);
    }
}

Java로는 HashMap의 getOrDefault(key, defaultValue)라는 메서드를 활용하면 해결하기 쉬운 문제였으나, 이것을 몰랐어서 헤맸다. 카드의 값을 key, 개수를 value로 보고 hashmap을 만들고, 가장 적은 카드를 출력하면 된다.

 

18870 - 좌표 압축

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

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[] nums = new int[n];
        int[] sorted = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();

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

        // 정렬된 좌표를 <원래 좌표값, 압축된 값>으로 맵에 추가
        int count = 0;
        for (int s : sorted) {
            if (!map.containsKey(s)) {
                map.put(s, count++);
            }
        }
        
        // 입력 받은 순서대로 압축된 값을 출력
        StringBuilder sb = new StringBuilder();
        for (int i : nums) {
            sb.append(map.get(i)).append(" ");
        }
        System.out.println(sb);
    }
}

이 문제도 HashMap을 이용하는 문제이다. 원래 좌표의 값을 key로, 압축한 값(count++하며 바꾼 값)을 value로 map에 저장한 뒤, 처음 입력받은 좌표 값을 key로 map에서 찾아 압축한 값을 StringBuilder에 이어 붙여 출력하면 된다.

 

+) HashMap이란

이번 문제들 중 2개에서 사용한 HashMap은 Java의 컬렉션 중 하나이다. 간단히 요약하자면, 데이터를 Key와 Value를 짝지어 저장하는데, Key값으로 실행한 해시함수의 결과로 저장 위치를 결정하여 검색이 빠르다는 장점이 있으며 Key값은 중복될 수 없다는 특징도 있다.