백준 1339번 단어 수학 Java

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

문제

---

생각하기

---

• 그리디 문제이다.

• 10진법을 활용한 단어 정렬.

동작

val sortedByValue: List<Pair<Char, Int>> = mapList.sortedByDescending { (_, v) -> v }

Kotlin에서 _(언더스코어)는 “이 변수(또는 파라미터)는 사용하지 않는다” 라는 의미로, 보통 구조 분해(destructuring) 시에 특정 항목을 무시할 때 사용됩니다.

이 문제는 알파벳에 가중치를 계산해 순서에 맞도록 값을 구해 합을 계산하는 것 같지만,
10진법을 활용해야 한다.

val weight = Math.pow(10.0, (len - i - 1).toDouble()).toInt()

-1을 해줘야 하는 이유는 단순히 가중치 계산이 아닌, $10^0$을 계산해서 1의 자리를 표현하기 위해서이다.

-1을 하지 않으면 10이 되어 가장 오른쪽 글자가 1의 자리가 아니라 10의 자리가 되어버립니다.

[(A, 10000), (C, 1010), (D, 100), (G, 100), (E, 10), (B, 1), (F, 1)]
first : A, second : 10000, sum = 90000
first : C, second : 1010, sum = 8080
first : D, second : 100, sum = 700
first : G, second : 100, sum = 600
first : E, second : 10, sum = 50
first : B, second : 1, sum = 4
first : F, second : 1, sum = 3
99437

결국에 1010의 경우, 8080을 계산하게 된다.
합이 1000자리와 10의 자리에 8을 곱한 값이므로

합을 더한 값에 숫자를 대입해 계산한다고 생각하면 된다.

결과

코드

---

Java

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {

    // input
    private static BufferedReader br;

    // variables
    private static int N;
    private static HashMap<Character, Integer> map;

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        input();

        bw.write(solve());
        bw.close();
    } // End of main()

    private static String solve() {
        StringBuilder sb = new StringBuilder();

        List<Map.Entry<Character, Integer>> entryList = new ArrayList<>(map.entrySet());
        entryList.sort((o1, o2) -> o2.getValue() - o1.getValue());

        int sum = 0;
        int digit = 9;
        for (Map.Entry<Character, Integer> entry : entryList) {
            sum += entry.getValue() * digit;
            digit--;
        }

        sb.append(sum);
        return sb.toString();
    } // End of solve()

    private static void input() throws IOException {
        N = Integer.parseInt(br.readLine());

        map = new HashMap<>();
        for (int i = 0; i < N; i++) {
            String temp = br.readLine();
            int len = temp.length();

            for (int j = 0; j < len; j++) {
                char ch = temp.charAt(j);

                int placeValue = (int) Math.pow(10, len - j - 1);
                map.put(ch, map.getOrDefault(ch, 0) + placeValue);
            }
        }
    } // End of input()
} // End of Main class

Kotlin

import java.io.File
import java.util.*

// input
private var br = System.`in`.bufferedReader()

// variables
private var N = 0
private lateinit var map: HashMap<Char, Int>

fun main() {
    val bw = System.out.bufferedWriter()

    input()

    bw.write(solve())
    bw.close()
} // End of main()

private fun solve(): String {
    val sb = StringBuilder()

    val mapList = map.toList()
    val sortedByValue: List<Pair<Char, Int>> = mapList.sortedByDescending { (_, v) -> v }
    var digit = 9
    var sum = 0

    sortedByValue.forEach {
        sum += it.second * digit
        digit--
    }

    sb.append(sum)
    return sb.toString()
} // End of solve()

private fun input() {
    N = br.readLine().toInt()
    map = HashMap<Char, Int>()

    repeat(N) {
        val temp = br.readLine()

        val len = temp.length
        for (i in 0 until len) {
            val ch = temp[i]
            val weight = Math.pow(10.0, (len - i - 1).toDouble()).toInt()
            map.put(ch, map.getOrDefault(ch, 0) + weight)
        }
    }
} // End of input()