[2025 1학기 알고리즘 스터디] 1주차 김민재

수 정렬하기3

처음에 너무 간단해 왜 간단할까 생각하며 코드를 작성했고 

바로 시간 초과가 떴다

import java.util.Arrays;
import java.util.Scanner;

public class NumSort3 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int[] num = new int[n];

        for (int i = 0; i < n; i++) {
            num[i] = sc.nextInt();
        }

//        for (int i = 0; i < n-1; i++) {
//            for (int j = 1; j < n-1-i; j++) {
//                if (num[j] > num[j+1]) {
//                    int tmp;
//                    tmp = num[j];
//                    num[j] = num[j+1];
//                    num[j+1] = tmp;
//                } else {
//                    continue;
//                }
//             }
//        }
        Arrays.sort(num);
        
        for (int i = 0; i < n; i++) {
            System.out.println(num[i]);
        }

    }
}

 

만든 버블 정렬도 사용해보고, 내장된 함수도 사용했지만 시간 초과가 발생했다

 

버퍼 뭐시기가 더 성능이 좋아 들어, Scanner를 사용해서 그런가 해서 BufferReader를 사용해서 풀어봤다

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

public class NumSort3 {

    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++) {
            num[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(num);

        for (int i = 0; i < n; i++) {
            bw.write(num[i] + "\n");
        }
        
        bw.flush();
        bw.close();
        br.close();
    }
}

 

 

 

카드

처음에는 정렬하고 리스트를 사용해서 하나씩 개수를 세고 최빈값을 구해야 하나 생각했었다

그래서 어떻게 풀까 하다 밑에 알고리즘 종류를 봤다

해시맵이 적혀있길래 사용해봐야겠다 생각하고 사용했다

 

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

public class Card {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        // hashMap 생성 후 매핑
        Map<Long, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            long m = Long.parseLong(br.readLine());
            map.put(m, map.getOrDefault(m, 0) + 1);
        }

        // 최대 빈도수와 최빈값
        int maxNum = 0;
        long num = 0;

        //map에서 빈도수 체크
        for (long i : map.keySet()) {
            //기존 maxNum보다 크면 교체
            if (map.get(i) > maxNum) {
                maxNum = map.get(i);
                num = i;
                // 같은 경우 작은 숫자가 최대 빈도 num
            } else if (map.get(i) == maxNum) {
                num = Math.min(i, num);
            }
        }
        System.out.println(num);
        
        br.close();
    }
}

 

 

 

좌표 압축

문제를 읽어봤는데 이게 왜 좌표 압축인가 생각했었다

찾아보니 값의 순서대로 0번부터 부여하는 방식이였다

해시맵을 이용해서 번호에 해당하는 랭크를 부여하고, StringBuilder를 사용해서 문자를 대량으로 다루었다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class CoordinateComp{

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<Integer, Integer> map = new HashMap<>();

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

        String[] input = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            num[i] = Integer.parseInt(input[i]);
            sorted[i] = num[i];
        }

        Arrays.sort(sorted);

        int rank = 0;
        for (int value : sorted) {
            if(!map.containsKey(value)){
                map.put(value,rank);
                rank++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int value : num) {
            sb.append(map.get(value)).append(" ");
        }

        System.out.println(sb);

    }
}