백준 알고리즘 1431 시리얼 번호

오늘은 이화여대 컴퓨터공학과 졸업 요건인 EPPER 경진대회를 보고왔습니다! 2시간 반동안 10문제를 풀었어야 했는데, 빡 집중하다가 다시 알고리즘 스터디 과제를 푸려니 어질ㄹ...

그래도 나름의 노하우가 쌓여서 오늘은 그 내용을 정리하려 합니다.

 

오늘 기록하고 싶은점은 먼저

 

1. 객체 Collections.sort()

기본적으로 Collections.sort() 메소드를 사용하면, 주어진 List가 오름차순으로 정렬이 됩니다.

 

저 같은 경우는 알고리즘 문제여도 새로운 객체 클래스를 정의하고, 그 객체안에 값을 넣어서 문제를 해결하는 경우가 많은데, 이때 객체의 특정 멤버값을 sort하고 싶을 때 어떻게해야하나 방법을 찾아보았습니다.

 

class Item implements Comparable<Item> {
    int size;

    @Override
    public int compareTo(Item o) {
        return this.size > o.size ? 1 : this.size < o.size ? -1 : 0;
    }
}

Item이라는 클래스를 선언하고, 그안에 있는 size라는 멤버변수를 이용해서 정렬이 하고싶다면 위와 같이 사용하면 됩니다.

 

Compareable<T> 인터페이스를 이용하고 그 인터페이스의 compareTo(T t) 메소드를 오버라이드 합니다.

이 메소드 안에서 return 되는 값에 따라 Collections.sort()가 이루어집니다.

 

[오름차순 정렬시]

인자로 전달된 obj가 작다면 1 반환

인자로 전달된 obj가 크다면 -1 반환

인자로 전달된 obj와 같다면 0을 반환

 

[내림차순 정렬시]

인자로 전달된 obj가 작다면 -1 반환

인자로 전달된 obj가 크다면 1 반환

인자로 전달된 obj와 같다면 0을 반환

 

2. 자리수 합 구할 때 주의할 점

원래 제가 자리수 합과 관련해서 구현한 코드는

    private int parsing(String str) {
        try {
            int number = Integer.parseInt(str);
            return number;
        } catch (NumberFormatException e) {
            return 0;
        }
    }

    private int findNumber(String str) {
        String replace = str.replaceAll("\\D", "");
        int num = parsing(replace);

        int sum = 0;
        while (num != 0) {
            sum += num % 10;
            num = num / 10;
        }
        return sum;
    }

String 클래스의 replaceAll을 사용해서 문자열에서 정수인 것들만 남게하고, 이들을 10단위로 나누어서 합을 구하는 방식으로 구현했습니다. 이때 replaceAll로 인해 모두 문자로만 이루어진 문자열 같은 경우엔, ""이 되므로 NumberFormatException이 나오니 이에 대한 return 값도 주려고 parsing 메소드안에 NumberFormatException도 넣었구요.

 

근데 계속 백준에서 틀렸습니다 가 뜨길래 엄청 화나서 왜그러지 왜그러지 하고 계속 생각하다가

입력값 조건에 시리얼 번호를 50자리 입력을 할 수 있다했는데 생각해보니 Integer로 변환을 하면 10자리 까지만 되더라구요!!!

 

하ㅏ... 그래서 앞으로 input 자리수를 잘 확인하자라는 교훈을 얻게 되었습니다.

 

그래서 아래와 같이 char의 ASCII 코드값을 한자리 한자리 비교하는 방식으로 리팩토링 하였습니다.

 

 

 

  private int findNumber(String str) {
        int sum = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                sum += str.charAt(i) - '0';
            }
        }
        return sum;
    }

 

3. String.replaceAll(), String.replace() 차이점

각 자리수의 합을 구하려고, 제가 String 클래스의 replaceAll()을 사용했는데요, 이과정에서 String.repace()랑 조금 헷갈렸어서 공유합니다.

 

string.replaceAll(String regex, String replacement)

string에서 regex(정규식)에 해당하는 문자열들을 replacement로 지정한 문자열로 바꿉니다.

 

string.replace(String target, String replacement)

한글에서 모두바꾸기, IDLE에서 ctrl+R 했을 경우 문자열에 해당하는걸 바꿀 수 있는 것처럼, 
target에 해당하는 문자열 자체를 replacement로 지정한 문자열로 바꿉니다.

 

따라서 아래와 같이 안녕1234 라는 문자열을 안녕으로 바꾸고 싶다면

replaceAll을 사용하면 정수에 해당하는 정규식을 써야하고

repace를 사용하면 1234 문자열 자체를 적어주어야 합니다.

String str = "안녕1234";

String replace = str.replace("1234", "");
String replaceAll = str.replaceAll("\\d", "");

System.out.println(replace);
System.out.println(replaceAll);

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

1026번: 보물

위에 말한 Comparable 인터페이스를 기본으로 저는 이번 문제인 1431 번의 조건을 해결했습니다.

1) 먼저 String의 size를 비교할 것

2) 이후 String안에 들어있는 정수들의 합을 비교할 것

3) 마지막으로 기존의 String 사전식 정렬을 사용할 것

 

그래서 1번조건에 따라 size를 먼저 비교하고

두 객체가 같을 경우에는 2번조건에 따라 number를 비교하고

그래도 1번, 2번 조건모두가 같을 경우에는 그냥 String 정렬을 따르기 위해 기존의 CompareTo() 메소드를 가져왔습니다.

 

https://github.com/mjung1798/algorithm_Java

mjung1798/algorithm_JAVA

package com.jyami;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main_1431 {
    public static void main(String args[]) {

        String str = "안녕1234";
        String replace = str.replace("1234", "");

        String replaceAll = str.replaceAll("\\d", "");

        System.out.println(replace);
        System.out.println(replaceAll);

        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();

        List<Item> list = new ArrayList<>();
        for (int i = 0; i < num; i++) {
            list.add(new Item(sc.next()));
        }

        Collections.sort(list);

        for (Item item : list) {
            System.out.println(item.text);
        }

    }
}


class Item implements Comparable<Item> {
    int size;
    String text;
    int number;

    public Item(String text) {
        this.text = text;
        this.size = text.length();
        this.number = findNumber(text);
    }

    private int findNumber(String str) {
        int sum = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) >= '0' && str.charAt(i) <= '9') {
                sum += str.charAt(i) - '0';
            }
        }
        return sum;
    }

    @Override
    public int compareTo(Item o) {
        return this.size > o.size ? 1 : this.size < o.size ? -1 :
                this.number > o.number ? 1 : this.number < o.number ? -1 :
                        this.text.compareTo(o.text);
    }
}