백준 25329번 : 학생별 통화 요금 계산 (맵 활용)

---

이번 문제는 학생들이 통화한 n개의 통화 기록이 주어질 때, 각 학생의 통화 요금의 합산을 내림차순 정렬 후 출력하는 문제이다.

통화 시간 100분은 기본 제공으로 기본 요금인 10원이며, 이후 50분 마다 3원씩 추가 요금이 발생한다.

HashMap을 활용한 입력 값 핸들링, TreeMap을 활용한 정렬이 주요 포인트이다.

가장 먼저 입력된 값에 대해 문제를 풀기 쉽게 핸들링 해야한다.

7
00:10 aaa
00:30 aaa
01:15 bbb
01:00 ccc
01:00 bbb
02:10 aaa
03:10 ccc

처음 통화 기록의 개수인 n이 입력되고 이후로 통화 기록이 입력된다.

문제에서 단위가 “분”이었기 때문에 이를 표현하기 쉽게 입력 받은 각 시간을 “분”으로 처리했다.

// 기본 100분, 기본 10원 / 단위 50분, 단위 3원
// 가공하기 쉽게 HashMap을 활용하여 입력
for (int i = 0; i < n; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int[] arr = Arrays.stream(st.nextToken().split(":")).mapToInt(Integer::parseInt).toArray();
    String name = st.nextToken();
    int time = ( arr[0] * 60 ) + arr[1];

    map.put(name, map.getOrDefault(name, 0) + time);
}

해쉬맵은 키 String, 밸류 Integer로 각 학생을 기준으로 자료를 담아내었다.

위의 반복문에서 StringTokenizer를 활용해 입력된 “시간” 단위의 통화시간을 “:”을 기준으로 분리하여 배열에 담아주었다.

이를 “분”으로 치환하기 위해 “시간”에는 60씩 곱해주었고, 남아있는 “분”을 합했다.

이를 통해 각 학생의 통화시간을 “분”으로 표현한 것이다.

이렇게 치환된 “분”을 순서가 보장되지 않지만 중복을 허용하지 않는 HashMap에 우선 담아주었고, 이제 map에는 각 학생을 기준으로 해당 학생의 통화시간이 담겨있게 된다.

다음으로는 정렬과 정답을 위해 학생과 요금을 TreeMap에 옮겨 담는 작업을 진행했다.

// TreeMap 활용 정렬
TreeMap<String, Integer> result = new TreeMap<>();
for (String s : map.keySet()) {
    int charge = (int) Math.ceil((double) (map.get(s) - 100) / 50) * 3; // 요금 합산
if (charge < 0) { // 0 보다 작은 경우 -> 기본 요금
    result.put(s, 10);
} else { // 0 보다 큰 경우 -> 추가 요금
    result.put(s, 10 + (charge));
}
}

HashMap과 마찬가지로 키 String, 밸류 Integer를 참조하는 TreeMap을 선언했다.

이후 반복문을 실행해 map의 key를 받아오고 charge라는 변수에 전체 요금 합산을 할당했다.

만약 이 charge가 0이면 기본 요금으로 충당된다는 의미이고, 반대인 경우 추가 요금이 발생했다는 의미이다.

그래서 charge가 0보다 작은 경우 10으로 요금을 고정하고 반대의 경우 추가 요금을 합산한다.

마지막으로 “내림차순”으로 출력 값을 맞추기 위해 stream을 활용했다.

// treeMap의 값을 기준으로 내림차순 정렬 후 출력
result.entrySet().stream()
.sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
  .forEach(entry -> System.out.println(entry.getKey() + " " + entry.getValue()));

result 내의 키와 밸류를 합친 entrySet을 스트림을 활용하여 값을 기준으로 내림차순 정렬하고 forEach 함수를 통해 문제에서 요구한 출력 값에 맞추어 출력했다.

여기서 아쉬운 점은 중간에

int charge = (int) Math.ceil((double) (map.get(s) - 100) / 50) * 3; // 요금 합산

이러한 요금 합산 로직의 경우, total이라는 변수를 활용해 10으로 초기화하여 기본 요금으로 시작하는 방법도 있다는 것이다.

int totalCharge = 10; // 기본 요금으로 시작
int extraTime = nameToTimeMap.get(name) - 100;
if (extraTime > 0) {
    totalCharge += Math.ceil((double) extraTime / 50) * 3;
}

앞선 풀이와 로직이 크게 다르진 않지만 기본 요금인 10을 미리 할당해주고, 시간에서 100을 차감하고 시작하는 방식이다.

조건 분기도 0보다 큰 경우만 계산하면 되기 때문에 메모리를 적게 사용할 것이다.

또 아쉬운 점이 하나 더 있는데, TreeMap의 자동정렬의 경우 오름차순으로만 정렬이 되기 때문에 내림차순으로 정렬해야하는 문제 특성 상 반드시 TreeMap을 활용해야하는 것은 아니다.

결국 마지막에 와서 Stream으로 “값을 기준으로 내림차순 정렬”을 하고 있기 때문에 TreeMap일 필요가 없다는 뜻이다.

물론 그래봤자 결국 키와 밸류 쌍으로 핸들링 해야하기 때문에 HashMap이 두 번 초기화되어야 하겠지만.

전체 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

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());

        HashMap<String, Integer> map = new HashMap<>();

        // 기본 100분, 기본 10원 / 단위 50분, 단위 3원
        // 가공하기 쉽게 HashMap을 활용하여 입력
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int[] arr = Arrays.stream(st.nextToken().split(":")).mapToInt(Integer::parseInt).toArray();
            String name = st.nextToken();
            int time = ( arr[0] * 60 ) + arr[1];

            map.put(name, map.getOrDefault(name, 0) + time);
        }

        // TreeMap 활용 정렬
        TreeMap<String, Integer> result = new TreeMap<>();
        for (String s : map.keySet()) {
            int charge = (int) Math.ceil((double) (map.get(s) - 100) / 50) * 3; // 요금 합산
            if (charge < 0) { // 0 보다 작은 경우 -> 기본 요금
                result.put(s, 10);
            } else { // 0 보다 큰 경우 -> 추가 요금
                result.put(s, 10 + (charge));
            }
        }

        // treeMap의 값을 기준으로 내림차순 정렬 후 출력
        result.entrySet().stream()
                .sorted(Map.Entry.<String, Integer>comparingByValue().reversed())
                .forEach(entry -> System.out.println(entry.getKey() + " " + entry.getValue()));
    }
}

---

요즘 알고리즘 풀이 블로깅을 안하다가 오랜만에 했다.

3월 들어오고서 부터 풀던 “정렬” 문제들은 왠만하면 실버 정도 문제여서 크게 어렵거나 기록할게 없었기 때문이기도 하다.

그런데 아직까지 Map 인터페이스를 구현한 자료구조들은 자주 사용하지 않았고, 사용법이나 함수도 전부 알고 있진 않기에 이번 기회에 정리해보았다.

또한 중복을 허용하지 않는 Map 자료구조 특성을 사용해서

map.put(name, map.getOrDefault(name, 0) + time)

와 같이 같은 키를 가진 값을 합산하는 함수가 매번 헷갈리는 것도 이번에 잡고간다.