2870번: 수학숙제

문제

종이에서 숫자만 찾아서 비내림차순으로 정렬하는 문제입니다. 글자는 알파벳 소문자와 숫자로만 이루어져 있습니다. 숫자의 앞에 0이 있는 경우에는 생략할 수 있습니다. (예: 01a2b34 -> 1, 2, 34)

• 입력: 첫째 줄에 종이의 줄 수 N (1 ≤ N ≤ 100)이 주어집니다. 둘째 줄부터 N개의 줄에 걸쳐 각 줄에 글자가 주어집니다. (각 줄의 길이는 최대 100)
• 출력: 찾은 숫자를 한 줄에 하나씩 오름차순으로 출력합니다.

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

풀이 1: StringBuilder 활용

문자열을 한 글자씩 순회하며 숫자인 경우 StringBuilder에 담고, 알파벳을 만나면 처리하는 방식입니다. 숫자 앞에 붙은 0을 제거하기 위해 deleteCharAt(0)을 사용하였습니다. 숫자의 길이가 매우 길어질 수 있으므로 String 형태로 유지하며 커스텀 정렬을 수행합니다.

다만, StringBuilder의 첫 번째 인덱스(deleteCharAt(0))를 삭제하게 되면 내부 배열의 모든 요소들을 한 칸씩 앞으로 당겨야 하므로 삭제가 일어날 때마다 오버헤드가 발생할 수 있습니다.

코드 1

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

public class Main {
    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());

       List<String> list = new ArrayList<>();
       while (n-- > 0) {
          String s = br.readLine();
          StringBuilder sb = new StringBuilder();
          
          for (char c : s.toCharArray()) {
             if (c >= '0' && c <= '9') {
                sb.append(c);
             } else if (sb.length() > 0) {
                // 맨 앞의 0 제거
                while (sb.length() > 0 && sb.charAt(0) == '0') {
                   sb.deleteCharAt(0);
                }

                if (sb.length() == 0)
                   list.add("0");
                else
                   list.add(sb.toString());
                sb.setLength(0);
             }
          }

          // 문자열 끝이 숫자로 끝난 경우의 나머지 처리
          if (sb.length() > 0) {
             while (sb.length() > 0 && sb.charAt(0) == '0') {
                sb.deleteCharAt(0);
             }

             if (sb.length() == 0)
                list.add("0");
             else
                list.add(sb.toString());
          }
       }

       // 숫자의 길이가 길 수 있으므로 문자열 기반의 커스텀 정렬 수행
       Collections.sort(list, (s1, s2) -> {
          if (s1.length() == s2.length()) {
             return s1.compareTo(s2);
          }
          return s1.length() - s2.length();
       });

       for (String s : list) {
          bw.write(s + "\n");
       }

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

풀이 2: 인덱스 상태 기록 및 슬라이싱

deleteCharAt(0)으로 인한 배열 이동(Shift) 오버헤드를 막기 위해 **인덱스 슬라이싱(substring)**을 활용한 방식입니다. 반복문 내부에서 인덱스를 강제로 조작하지 않고 상태 변수(start)를 사용하여 안정적으로 구현했습니다.

1. 상태 기록: 문자열을 순회하며 숫자를 만나면 해당 시작 인덱스(start)를 기록해 둡니다.
2. 일괄 처리: 알파벳을 만나거나 문자열의 끝(i == len)에 도달했을 때, 기록된 start가 있다면 숫자 구간이 끝난 것이므로 문자열 슬라이싱을 수행합니다.
3. 0 건너뛰기: 삭제 연산을 하는 대신, 시작 인덱스(nonZeroIdx)를 뒤로 이동시키며 불필요한 0을 건너뛴 후 s.substring(nonZeroIdx, i)로 한 번에 잘라냅니다.

코드 2

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

public class Main {
    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());
       List<String> list = new ArrayList<>();

       while (n-- > 0) {
          String s = br.readLine();
          int len = s.length();
          
          int start = -1; // 숫자가 시작되는 인덱스 저장
          
          // 문자열의 끝부분 처리를 위해 조건식을 i <= len 으로 설정
          for (int i = 0; i <= len; i++) {
             // 문자열 끝에 도달했거나 숫자가 아닌(알파벳인) 경우
             if (i == len || (s.charAt(i) < '0' || s.charAt(i) > '9')) {
                // 이전에 모아둔 숫자가 있다면 처리
                if (start != -1) {
                   int nonZeroIdx = start;
                   
                   // 맨 앞의 0(Leading Zeros) 건너뛰기
                   // 숫자 전체가 0인 경우를 위해 마지막 인덱스(i - 1)는 남겨둠
                   while (nonZeroIdx < i - 1 && s.charAt(nonZeroIdx) == '0') {
                      nonZeroIdx++;
                   }
                   
                   // 유효한 숫자 부분만 리스트에 추가
                   list.add(s.substring(nonZeroIdx, i));
                   start = -1; // 다음 숫자를 찾기 위해 상태 초기화
                }
             } else {
                // 숫자인 경우 처음 시작점만 기록
                if (start == -1) {
                   start = i;
                }
             }
          }
       }

       // 숫자의 길이가 길 수 있으므로 문자열 기반의 커스텀 정렬 수행
       Collections.sort(list, (s1, s2) -> {
          if (s1.length() == s2.length()) {
             return s1.compareTo(s2);
          }
          return s1.length() - s2.length();
       });

       for (String s : list) {
          bw.write(s + "\n");
       }

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

알고리즘 분류

문자열 처리 (String), 정렬 (Sorting)