[PS] 백준1339 : 단어 수학(Java)

문제

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

 

---

풀이

자료구조를 활용한 그리디 풀이

첫번째 접근법 (오답)

다음과 같은 우선순위를 통해서 알파벳에 대한 값을 메겼습니다.

• 자리수가 높은 알파벳 우선
  • 같은 자리수라면 개수에 따라서

반례

2
AB
BB
----
wrong : 186
ans : 188

해당 접근으로는 바로 뒷자리수에 나오는 알파벳에 따라 잘못된 결과가 측정될 수 있었습니다.

 

두번째 접근법

그렇다면 위와 같은 반례에 대해서 어떻게 풀이를 해야할까요?

처음에는 단순히 바로 뒤에 나오는 각각의 자리수에 대해서 알파벳의 개수를 측정하고, 비교하려 했는데요. 이렇게 될 경우 로직이 굉장히 복잡해지고 어떻게 코드를 작성해야할지 모르겠더라구요.

코드를 아예 지우고 다시 생각을 해본 결과 다음과 같은 로직을 생각할 수 있었습니다.

 

입력으로 들어오는 알파벳에 대해 자리수만 고려하여 결과값을 기록하는 것으로 풀이를 할 수 있었습니다.

예를 들어, 위의 반례와 같은 입력이 들어온다면 각 알파벳을 1로 두고, 자리수에 해당하는 값을 누적합니다.

• AB → A*(10), B*(1)
• BB → B*(10, B*(1)

각 알파벳에 대한 최종 값은 A=10, B=12로 우선순위를 메길 수 있게 됩니다. 또한 자릿수, 개수에 대해 각각의 서로다른 가중치를 메길 수 있게 됩니다.

이후 우선순위 큐를 이용하여 각 최종값에 대해 해당하는 Value(9 ~ 1)를 곱한 값을 누적하면 정답을 구할 수 있습니다.

 

요약

첫 번째 입력 AB -> (A : 10), (B : 1)

두 번째 입력 BB -> (A : 10), (B : 12) //누적

결론적으로, B > A //(B*9) + (A*8)

 

---

소스코드

import java.io.*;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

//BOJ_1339
public class Main {
    static int res;
    static final int FIX = 10;  //자리수 계산 상수
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        Map<Character, Integer> cntForPos = new HashMap<>();

        int N = Integer.parseInt(br.readLine());

        for(int i=0; i<N; i++) {
            String input = br.readLine();
            int position = 0;
            for(int j=input.length()-1; j>=0; j--) {
                char idx = input.charAt(j);
                cntForPos.put(idx, cntForPos.getOrDefault(idx, 0) + (int) Math.pow(FIX, position++));
            }
        }

        PriorityQueue<Integer> pq = new PriorityQueue<>((o1, o2) -> {return o2 - o1;});
        for(int idx : cntForPos.values()) {
            if(idx == 0) continue;
            pq.offer(idx);
        }

        int value = 9;
        while(!pq.isEmpty()) {
            res += pq.poll() * value--;
        }

        System.out.println(res);
    }
}

 

---

정리

그리디 알고리즘의 경우 첫 접근을 잘못하면 미궁으로 빠져들어 시간을 자주 버리게 되었던 것 같습니다. 이렇기에 잘 풀 수 있는 방법이라면 접근을 잘 하는게 되겠죠.

 

이번 문제의 경우에도 각 자릿수만 신경쓰느라 뒤에 나오는 개수에 따라 값이 변동될 수 있다는 점을 간과하여 헛걸음을 많이 했습니다. 반례에 대해서 조금 생각해보고, 접근법에 대한 가정을 충분히 했다면 금방 풀 수 있었을거라 생각이 되네요.

 

다른 알고리즘들의 경우 최대한 많이 풀어보는게 도움이 되었지만, 그리디의 경우에는 문제에 대한 조건을 꼼꼼히 읽고, 접근법에 대한 반례를 생각하면서 푸는 습관을 가지는게 이번 풀이를 통해 중요하다고 생각이 되었던 것 같습니다.