algorithm file fragmentation

• 문제보기
• 3장 Summit Pages

CynicJJ

    Public Class FileFragments
    
    	Function GetOriginalFile(ByVal fragments As List(Of String)) As String
    		Dim frags As New List(Of String)(fragments)
    		frags.Sort(AddressOf CompareLength)
    
    		Dim candidate As List(Of String) = GetCombined(frags(0), frags)
    		RemoveDuplicated(candidate)
    		For i As Integer = 1 To frags.Count - 1
    			If candidate.Count = 1 Then Exit For
    
    			Dim combined As List(Of String) = GetCombined(frags(i), frags)
    			RemoveWrongCandidate(candidate, combined)
    		Next
    
    		Return candidate(0)
    	End Function
    
    	Private Sub RemoveDuplicated(ByVal candidate As List(Of String))
    		Dim i As Integer
    		While i < candidate.Count
    			Dim duplicated As Integer = candidate.IndexOf(candidate(i), i + 1)
    			If duplicated <> -1 Then
    				candidate.RemoveAt(i)
    			Else
    				i += 1
    			End If
    		End While
    	End Sub
    
    	Private Sub RemoveWrongCandidate(ByVal candidate As List(Of String), ByVal combined As List(Of String))
    		Dim i As Integer
    		While i < candidate.Count
    			If combined.IndexOf(candidate(i)) = -1 Then
    				candidate.RemoveAt(i)
    			Else
    				i += 1
    			End If
    		End While
    	End Sub
    
    	Private Function GetCombined(ByVal frag, ByVal frags) As List(Of String)
    		Dim originalLength As Integer = frags(0).Length + frags(frags.Count - 1).Length
    
    		Dim combined As New List(Of String)
    		For i As Integer = frags.Count - 1 To 0 Step -1
    			Dim compared As String = frags(i)
    			If compared.Length + frag.Length = originalLength Then
    				combined.Add(frag + compared)
    				combined.Add(compared + frag)
    			End If
    		Next
    		Return combined
    	End Function
    
    	Private Shared Function CompareLength(ByVal str1 As String, ByVal str2 As String) As Integer
    		If str1.Length > str2.Length Then
    			Return 1
    		ElseIf str1.Length < str2.Length Then
    			Return -1
    		Else
    			Return 0
    		End If
    	End Function
    
    End Class

Outbreak

문제 요약

• 동일한 파일 n 개가 모두 다른 위치에서 2개씩 쪼개져 2n 개 됐다.
• 이 파일 조각들을 이용해 원본 파일 알아내기!

문제 해결

• 무조건 반으로 쪼개지므로 조각 길이를 사용
• 조각은 파일의 앞부분이나 뒷부분

소감

• 대충 짜고 그냥 돌려 봤는데.. Solved.. 허허..
• Solved 됐으므로.. 수정은 없습니다. ㅋㅋ

풀이

    // "File Fragmentation" Solution By Outbreak 
    
    #include <iostream>
    #include <map>
    #include <vector>
    #include <string>
    #include <set>
    #include <algorithm>
    
    using namespace std;
    
    //#define _TDD
    
    // 한 파일의 크기 구할 수 있음.
    
    // 각 조각은 앞부분 아니면 뒷부분!
    
    // 클래스로 리팩토링 할 것!
    namespace Solver
    {
    	static const int MAX_FRAGMENT = 144 * 2;
    
    	static vector<string> VFragment(MAX_FRAGMENT);
    
    	void MakeFragmentTable()
    	{
    		VFragment.clear();
    	}
    
    	void InsertFragment(const string& fragment)
    	{
    		VFragment.push_back(fragment);
    	}
    
    	int FindCompleteFileLength()
    	{
    		int sum = 0;
    		int n = (int)VFragment.size() / 2;
    
    		if(n==0)
    			return -1;
    
    		for( int i=0; i<(int)VFragment.size(); i++ )
    		{
    			sum += (int)VFragment[i].length();
    		}
    
    		return sum / n;
    	}
    
    	bool CheckCompleteFile(string front, string end)
    	{
    		string file = front + end;
    
    		// 검증
    
    		// 모든 조각들이 맞춰지는지 확인해 본다.
    
    		int i;
    
    		// 앞, 뒤에서 찾아봄.
    		for( i=0; i<(int)VFragment.size(); i++ )
    		{			
    			size_t pos = file.find(VFragment[i]);
    
    			// 앞
    			if( pos == 0 )
    				continue;
    
    			// 뒤
    			pos = file.rfind(VFragment[i]);
    			if( pos + VFragment[i].length() == file.length() )
    				continue;
    
    			return false;
    		}
    
    		return true;
    	}
    	
    	string Recovery()
    	{
    		string result = "01110111";
    		
    		// 파일의 크기를 찾는다.
    		int length = FindCompleteFileLength();
    
    		if( length == -1 )
    			return "error";
    
    		const int remain = length - (int)VFragment[0].length();
    		
    		set<string> Set;
    		// 첫번째 조각을 앞이라고 가정
    		// 짝이 될 수 있는 녀석들 조사. set 에다 넣는다.
    		for( int i=0; i<(int)VFragment.size(); i++ )
    		{
    			if( remain == (int)VFragment[i].length() )
    			{
    				Set.insert(VFragment[i]);
    			}
    		}
    
    		// 앞일 경우 Set 에 든 녀석들 합해서 문장 만들기
    		for( set<string>::iterator it = Set.begin(); it != Set.end(); it++ )
    		{
    			if( CheckCompleteFile(VFragment[0],*it) )
    			{
    				result = VFragment[0] + *it;
    				return result;
    			}
    		}
    
    		// 뒤일 경우 Set 에 든 녀석들 합해서 문장 만들기
    		for( set<string>::iterator it = Set.begin(); it != Set.end(); it++ )
    		{
    			if( CheckCompleteFile(*it, VFragment[0]) )
    			{
    				result = *it + VFragment[0];
    				return result;
    			}
    		}
    
    		return "none";		
    	}
    
    }
    
    namespace Runner
    {
    	void Execute(istream& in, ostream& out)
    	{
    		int sample = 0;
    
            in >> sample;
    
            while( sample-- )
            {                
    			// 테이블 초기화
    			Solver::MakeFragmentTable();
    
                while(true)
                {               
    				string fragment;
    				in >> fragment;
    
                    if( in.fail() )
    					break;
    
    				// 조각 넣기
    				Solver::InsertFragment(fragment);
    
    				in.get();
    
                    if( in.peek() == '\n')
                    {										
    					break;
                    }				
                }
    
    			// 처리 하기
    			out << Solver::Recovery() << endl;
    		
                if( sample > 0 )
                {
    				out << endl;
                }
            }
    
    	}
    }
    
    
    #ifdef _TDD
    
    #include "unittest++.h"
    
    TEST(Output)
    {
    	stringstream input;
    	stringstream output;
    
    	input <<
    			"2\n\n"
    			"011\n"
    			"0111\n"
    			"01110\n"
    			"111\n"
    			"0111\n"
    			"10111\n"
    			"\n"
    			"011\n"
    			"0111\n"
    			"01110\n"
    			"111\n"
    			"0111\n"
    			"10111";
    			
    	Runner::Execute(input, output);
    
    	CHECK_EQUAL("01110111\n01110111",output.str());	
    }
    
    #endif
    
    int main()
    {
    
    #ifdef _TDD	
    	UnitTest::RunAllTests();
    #else
    	Runner::Execute(cin, cout);
    #endif // _TDD
    	return 0;
    
    }