문제 12, 암호 깨기 ( Crypt Kicker )

PC/UVa ID : 110204/843

사설
.. 문제를 이해 하는데 엄청난 노력이 필요했다. 일반적을 나는 짜증이 나면, 단잠(30~ 40분)을 자는 스타일인데, 이 문제를 풀기 위해서 3번은 잠을 청해야 했기에, 얼마나 문제를 이해하고자 노력했는지 스스로가 알 수 있었다.

개요

아주 간략하게 설명하자면, 암호화된 문자를 해독하여, 표준출력을 하라는 내용이다. 여기서 다루는 암호의 종류는 "알파벳 문자 한개를 다른 알파벳 문자 한개로 치환하는 암호"로 흔히 "단문자 암호"라 불리는 암호이다.

그러므로 문제는 임의의 단문자 암호화가 된 문자들이 입력되었을 때, 이 단문자 암호를 깨고, 본래의 문자가 출력되게 하라는 것이다. 임의의 단문자 암호화는 "입력 하는 사람"만 알고 있을 뿐이라는 것이다.

여기서 전제조건을 하나 추가하면, 암호화된 텍스트의 본래 텍스트는 주어진 사전에 있는 단어만을 사용해야 한다는 것이다.

입력

사전에 등록될 단어들의 수를 정수 n에 입력 받는다. 이때 n은 1000 이하여야 한다.
1번에 의해 받은 n개의 단어들의 수 만큼 한줄에 한 단어씩 입력받는다. 이때 단어의 길이는 16자 이하여야 한다.
2번이 끝나면, 임의의 단문자 암호화된 텍스트를 입력받는다. 이때 임호화된 텍스트는 소문자, 스페이스만 들어가며, 80자 이하여야 한다.
공백이 입력될 때까지 3번을 반복하며 입력받는다.

출력

입력의 3번이 끝나면, 바로 복호화가된 문자들을 출력한다. 입력의 3번이 반복될때마다 복호화된 문자들을 계속 출력하기만 하면 된다.

관련링크

http://online-judge.uva.es/p/v8/843.html

마땅히 떠오르는 코드가 없으므로, 실제로 종이와 연필로 복호화를 해보는 연습을 해보고 요령이 생기면, 코드화 할 수 있을 것이라고 생각 한다.

-- 루아에 없는 테이블 기능을 추가 했다. 여러모로 편하기 때문이다.

-- 테이블의 값을 찾는 함수, 테이블을 순차로써 찾아야만 할 때 쓴다.
function table.search( t, value )
	for k, v in pairs(t) do
		if v == value then return true end
	end
	return false
end

-- 테이블의 사이즈를 계산하는 함수
function table.size( t )
	size = 0
	for k in pairs( t ) do
		size = size + 1
	end

return size
end

-- 테이블 요소 출력
function table.print( t )
	for k, v in pairs( t ) do
		print( k, v )
	end
end

-- 테이블 얕은 복사
function table.copy( t )
	copy_t = {}
	for k, v in pairs( t ) do
		copy_t[k] = v
	end

return copy_t
end

-- 디파인 변수 정의
LimitationOfCountWord = 1000
LimitationOfWordLen = 16
LimitationOfStringLen = 80

-- 디코드 함수
function Decode( ENCString, DECString, DECMap )
	-- Step 1. 몇 개의 문자를 디코딩 할지 결정한다.
	LoopCount = string.len( ENCString )

-- Step 2. 인코딩, 디코딩 문자열의 이터레이터를 뽑는다.
	TempDECMap = {}
	ENCIter = string.gmatch( ENCString, "%l" )
	DECIter = string.gmatch( DECString, "%l" )

-- Step 3. 루프를 돌며, 이터레이터로 문자열을 얻어와 서로 매칭이 되는지
	-- 확인한다. 확인은 TempDECMap을 통해서 확인한다.
	for i = 1, LoopCount, 1 do
		ENCC = ENCIter()
		DECC = ENCIter()

-- Step 4.
		-- 아래 코드는 기존의 디코딩 맵에서 기존의 문자를 디코딩 했지만
		-- 현재의 디코딩 문자와 다르다면, 디코딩문자열 자체가 틀린 것으므로
		-- 그냥 빠저나가라는 코드이다.
		if DECMap[ENCC] and DECC ~= DECMap[ENCC] then
			return {}
		end

-- Step 5.
		-- 아래의 코드는 임시 디코딩 맵에 값이 nil이라면 현재의 디코딩문자를
		-- 넣으라는 코드이다.
		TempDECMap[ENCC] = TempDECMap[ENCC] or DECC

-- Step 6.
		-- 아래의 코드는 임시 디코딩 맵에서 인코딩 문자가 현재의 디코딩 문자가 다를 경우
		-- 현재의 디코딩 문자열자체가 틀린 것이므로 그냥 빠저나가라는 코드이다.
		if DECC ~= TempMap[ENCC] then
			return {}
		end
	end

return TempDECMap
end

-- 해독하는 함수이다.
function DecodeProcess( Dictionary, ENCWordTable )
	-- 디코딩 맵
	DECMap = {}

-- 인코딩 워드 테이블의 각 요소에 접근한다.
	for ENCWordTableKey, ENCWords in pairs( ENCWordTable ) do
		-- 인코딩 워드 테이블 이하. ENCWordTable의 키로써 사전에 없다면
		-- 인코딩 할 수 없으므로, false를 리턴한다.
		if nil == Dictionary[ENCWordTableKey] then return false end

