[Code Jam] 2016 Round1B A.Getting the Digits

문제 링크

문제를 이해하는데는 어렵지 않으나 푸는데 약간의 지장이 있었습니다.

그래도 round1 치곤 쉬운문제 아닐까 싶었지만

larget-set은 처음에 풀지 못하였습니다.

다행히도 조건 하나를 추가해서 해결할 수 있었습니다.

문제에서 INPUT으로 주어지는 문자열을 잘 조합하여 오름차순의 숫자를 완성하는겁니다. 

OZONETOWER라면 ZERO ONE TWO가 되겠고 이를 다시 012로 출력하면 완성입니다.

small-set을 풀때는 그래프와 동적계획법을 이용하여 풀었으나

large-set은 실패하였습니다. 후의 방법으로 해결하고 나니 닭잡는데 소잡는 칼을 쓴 겪이였습니다.

역시 해결방법은 의외로 간단하고 짧게 나오는 법인가 봅니다.

---

main은 읽는게 전부입니다.

다만 선처리로 문자열의 각 영문자가 몇개 있는지를 letters에 더하고 있습니다.

이때 vector의 크기를 'Z'+1로 하였습니다.

괜히 28개만 지정한 다음 후에 변환하고 또 인덱스 처리를 위해 1을 더하고 빼는 귀찮음을 생략하기 위함입니다.

해결방법 역시 어렵지 않습니다. 각 문자열의 root가 있는지 검사 후 있으면 문자열의 문자가 letters에 몇개씩 있는지 검사합니다.

또 그때마다 갯수의 최솟값을 구합니다(58줄)

이렇게 함으로써 str에 몇개의 숫자를 더하게 될지를 결정하게 됩니다.

또 61번줄에서 letters에 min을 빼는것 역시 해주어야 합니다.

중요한건 전역변수로 order를 주목해야합니다.

50번줄을 보면 nubmer[order[i][0]이 있습니다.

order배열의 순서대로 numbers 각 문자열에서 첫 글자만 가져오겠다는것이죠.

왜 순서대로 안하고 이렇게 하는걸까요?

이유는 먼저 희귀한 문자가 있는 문자열부터 세어 나가는것입니다.

FERINOUN이라는 문자열을 보겠습니다.

ONE을 먼저 샐 수도 있습니다. 하지만 그러면 완성할 수가 없죠.

반면에 NINE FOUR로 샌다면 성공입니다.

이처럼 남김없이 새기 위해선 희귀한 문자가 있는 문자열부터 새야 한다는 전제조건을

달고 시작 해야 하는것 입니다. 따라서 Z(0), W(2) U(4) X(6) 이런식으로 먼저 제외해나가면서

안전하게 새는것 입니다. 

배열인덱스를 통해 계속 접근해나가다 보니 읽는데 좀 불편하지만 알고리즘 자체는 어렵지 않다고 봅니다.