[Project Euler] Problem 022

<문제>

여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일 names.txt 이 있습니다 (우클릭해서 다운로드 받으세요).
이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다.

• 먼저 모든 이름을 알파벳 순으로 정렬합니다.
• 각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 수(A=1, B=2, ..., Z=26)를 모두 더합니다.
• 여기에 이 이름의 순번을 곱합니다.

예를 들어 "COLIN"의 경우, 알파벳에 해당하는 수는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다.

names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까?

 

 

 

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class Problem022 {
    public static void main(String[] args) {
        System.out.print(run());
    }
    
    public static String run() {
        File file = new File("names.txt");
        int seq = 0, result = 0;
        List<String> list = new ArrayList<String>(0);
        try {
            BufferedReader br = new BufferedReader(new FileReader(file));
            
            String s = null;
            while((s = br.readLine()) != null) {
                list.add(s.substring(s.indexOf('\"') + 1, s.lastIndexOf('\"')));
           } br.close();
 
            String[] arr = new String[list.size()];
            for(int i = 0; i < list.size(); arr[i] = list.get(i++));
            Arrays.sort(arr);
 
            for(int i = 0; i < arr.length; i++) {
                int sum = 0;
                for(int j = 0; j < arr[i].length(); j++) {
                    sum += (arr[i].charAt(j) - 'A' + 1);
                }
                
                result += (++seq*sum);
            }
            
        } catch (Exception e) {
            e.printStackTrace();
        }
        
        return Integer.toString(result);
    }
}

 

names.txt에는 5163개의 이름이 단 하나의 개행도 없이 한 줄에 써져 있다. 세상에..

사실 이 부분이 어렵다. 개행이 없기 때문에 한 줄로 읽을 수도 없고, 문자열이 너무 길어서 읽어온 다음 토큰화하기도 여의치 않다(파이썬은 될 지도 모르겠다).

notepad++로 names.txt에서 콤마(,)를 개행(\r\n)으로 바꾼 후에 풀었다.

 

15행 ~ 16행:

5163개의 이름에 매겨질 순번 변수, 결과값이 저장될 변수, 이름 리스트 선언.

 

18행:

원래는 FileReader(file) 대신 InputStreamReader(new FileInputStream(file), ENCODING)으로 인코딩을 지정해주는 편인데, 지금은 그런 부분이 중요한 게 아니라 그냥 전자의 방법으로 했다.

 

22행:

현재 파일에는 이름들이

"이름1"

"이름2"

...

"이름n"

의 형태로 저장되어 있기 때문에 큰 따옴표를 잘라낸 문자열을 리스트에 저장한다.

 

25 ~ 27행:

이 문제는 크게 세 부분으로 나눌 수 있다.

① 이름 데이터 정렬

② 이름 별로 알파벳에 대응하는 숫자 값 합산

③ ②에서 합산한 값에 이름의 순번 값을 곱한 후 합산

 

여기서는 ①을 수행한다.

리스트의 문자열들을 배열로 옮긴 후  Arrays.sort() 로 정렬한다. List 인터페이스에도 정렬 메소드가 있지만 그러러면 비교자까지 선언해줘야 돼서 그냥 배열로 옮겼다. 그리고 어차피 List의 정렬 메소드도 내부적으로는 배열로 옮겨서 정렬하기 때문에 굳이 쓸 필요성을 못 느꼈다.

그리고 배열로 옮기는 것보다는 정렬이 목적이기 때문에 깊은 복제(객체까지 복제)가 아닌 얕은 복제(참조만 복제)의 형태로 옮겼다.

 

29 ~ 33행:

여기서는 ②을 수행한다.

배열에서 문자열을 하나 읽어온 후 문자열에서 각 알파벳에 대응하는 값 sum에 합산한다.

'A' = 1, 'B' = 2, 'C' = 3, ..., 'Z' = 26에 대응시키려면 알파벳에서 'A'를 뺀 후 1을 더하면 된다.

 

35행:

여기서는 ③을 수행한다.

앞에서 합산한 값(sum)에 순번(seq)를 곱해 result에 더한다. seq는 0으로 초기화한 후 여기서 선위 증가 연산자로 1부터 차례대로 순번이 매겨지게 했다.

 

42행:

결과 값을 문자열 형태로 반환한다.

 

 

 

처음에는 notepad++에서 파일 내용을 수정한 후 풀었는데, 풀고 보니 안 그래도 되겠다 싶어서 다시 풀었다.

 

import java.io.File;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
public class Problem022 {
    public static void main(String[] args) {
        System.out.print(run());
    }
    
    public static String run() {
        File file = new File("names.txt");
        int seq = 0, result = 0;
        List<String> list = new ArrayList<String>(0);
        try {
            FileReader fr = new FileReader(file);
            
            int b = -1;
            StringBuilder sb = new StringBuilder();
            while((b = fr.read()) != -1) {
                if(('A' <= b) && (b <= 'Z')) {
                    sb.append((char) b);
                } else if(b == ((int)',')) {
                    list.add(sb.toString());
                    sb = new StringBuilder();
                }
            } fr.close(); list.add(sb.toString()); //The last string doesn't contain a comma
            
            String[] arr = new String[list.size()];
            for(int i = 0; i < list.size(); arr[i] = list.get(i++));
            Arrays.sort(arr);
 
            for(int i = 0; i < arr.length; i++) {
                int sum = 0;
                for(int j = 0; j < arr[i].length(); j++) {
                    sum += (arr[i].charAt(j) - 'A' + 1);
                }
                
                result += (++seq*sum);
            }
            
        } catch (Exception e) {
            e.printStackTrace();
        }
        
        return Integer.toString(result);
    }
}

달라진 것은 파일에서 읽어오는 부분 뿐이고, 30행부터는 결과를 구하는 부분이므로 앞의 코드와 동일하다.

 

19행:

~Writer 클래스의 read() 메소드는 파일에서 문자 하나를 읽어온 후 문자의 유니코드 값을 int 형으로 반환한다.

따라서 문자 코드 값을 저장할 변수는 int 형으로 선언한다. 

 

20행:

문자를 하나씩 추가해 문자열을 형성하기 위해 StringBuilder 변수를 선언한다.

 

22 ~ 27행:

각 이름은 큰 따옴표로 둘러싸여 있고, 콤마로 구분되어 있다.

따라서 문자를 하나씩 읽으면서 알파벳일 경우 StringBuilder에 추가하고, 콤마일 경우 이름 하나가 끝났음을 의미하므로 현재 StringBuilder로 만들어진 문자열을 리스트에 추가하고 새로운 StringBuilder를 만든다.

큰 따옴표는 큰 따옴표에 대한 조건문을 생략함으로써 무시한다.

 

28행:

마지막 이름은 뒤에 콤마가 없다. StringBuilder에는 마지막 이름이 저장되어 있지만 리스트에는 추가되지 않은 상태로 반복문을 탈출하게 되는 것이다. 따라서 마지막 이름을 list에 추가해준다.

 

그 다음부터는 위와 동일하므로 생략.