-- 참조가 되는 테이블에서 인코딩 후보가 될 수 있는 단어들을 얻어 온다.
		CandidateWords = Dictionary[ENCWordTableKey]

--[[
		-- test code start
		for i, w in pairs( CandidateWords ) do
			print( i, w, "단어 갯수", #ENCWords, ENCWordTableKey )
		end
		print("끝")
		-- test code end
		--]]

-- 이제 인코딩되는 단어들과 후보가 되는 단어들을 대조하여
		-- 정말 후보가 될 수 있는지 알아 본다.
		for i, ENCWord in pairs( ENCWords ) do
			DECTable = {}
			for j, CandidateWord in pairs( CandidateWords ) do
				TempDECTable = Decode( ENCWord, CandidateWord, DECMap )

if 0 ~= table.size(TempDECTable) then
					table.insert(DECTable, TempDECTable)
				end
			end

-- 디코딩 테이블의 요소가 1개 밖에 없다면, 디코딩이 된것이므로
			-- 디코딩 맵에 기록해 둔다.
			if 1 == #DECTable then
				for DECKey, DECValue in pairs( DECTable[1] ) do
					DECMap[DECKey] = DECMap[DECKey] or DECValue

if DECValue ~= DECMap[DECKey] then return false end
				end
			end
		end
	end

return DECMap
end

-- 사전에 단어들을 넣는다.
-- 함수 안에서 예외처리를 하여, 성공여부를 뱉어 낸다.
function InsertWordToDic( Dictionary, Word )
	if LimitationOfWordLen < string.len( Word ) then
		print( "Warn : LimitationOfWordLen is Over!")
		return false
	end

if nil ~= Dictionary[Word] then return false end

WordLen = string.len(Word)
	Dictionary[WordLen] = Dictionary[WordLen] or {}
	table.insert( Dictionary[WordLen], Word )

return true
end

function main()
	-- 1. 사전에 들어갈 단어들의 수를 지정한다.
	CountOfWordinDic = io.read()
	CountOfWordinDic = tonumber( CountOfWordinDic )
	if nil == CountOfWordinDic or LimitationOfCountWord < CountOfWordinDic then
		print( "Error : CountOfWordinDic is invalid or Over!")
		return
	end

-- 2. 사전의 단어들을 1번에서 받은 수 만큼 받는다.
	Dictionary = {}
	LoopCount = 1
	-- for문 말고 while을 쓴 이유는 정상 입력 처리시에만
	-- 1씩 카운트를 늘리기 위해서 이다.
	while LoopCount <= CountOfWordinDic do
		Word = io.read()
		isSuccess = InsertWordToDic( Dictionary, Word )
		if true == isSuccess then LoopCount = LoopCount + 1 end
	end

while true do
		ENCString = io.read()
		--[[
		Dictionary = { }
		Dictionary[3] = { "and" }
		Dictionary[4] = { "dick", "jane", "puff", "spot" }
		Dictionary[6] = { "yertle" }

-- 암호화가 된 문자열을 입력받는다.
		ENCString = "bjvg xsb hxsn xsb qymm xsb rqat xsb pnetfn"
		--]]

-- Step 1. 암호화된 문자열이 없다면 return 하고 프로그램을 끝낸다.
		if "" == ENCString then return end

-- Step 2. 만약 길이가 한계길이를 초과 했다면 에러를 찍고 프로그램을 끝낸다.
		if LimitationOfStringLen < string.len( ENCString ) then
			print( "Error : LimitationOfStringLen is Invalid!")
			return
		end

-- Step 3. 암호화 된 문자열을 단어 단위로 쪼갠다.
		ENCWordTable = {}
		for ENCWord in string.gmatch( ENCString, "%l+" ) do
			WordLen = string.len( ENCWord )
			ENCWordTable[WordLen] = ENCWordTable[WordLen] or {}

-- Step 4. 쪼개진 단어를 인코딩워드테이블에 중복을 제거하여 밀어 넣는다.
			if false == table.search( ENCWordTable[WordLen], ENCWord ) then
				table.insert( ENCWordTable[WordLen], ENCWord )
			end
		end

-- Step 5. 디코딩 한다
		DecMap = DecodeProcess( Dictionary, ENCWordTable )
		DecMap[" "] = " "

-- Step 6. 출력 한다.
		DECString = ""
		for w in string.gmatch( ENCString, "." ) do
			--print( w )
			--print(type(w))
			DECString = DECString .. (DecMap[w] or "*")
		end

print( DECString )
		return
	end
end

main()

저작자표시

'책 정리 > Programming Challenges : 알고리즘 트래이닝 북' 카테고리의 다른 글

문제 17, WERTYU, PC/UVa ID : 110301/10082 (0)	2010.12.28
문제 16, 야찌(Yahtzee) (6)	2010.12.28
문제 15, 경시 대회 점수판(Contest Scoreboard) (0)	2009.12.13
문제 14, 에르되시 수 (Erdos Numbers) (1)	2009.12.08
문제 13, 쌓아 올리기 (Stack 'em Up) (1)	2009.11.25
문제 11, 동맹 휴업(Hartal) (2)	2009.11.07
문제 10, 포커 패 (Poker Hands) (1)	2009.11.06
문제 9, 유쾌한 점퍼 (Jully Jumpers) (2)	2009.11.01
문제 8, 호주식 투표법 (Australian Voting) (1)	2009.11.01
문제 7 : 체크 확인 - Check the Check (4)	2009.10.28