백준 12400번 Speaking in Tongues :: 마이구미

이번 문제는 백준 알고리즘 12400번 "Speaking in Tongues" 를 다뤄본다.

2012 Google Code Jam 에서 출제된 문제이다.

영어로 된 문제이기 때문에 해석이 필요하다.

해석만 가능하다면 굉장히 쉬운 문제이기 때문에 두려울 게 없다.

문제를 보자. (번역과 함께 보여주겠다)

We have come with up the best possible language here at Google, called Googlerese.

- 구글은 Googlerese라고 불리는 최고의 언어를 제시한다.

To translate text into Googlerese, we take any message and replace each English letter with another English letter.

- Googlerese를 통해 텍스트를 번역하기 위해 우리는 어느 메시지를 받아 각각의 영문자를 다른 영문자로 대체한다.

This mapping is one-to-one and onto, which means that the same input letter always gets replaced with the same output letter, different input letters always get replaced with the different output letters.

- 이 맵핑은 1:1 방식으로 같은 입력 글자는 항상 같은 출력 글자로 대체되고, 다른 입력 글자는 항상 다른 출력 글자로 대체된다.

A letter may be replaced by itself. Space are left as-is.

- 글자는 그 자체로 대체될 수도 있다. 공백은 그대로 유지된다.

For example(and here is a hint!), our awesome translation algorithm includes the following three mappings: 

'a' -> 'y', 'o' -> 'e', and 'z' -> 'q'.

- 예를 들어(여기는 힌트), 우리는 굉장한 번역 알고리즘은 다음의 세가지 맵핑을 포함한다.

'a' -> 'y', 'o' -> 'e', and 'z' -> 'q'.

This means that 'a zoo' will become 'y qee'.

- 이 의미는 'a zoo'는 'y qee'로 되는 것이다.

Googlerese is based on the best possible replacement mapping, and we will naver change it.

- Googlerese은 최고의 대체 맵핑을 기반으로 하고, 절대 변경하지 않는다.

It will always be the same. In every test case.

- 모든 테스트 케이스에서 대체 맵핑은 항상 같다.

We will not tell you the rest of mapping because that would make the problem too easy, but there are a few examples below that may help.

- 우리는 문제가 너무 쉽기 때문에 당신에게 나머지 맵핑을 설명하지 않을 것이다. 그러나 도움이 될 만한 예제들이 아래에 있다.

문제를 보다시피, 각 글자에 대한 대체될 글자들이 존재한다.

그것만 찾는다면 문제를 쉽게 해결할 수 있다.

문제에서는 세가지만 알려주었다. ('a' -> 'y', 'o' -> 'e', and 'z' -> 'q')

또한 주어지는 예제를 통해 도움을 얻으라고 말해주고 있다.

노가다를 해서 각 대체 글자들을 찾으면 된다.

하지만 노가다 문제는 풀었다는 느낌을 못 받을 수 있다.

그렇기에 일일이 노가다로 찾지 않고, 코드를 짜서 찾아보자.

String Googlerese = "ejp mysljylc kd kxveddknmc re jsicpdrysi rbcpc ypc rtcsra dkh wyfrepkym veddknkmkrkcd de kr kd eoya kw aej tysr re ujdr lkgc jv";
String string = "our language is impossible to understandthere are twenty six factorial possibilitiesso it is okay if you want to just giveup";

위와 같이 예제로 주어진 입력과 출력을 그대로 복사하여 문자열을 만들어보자.

그 후 공백은 신경쓸 필요가 없기 때문에 공백을 제거하자.

Googlerese = Googlerese.replaceAll(" ", "");
string = string.replaceAll(" ", "");

그 후 두 문자열을 비교하면서 대체 글자에 대한 배열을 만들어 주면 된다.

char[] ans = new char[26];

for(int i=0;i<Googlerese.length();i++) {
    ans[Googlerese.charAt(i) - 'a'] = string.charAt(i);
}

그 결과, ans 배열에는 대체 글자들이 존재하게 된다.

(ans[0]은 'a'를 의미한다. ans[0]의 값은 'a' 가 대체될 글자가 존재한다)

* q, z는 예제에서 주어지지 않았기 때문에 따로 넣어줘야한다.

이렇게 구함으로써, 일일이 노트에 적으면서 대체 글자를 찾을 필요가 없어진다.

노가다보다는 조금 더 생각하여 문제를 해결하자.

우리는 개발자이기 때문이다.

전체 소스는 아래 Github URL을 참고하자.

백준 알고리즘 12400번 Speaking in Tongues 전체 소스 

https://github.com/hotehrud/acmicpc/blob/master/English/12400.java