백준 2870번 : 수학숙제

게시 2024/03/04

By Jeremiah Lee 6 분 : 읽는 시간

최근에는 정렬 문제를 몰아서 풀고 있다.

알고리즘 중 가장 자주 접할 수 있으며, 실제 개발 시에도 자주 사용할 법한 두 가지가 탐색과 정렬이라고 생각한다.

그렇기 때문에 탐색 문제를 계속 풀었으니 이제 정렬로 넘어온 것이다.

기록이 멈춘 보름 동안 여러 문제를 풀었지만 특이했고, 알지 못하면 사용하지 못하는 방법으로 풀어낸 문제를 들고 왔다.

이번 문제는 100까지의 길이의 문자열을 입력 받아, 해당 문자열에 포함된 연속된 숫자를 추출하여 정렬 후 출력하는 문제이다.

예를 들어

4
43silos0
zita002
le2sim
231233

위와 같이 4개의 문자열을 입력 받는 경우, 출력은

이렇게 정수만 추출해 출력해야한다.

이 문제의 의도는 알기 쉽다.

우선은 문자열에서 정수를 추출하여야 하는데, char을 사용하거나 정규표현식을 사용하면 된다고 생각하여

우선 char 배열로 만들어서 추출하는 작업을 해보았다.

그러나 연속된 숫자를 추출하기가 어려웠고, 조금 더 쉬운 방법이 없을까 생각하다가 정규표현식을 사용하게 되었다.

String str = "43silos0";
str = str.replaceAll("[^0-9]", ""); // 숫자가 아닌 모든 문자를 공백으로 대체
System.out.println(str); // 출력 결과: 430

정규표현식의 사용법은 다양하다.

위와 같이 문자열에서 숫자를 제외한 모든 문자를 공백으로 대체하는 방법도 있다.

하지만 위의 방법의 경우, 마찬가지로 연속된 숫자만을 추출하기는 어렵다.

그래서 아래와 같이 정규표현식 “패턴”을 사용하여 문자에서 숫자를 추출했다.

  
Pattern pattern = Pattern.compile("\\d+"); < 숫자가 연속으로 나타나는 패턴
Matcher matcher = pattern.matcher(str); < 문자에 위의 패턴 적용

위에서, 숫자가 연속으로 나타나는 패턴을 찾기 위해 “\d+” 패턴을 지정하고 이 패턴을 matcher를 사용해 문자열에 적용한다.

그 다음으로

  
while (matcher.find()) {
    nums.add(new BigInteger(matcher.group()));
}

반복하여 matcher에서 패턴을 적용한 문자열(숫자)를 찾아 통째로 nums List에 삽입한다.

이후에는

  
Collections.sort(nums);
StringBuilder sb = new StringBuilder();
for (BigInteger num : nums) {
    sb.append(num).append('\n');
}

System.out.println(sb);

해당 결과값을 정렬한 다음 출력했다.

여기서 정규표현식 뿐만 아니라 BigInteger라는 클래스도 처음 발견했는데, 데이터베이스를 다루면서 Bigint라는 타입은 알고 있었어도 자바에서 BigInteger라는 클래스를 사용할 수 있는지는 몰랐다.

이 BigInteger 클래스는 java.math 라이브러리에 포함되어 있으며, int나 long 과 같은 타입과 달리 정수를 제한 없이 표현해준다.

왜 이러한 BigInteger 를 int나 long을 대체하여 이번 알고리즘에서 사용했냐면, 문제에서 문자열의 길이가 100 이상이기 때문에, 이는 int, long 타입의 범위를 벗어나기 때문이다.

정수를 길이 제한 없이 그대로 표현해주는 BigInteger 를 사용하여 문제를 풀어냈다.

전체 코드는 다음과 같다.

  
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

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

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

        List<BigInteger> nums = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            String str = br.readLine();
            Pattern pattern = Pattern.compile("\\d+");
            Matcher matcher = pattern.matcher(str);

            while (matcher.find()) {
                nums.add(new BigInteger(matcher.group()));
            }
        }

        Collections.sort(nums);
        StringBuilder sb = new StringBuilder();
        for (BigInteger num : nums) {
            sb.append(num).append('\n');
        }

        System.out.println(sb);
    }
}

보름 정도 포스트를 하지 않았다.

salog 프로젝트를 마무리하고, 적용한 내용을 정리하고, 정보처리기사 시험도 보고, 면접도 보고….

좀 많은 일이 있었어서 그 일에 대처하느라 블로깅에 신경쓰질 못 했다.

더구나 요즘 정렬로 들어오면서 다시 쉬운 난이도 부터 알고리즘을 풀고 있기 때문에 딱히 작성할 내용도 없었다.

그래도 오늘을 기점으로 다시 알고리즘에 대해 작성할 일도 생겼고, 프로젝트에서 적용했던 Oauth2나 수동 Https 프로토콜 변경 등, 작성할 일이 생겼기 때문에 조금씩 다시 포스트 할 예정이다.

알고리즘, 백준

알고리즘 백준

인기 태그