[백준 JAVA] 2870 수학숙제

2870 수학숙제

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

문제설명

정규식을 사용해 숫자를 추출하고 내림차 순으로 정렬

접근방식

O(N log N) collections.sort

 

N개의 줄에서 각 줄(L)마다 숫자를 추출하고 리스트에 저장한다. 

그리고 Collections.sort로 정렬한다. 

Collections.cort는 O(N log N)의 시간 복잡도를 가진다.

문제 조건 분석 과정

• ArrayList<String>인 numbers에 숫자 저장. 정규 표현식을 사용하여 숫자를 추출한다.
• '\\d' 로 숫자의 해당하는 패턴을 검사했다. 이 패턴에 맞는 숫자를 찾아 리스트에 저장한다.
• Collection.sort를 사용하여 numbers 리스트를 정렬한다.
• 내림차순으로 정렬하기 위해 Comparator을 사용했다.
• 처음엔 treemap으로 정렬하려고 했으나 오름차순으로 정렬되어 중간에 Comparator로 바꿨다.

사용된 자료구조

• ArrayList: 숫자를 저장하는 리스트
• Pattern, Matcher: 정규 표현식을 이용한 숫자 추출
• Comparator: 매개변수들을 비교하여 내림차순으로 정렬

전체코드

import java.io.*;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        ArrayList<String> numbers = new ArrayList<>();

        // 정규 표현식 패턴 설정
        Pattern pattern = Pattern.compile("\\d+");

        int N = Integer.parseInt(br.readLine()); // 종이의 줄의 개수 N

        // 각 줄을 읽어 숫자를 추출하여 리스트에 저장
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            Matcher matcher = pattern.matcher(line);

            while (matcher.find()) {
                String num = matcher.group().replaceAll("^0+", ""); // 숫자 추출 후 앞의 0 제거
                numbers.add(num.isEmpty() ? "0" : num); // 숫자가 없으면 "0"으로 처리
            }
        }

        // 비내림차순으로 정렬하기
        Collections.sort(numbers, (o1, o2) -> {
            if (o1.length() == o2.length()) { // 길이가 같으면 사전순으로 정렬
                return o1.compareTo(o2);
            } else { // 길이가 다르면 길이가 짧은 순서대로 정렬
                return o1.length() - o2.length();
            }
        });

        // 결과를 StringBuilder에 추가
        for (String num : numbers) {
            sb.append(num).append('\n');
        }

        System.out.print(sb); // 결과 출력

        br.close();
    }
}