conflux
자유롭게 흘러가는 곳으로
만남.
가까와짐.
일체감.
서로의 마음 속에 들어갈 수 있는 사람은 일생에 몇 명이나 될까.
우린 누구를 만나도록 되어 있는 것일까.
바람 부는 푸르른 산중턱에 앉아
저 멀리 마을에 돌아가는 물레방아, 흐르는 강물 위 좁은 나무다리를 건너는 아이들,
해질녘 바알갛게 물든 집들과 거리
가고 싶다. 보고 싶다.
가스펠 중에도 좋은 곡들이 많습니다. 이게 벌써 언제적 곡인가.
단어의 글자수는 3이고, 사전의 표제어는 다음과 같이 5개 있는 경우를 예로 들겠습니다.
사전에 몇 번 등장하는지 찾아야 할 대상 단어들 (이하 '문제단어'로 호칭) 은 2개라고 하겠습니다.
[사전의 표제어들]
abd
aed
efw
oli
fse
[사전에 몇 번 나오는지 알아내야 하는 단어들 = 문제단어들]
uiw
a(bel)(irdxq)
이제 uiw 과 a(bel)(irdxq) 가 각각 사전의 표제어에 몇 번씩 일치되는지를 알아내면 끝입니다.
답은 다음 형식으로 출력하면 됩니다. (XXX, YYY는 각각 사전에 등장한 횟수)
case #1 : XXX
case #2 : YYY
1. 망하는 풀이
사람이 사전을 찾을 때와 같은 식으로 푸는 방법입니다.
- 문제단어 각각에 대해
- 사전의 표제어들 각각과 일치하는지 검사하여 일치하면 일치횟수를 1 증가시킴
- 일치횟수를 출력
먼저 case #1 (즉 단어 'uiw') 의 경우는 간단합니다.
문제단어 'uiw'가 사전의 첫번째 표제어 'abd'와 일치하는지 검사하면 일치하지 않으니까 그냥 넘어가고, 사전의 두번째 표제어 'aed'와 일치하는지 검사하여 또 일치하지 않으니 그냥 넘어가고, ..., 마지막 표제어 'fse'와도 일치하지 않으니 넘어가고, 더이상 사전에 표제어가 없으면 끝입니다.
한번도 일치하지 않았으니까 일치횟수는 0이군요.
여기까진 문제가 없습니다.
다음 case #2 ( 단어 a(bel)(irdxq) ) 의 경우는 이런 방식으로 하면 다음과 같이 하게 됩니다.
문제단어가 확정된 것이 아니라 a(bel)(irdxq) 와 같이 여러 단어가 될 가능성이 있으므로 이를 풀어 보면 다음과 같은 단어조합이 가능합니다.
abi
abr
abd
abx
abq
aei
aer
aed
aex
aeq
ali
alr
ald
alx
alq
1*3*5 = 15개의 조합이 나왔습니다. 문제단어 a(bel)(irdxq) 는 표현상으로는 1개의 단어처럼 보이지만 실제로는 15개의 단어가 될 가능성을 가지는 것입니다.
이제 다음 풀이 방법을 적용시켜 보자면
- 문제단어 각각에 대해
- 사전의 표제어들 각각과 일치하는지 검사하여 일치하면 일치횟수를 1 증가시킴
- 일치횟수를 출력
문제단어 각각에 대해 사전 표제어 각각과 일치하는지 검사해야 하는데, 앞에서 문제단어가 1개가 아니라 15개가 되어 버렸습니다.
따라서
- 15개의 문제단어 각각에 대해
- 사전의 5개의 표제어들 각각과 일치하는지 검사하여 일치하면 일치횟수를 1 증가시킴
- 일치횟수를 출력
과 같이 계산해야 하므로, case #1에서 1개의 문제단어에 대해 사전의 5개의 표제어와 일치검사시에는 1*5=5번의 계산만 수행하면 되었던 것에 비해서 이번에는 15*5=75번의 계산이 필요합니다.
75번의 계산을 수행하면 결과는 '2회 일치'라는 것을 알 수 있습니다.
이 정도 표제어 수와 이 정도 조합의 단어까지는, 사람의 눈으로 보면 바로 몇 개가 일치하는지 보이죠.
이 정도까진 그냥 하면 되지 않냐 할 수 있는데, 단어의 길이가 10이고 문제단어가 다음과 같은 경우를 생각해 봅시다.
(qweasdzxcv)(poiuytrewq)(afdgs)(eydhcn)o(ethi)(bnvn)(asdfghjklm)(yt)(ghfjdk)
10 * 10 * 5 * 6 * 1 * 4 * 4 * 10 * 2 * 6 = 5,760,000
문제단어 1개가 실제로는 오백 칠십 육만개의 단어조합을 나타냅니다.
조합을 만들 때 가능한 경우의 수는 곱하기로 늘어나기 때문에 걷잡을 수 없이 커집니다.
이런 문제단어가 1000개라면? 오십 칠억 육천만개의 단어조합이 되지요.
그리고 사전의 표제어가 1000개라면? 오십칠억육천만 * 1000 번의 계산이 필요합니다.
계산할 수는 있겠지만 시간이 얼마나 걸릴지 알 수 없습니다. 그래서 망하는 풀이입니다.
2. 진짜 풀이
우선 문제를 다시 정리해 보죠.
다시 사전의 표제어를 살펴보겠습니다.
abd
aed
efw
oli
fse
그리고 문제단어들입니다.
uiw
a(bel)(irdxq)
case#2 인 단어 'a(bel)(irdxq)' 의 경우 다음과 같은 문제단어조합이 나오고, 이 중에 표제어와 일치하는 것은 abd와 aed의 2 개입니다.
abi
abr
abd
abx
abq
aei
aer
aed
aex
aeq
ali
alr
ald
alx
alq
그럼 이번엔 이렇게 풀어보겠습니다.
- 사전의 각 표제어에 대해서
- 문제단어와 일치하는지 검사하여 일치하면 일치횟수를 1 증가시킴
case #1은 뻔하니까 case #2 에 대해 풀어봅시다.
1) 1번째 사전 표제어 'abd' 가 문제단어 'a(bel)(irdxq)' 와 일치하는지를 검사.
- 첫번째 글자는 'a'로 같으니까 OK
- 두번째 글자는 사전표제어 'b' 가 문제단어의 '두번째 글자로 가능한 글자들 (bel)' 에 포함되니까 OK
- 세번째 글자는 사전표제어 'd' 가 문제단어의 '세번째 글자로 가능한 글자들 (irdxq)' 에 포함되니까 OK
- 마지막 글자까지 모두 일치했으니까 일치횟수 1 증가
2) 2번째 사전 표제어 'aed' 가 문제단어 'a(bel)(irdxq)' 와 일치하는지를 검사.
- 풀이는 똑같으니 생략함. 마지막 글자까지 모두 일치하니까 일치횟수는 또 1 증가하여 2가 됨.
3) 3번째 사전 표제어 'efw'가 문제단어 'a(bel)(irdxq)' 와 일치하는지를 검사.
- 첫번째 글자가 'e'와 'a'로 서로 다르니까 FAIL
- 두번째 글자부터는 볼 필요 없음
4) 4번째 사전 표제어 'oli'가 ....
- 풀이 생략. FAIL
5) 5번째 사전 표제어 'fse'가 ...
- 풀이 생략. FAIL
이와 같이 계산하여, case#2의 단어는 모든 사전 표제어에 대해 2번 일치함을 구했습니다.
이 경우에는 단어의 글자수가 늘어나고, 사전의 표제어 수가 많아지고, 문제단어 수가 많아져도 조합을 만들지 않기 때문에 소요시간이 기하급수적으로 증가하지 않습니다.
즉 이 문제 풀이의 핵심은 '조합을 만들지 않는 것' 에 있습니다.
좀 더 구체적인 사항으로는, 각 과정에서 다음과 같은 계산을 할 때
[ 사전표제어의 두번째 글자인 'b'가 문제단어의 두번째 글자로 가능한 (bel) 에 포함되는지 검사 ]
어떤 방법으로 검사하느냐에 따라 속도 차이가 납니다.
예를 들어 글자 'a' 가 (guiwpzanbmxc) 에 포함되는지를 검사할 때, (guiwpzanbmxc) 의 각 글자에 대해 a와 일치하는지를 순차적으로 검사할 수도 있습니다.
- 'g'가 'a'와 같은지 검사하여 아니니까 그룹 안의 다음 글자 'u'로 넘어가고
- 'u'가 'a'와 같은지 검사하여 아니니까 그룹 안의 다음 글자 'i'로 넘어가고
- ...
- 'z'가 'a'와 같은지 검사하여 아니니까 그룹 안의 다음 글자 'a'로 넘어가고
- 'a'가 'a'와 같은지 검사하여 같으니까 이번 그룹에 대해서는 일치한다고 판단.
이렇게 검사하면, 괄호 안의 글자들 중 a의 위치에 따라 계산속도가 달라집니다. a가 처음에 나오면 바로 일치한다고 판단할 것이고, 맨 마지막에 나오면 그때까지 계산을 반복해야 합니다.
이렇게 하지 않으려면 (guiwpzanbmxc) 를 그냥 텍스트나 배열로 만들어서 순차적으로 비교하는 것이 아니라, 다음과 같이 hash ( = map ) 의 형태로 만들어 놓고
{ 'g' => 1, 'u' => 1, ... , 'c' => 1 }
이 hash가 'a'라는 key를 가지는지 아닌지를 판단하면 됩니다.
( 이때 value는 뭐든 상관없습니다. value를 찾는 것이 목적이 아니라 해당 key가 존재하는가만 이용합니다. )
hash는 내부적으로 key를 빨리 찾기 위한 최적화된 자료구조를 가지고 있기 때문에 순차적인 계산을 수행하지 않으며, 그룹 내의 글자수가 많아져도 빨리 찾을 수가 있습니다.
예를 들어 hash가 내부적으로 b*tree로 이루어져 있을 경우, (abcdefghijklmnopqrstuvwxyz) 라는 26개의 글자를 가지는 그룹의 각 글자를 hash의 key로 만든 hash 안에 'q'가 있는지 없는지를 찾는 경우
- 1번째 계산 : 2개로 분리된 그룹들 (13개 / 13개) 중 q가 속할 수 있는 그룹이 선택됨
- 2번째 계산 : q가 속할 가능성이 있는 그룹이 다시 2개로 분리 (6개 / 7개) 되어 이 중 다시 q가 속할 수 있는 그룹이 선택됨
- 3번째 계산 : 다시 2개로 분리 (3개 / 4개) 되어 이 중 q가 속할 수 있는 그룹이 선택됨
- 4번째 계산 : 다시 2개로 분리 (2개 / 2개) 되어 이 중 q가 속할 수 있는 그룹이 선택됨
- 5번째 계산 : 마지막으로 분리된 글자수 2개의 그룹에 q가 있는지 검사.
이와 같은 식으로 처리됩니다.
이 방법의 좋은 점은, 그룹 내의 글자수가 100개 증가해도 계산해야 하는 횟수가 100번 증가하는 게 아니라는 점이지요.
여튼 이런 생각을 프로그램으로 만들면 다음과 같이 됩니다. (사실 후딱 짜고 나서 정리한 거지만) 딱 100줄이네요.
변수의 scope를 따져서 reference를 서브루틴으로 넘기거나 이런 건 하지 않았습니다. 돌아가는 데 집중한 코드입니다.
#!/usr/bin/perl
use strict;
use warnings;
use FileHandle;
my $dataFileName = 'A-small-attempt0.in';
my @dic; # 사전
my @message; # 사전과 대조해볼 단어들, 즉 case 들
my @messageInDicCount; # 각 case 가 사전의 표제어들 중 몇 개와 일치하는지. 프로그램의 목표는 이것을 구하는 것.
my $wordLength; # 단어의 길이. 사전의 표제어이든 사전과 대조해볼 단어든 모든 단어의 길이는 일정함.
my $dicEntryTotalNo; # 사전에 들어 있는 표제어의 수
my $messageTotalNo; # 사전과 대조해볼 단어들의 수
makeStructure();
calculate();
printout();
# 데이터파일을 읽어서 사전과 메시지 데이터구조를 만든다.
sub makeStructure {
my $ifh = new FileHandle( $dataFileName, 'r' );
my $linecount = 0;
my $dicAddedCount = 0;
my $messageAddedCount = 0;
while (<$ifh>) {
$linecount++;
chomp;
my $line = $_;
next if $line =~ m| \s* \# |x;
next if $line =~ m|^$|;
if ( $linecount == 1 ) {
( $wordLength, $dicEntryTotalNo, $messageTotalNo ) = split ' ', $line;
}
elsif ( $dicAddedCount < $dicEntryTotalNo ) {
push @{ $dic[$dicAddedCount] }, split '', $line;
$dicAddedCount++;
}
elsif ( $messageAddedCount < $messageTotalNo ) {
my $position = 0;
while ( $line =~ m/ ( \(\w+\) | \w ) /xg ) {
my $element = $1;
$element =~ s/\(//;
$element =~ s/\)//;
my @elArray = split '', $element;
for my $el (@elArray) {
$message[$messageAddedCount]->[$position]->{$el} = 1;
}
$position++;
}
$messageAddedCount++;
}
}
}
# 메시지 데이터구조 내의 각 메시지건들이 각각 사전의 표제어들 중 몇 개와 일치할 수 있는지를 구한다.
sub calculate {
$messageInDicCount[$_] = 0 for ( 0 .. $#message );
my $entryNo = 0;
for my $entry (@dic) {
my $messageNo = 0;
for my $message (@message) {
my $letterPosition = 0;
for my $entryLetter ( @{$entry} ) {
unless (
defined(
$message[$messageNo]->[$letterPosition]->{$entryLetter}
)
)
{
last;
}
$letterPosition++;
if ( $letterPosition == $wordLength ) {
$messageInDicCount[$messageNo]++;
}
}
$messageNo++;
}
$entryNo++;
}
}
sub printout {
for my $messageIndex ( 0 .. $#messageInDicCount ) {
$messageInDicCount[$messageIndex] = 0
unless defined $messageInDicCount[$messageIndex];
print "case #"
. ( $messageIndex + 1 )
. " : $messageInDicCount[$messageIndex]\n";
}
}
그리고 이 프로그램이 돌아갈 때 입력으로 받는 'A-small-attempt0.in' 파일 내용은 다음과 같습니다.
10 25 10
dheoyyidga
ebxfffvhqx
yjjpteklgp
yjwfawdkal
kgmjlupidf
feqrtmvgzd
vxnrcpqhzq
tlyhukdlsh
taljrgxoow
rjwgdyvtiw
ldjjmgvqrq
zkqmwjutzj
qqsmzvmwqw
vbzelmkgce
wdqopmxjgw
sypnmoiakb
xhcwmnkywm
esrvhghgsp
fmpuzdkkew
lbenzsdkqz
yxrqsawbjq
todikcmums
sxtwnuoqeh
pdeitylrzu
isklduprqc
lkbehqyxgf
(vzep)bzelmkgce
(mrz)(jmg)(vbl)(ac)(zhn)(mqs)(dhj)(qbg)(rux)(yci)
(rtgo)(nya)(zhlr)(ijw)(rzch)(vgh)(xado)(vlno)(opfg)(pwd)
(uwxyabcdfghijklmoprs)(ghijklmnpqrsuvwxabcdef)(wxyzabcdfgjklmnoprstuv)(knopqrstuvwxyzacdefghij)(cdefghijklmnoqrstuvwxyzab)(jklmnopqruvwzabcdfgi)(tvwxyzabcdfghijkmnopqrs)(pqrstuvxyzabcdefghjklmno)(efghijklmnopqrsuvwxyzbc)(abcefhijklmnopstuvwxy)
(wxzacdefhijklmnopqrsv)(klnopqrstuvwxyabcdfghi)(rstuvwxyabcdefgijlmnopq)(yzabdefghijklopqstvwx)(yzbcdefghijklmnopqrstuvwx)(wyzabcefghjklmnopqrstuv)(qrstuvwxzabcefhikmnp)(oprstuwxyzabcdfghijkmn)(xyzabcdefghijklmnoprsuvw)(klmnopqrstuxzabcdefghj)
(nuxy)(zerx)(raeh)(cdqs)(stbl)(sap)(djnw)(bdlq)(bejo)(qzd)
(stuvwxyzabcdefghiklmnopq)(stuvwxyzacdefghjlmnopq)(bcdefgijklmopqrstuvwyza)(xyzbcdefghiklmnpqrstvw)(qrstuvwxyzabcdfgijklmno)(ijklmnopqrsvwxyabcdfg)(gijklmopqrstuvwxyzacef)(abdefghijkmnopqrstuvwxyz)(abdefghijlnopqrstuvwxy)(ghijnoqrstuwxyzabcdef)
(fgku)(kmno)(pwbk)(ua)(zdim)(ydps)(koqy)(ahkn)(kvye)(adjw)
(tuwxyzabcdefghijklmnopqrs)(ghkmnopqtuvwxyzabcdef)(rstuvwxzacdeghijkmnoq)(lmopqstuvwxyzabdfghik)(bcdefghjklmnopqrstuvwxy)(ghijklmopqrstuvwxyzacdef)(xyzabcdefghiklmnpqrstvw)(stuvwxyzacdefghijklmnoqr)(tuvyabdefghjklmnopqs)(xyzabcdfgjklmnopqrtuvw)
프로그램의 수행 결과는 다음과 같습니다.
case #1 : 0
case #2 : 1
case #3 : 0
case #4 : 1
case #5 : 3
case #6 : 4
case #7 : 1
case #8 : 2
case #9 : 1
case #10 : 3
실제 code jam의 문제는, 입력파일이 이렇게 작지 않고
- 단어의 글자수는 15
- 사전의 표제어는 5000개
- 문제단어는 500개
입니다.
예를 들어 문제단어 하나가 이런 식입니다.
(xyabdefghiklnopqrstuvw)(tuvxyzabcdefijklmnopq)(yzacdefghijklmnopqrstuvx)(bcdfghiklmnopqrstuvxyza)(pqrstuvwxyzabdefghijklmno)(pqrsuvwxyzbcdeghijkmno)(rstuvxyabcdefijklmnopq)(jklmnopqstuvwxyzabcdegh)(cdefgijklmopqrstuvwxyza)(hjklmopqrstuvwxyzabcdefg)(wxyzabcdefgiklmnoqrsuv)(npqrstvwxyzabcdefghijklm)(efghjklmnopqrstvwxyzabcd)(xyzabcefghijklnopqrstuvw)(opqrstuvwxyzacdghijklmn)
이런 게 500개니까, 망하는 방법으로 풀면 언제 끝날 지 알 수 없겠지요.
여튼 요점은, '노가다도 잘 해야 한다' 입니다.
구글에서 code jam이라고, 문제를 내면 풀이를 프로그램으로 만들어서 제출하는 것을 1단계 2단계... 서바이벌식으로 하는 대회 같은 게 있나 봅니다. 전 참가신청을 해서 한 것은 아니고 팀 동료가 하길래 옆에서 문제 보고 재밌어 보여서 풀어 봤습니다.
일단 문제는 다음과 같은데요.
Problem
After years of study, scientists at Google Labs have discovered an alien language transmitted from a faraway planet. The alien language is very unique in that every word consists of exactly L lowercase letters. Also, there are exactly D words in this language.
Once the dictionary of all the words in the alien language was built, the next breakthrough was to discover that the aliens have been transmitting messages to Earth for the past decade. Unfortunately, these signals are weakened due to the distance between our two planets and some of the words may be misinterpreted. In order to help them decipher these messages, the scientists have asked you to devise an algorithm that will determine the number of possible interpretations for a given pattern.
A pattern consists of exactly L tokens. Each token is either a single lowercase letter (the scientists are very sure that this is the letter) or a group of unique lowercase letters surrounded by parenthesis ( and ). For example: (ab)d(dc) means the first letter is either a or b, the second letter is definitely d and the last letter is either d or c. Therefore, the pattern (ab)d(dc) can stand for either one of these 4 possibilities: add, adc, bdd, bdc.
Input
The first line of input contains 3 integers, L, D and N separated by a space. D lines follow, each containing one word of length L. These are the words that are known to exist in the alien language. N test cases then follow, each on its own line and each consisting of a pattern as described above. You may assume that all known words provided are unique.
Output
For each test case, output
Case #X: K
where X is the test case number, starting from 1, and K indicates how many words in the alien language match the pattern.
Limits
Small dataset
1 ≤ L ≤ 10
1 ≤ D ≤ 25
1 ≤ N ≤ 10
Large dataset
1 ≤ L ≤ 15
1 ≤ D ≤ 5000
1 ≤ N ≤ 500
Sample
|
|
|
|
3 5 4 |
Case #1: 2 |
뭐 머나먼 행성에서 수신된 외계인의 언어가 어쩌고 하는 귀신 씨나락 까먹는 소리로 시작하는데 이런건 그냥 제끼고 간단히 정리하면 다음과 같습니다.
1) '단어'는 다음과 같이 모든 글자가 분명한 경우도 있고, 단어에 대한 정보가 불충분하여 일부/전부의 글자가 불분명할 수 있습니다. 하지만 어떤 경우에도 모든 단어의 글자수는 동일합니다.
- 모든 글자가 분명한 경우의 단어 예 : abc , agh, dac 등등
- 일부/전부의 글자가 불분명한 경우의 단어 예 : (ab)(bc)a , (ds)(gw)(fd) , h(xr)g
* 괄호는 그 안의 글자들 중 하나라는 뜻으로서, (ab)(bc)a 는 다음과 같은 4 경우가 다 될 수 있다는 이야기입니다.
: aba, aca, bba, bca
2) '사전'은 다음과 같이 모든 글자가 분명한 단어들의 모음입니다. 사전의 모든 단어의 글자수는 위와 마찬가지로 동일합니다.
: abg, fwg, svc, sfe
3) 입력 파일 (우리가 이걸 가지고 문제를 풀어야 함) 은 다음과 같은 형식입니다.
3 5 4
abc
bca
dac
dbc
cba
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc
* 첫행의 '3 5 4' 의 의미 :
- 모든 단어의 글자수는 3 (그냥 단어 및 사전 내의 단어 모두 동일)
- 아래에 나열된 단어 중 처음 5개는 사전에 수록된 단어
- 아래에 나열된 단어 중 사전에 있는 단어 뒤에 나오는 4개의 단어는 사전에 등록되어 있는지 아닌지 찾아봐야 하는 단어
* 두번째행부터 나오는 다음의 5행은 사전에 있는 5개의 단어를 나타냄. 즉 사전의 표제어.
abc
bca
dac
dbc
cba
* 그 뒤에 나오는 4행은 이 단어들이 사전에 있는지 없는지 찾아봐야 하는 단어들.
(ab)(bc)(ca)
abc
(abc)(abc)(abc)
(zyx)bc
4) 출력 파일 (우리가 만들어내야 하는 최종 결과) 는 다음과 같은 식입니다.
Case #1: 2
Case #2: 1
Case #3: 3
Case #4: 0
케이스 #1 : 2 라는 것이 무슨 말인가 하면
- 위 3)의 입력파일에서 사전의 표제어가 아니라 사전에 등재되어 있는지 아닌지 찾아봐야 할 4행이 각각 케이스 #1~#4가 되고
- 그러면 case#1은 (ab)(bc)(ca) 라는 단어가 되는데, 이걸로 가능한 단어의 조합은 사전 표제어들 중 2개와 일치한다는 의미입니다. 즉 (ab)(bc)(ca)로 만들 수 있는 단어 조합은 여러 개가 있는데 이 중 'abc'와 'bca'가 사전에 있는 단어이고 나머지 조합들은 사전에 없습니다. 2개가 사전과 일치하니까 값이 2 입니다.
그래서 최종 목표는, 입력파일을 받아서, 사전에서 찾아봐야 할 단어들 목록 전체에 대해서 사전에 각각 몇 번씩 나오는지를 구하고, 출력파일을 만드는 것입니다.
일단 여기까지 문제설명만. 풀이는 code jam 제출마감시간 이후에 올리겠습니다. 저는 참가하지 않았지만, 모범답안은 아니라도 일단 작동하는 답안을 올리면 안되겠죠.
