Skip to content

algorithm stacks of flapjacks

Jump to bottom
Jongbin Oh edited this page Jun 8, 2013 · 1 revision

해답

  • 당연히 Solved

      /* BEGIN_OF_SOURCE_CODE */
  
  /* JUDGE_ID: 46288WZ 120 C "" */
  
  /* $Id$ */
  
  #include <stdio.h>
  
  void main()
  {
  	while (!feof(stdin))
  	{
  		char temp[100];
  		int pencake_num = 0;
  		int diameter[30];
  		int i, j;
  		int code;
  		char* pt;
  
  		if(!gets(temp)) break;
  
  		printf("%s\n", temp);
  
  		pt = temp;
  		code = 0;
  		while (pt[0])
  		{
  			if (pt[0] >= '0' && pt[0] <= '9')
  			{
  				code = code*10 + (pt[0]-'0');
  			}
  			else
  			{
  				if(code > 0)
  				{
  					diameter[pencake_num] = code;
  					pencake_num++;
  					code = 0;
  				}
  			}
  			pt++;
  		}
  		if(code > 0)
  		{
  			diameter[pencake_num] = code;
  			pencake_num++;
  		}
  
  		for(i=pencake_num-1; i>=1 ; i--)
  		{
  			int now = i;
  			for(j=0; j<i; j++)
  				if(diameter[now]<diameter[j]) now=j;
  
  			if(now<i)
  			{
  				if(now>0)
  				{
  					printf("%d ", pencake_num - now);
  					for(j=0; j<=now/2;j++)
  					{
  						int temp = diameter[j];
  						diameter[j] = diameter[now-j];
  						diameter[now-j]=temp;
  					}
  				}
  				printf("%d ", pencake_num -i);
  				for(j=0;j<=i/2; j++)
  				{
  					int temp = diameter[j];
  					diameter[j] = diameter[i - j];
  					diameter[i - j] = temp;
  				}
  			}
  		}
  		printf("0\n");
  	}
  }
  
  /* @END_OF_SOURCE_CODE */

soomong

  • 쉽지가 않네요...

    • 실패하는 케이스가 몇개 있네요.
      • 3 2 1 8 9 -> 3 0
      • 1 1 2 2 4 4 3 -> 3 1 6 2 4 0
      • 이 경우엔 2 1 3 4 0 이라는 더 짧은 솔루션도 존재합니다. 하지만 문제에선 동일 크기의 팬케이크는 입력되지 않으므로 이 경우까지 고려하진 않으셔도 됩니다. - Mastojun
      • 해답하고 같게만 만들려고 했더니 이런 오류가 있었네요.ㅋ
      • 잘못적은 솔루션을 고쳐주시는 센스!
    • 제대로 된 위치에 있는 것은 flip 할 필요가 없었는데 체크를 안하고 있었네요. -soomong

  • FlapJackMain

      import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.ArrayList;
  import java.util.Collections;
  
  public class FlapJackMain {
  
  	ArrayList<Integer> sortedStack = new ArrayList<Integer>();
  	ArrayList<Integer> stack = new ArrayList<Integer>();
  	
  	public static void main(String args[])
  	{
  		FlapJackMain jack = new FlapJackMain();
  		String in;
  		
  		while(!(in = readLine()).equals(""))
  		{
  			if( jack.initStack(in) == false )
  				break;
  		
  			jack.printStack();
  			System.out.println(jack.parseStack());
  			//jack.printStack();
  		}
  	}
  	
  	public boolean initStack(String in)
  	{
  		sortedStack.clear();
  		stack.clear();
  		
  		String[] data = in.split(" ");
  		
  		if( data.length > 30)
  			return false;
  		
  		for(int i =0; i< data.length; i++)
  		{
  			int value = Integer.parseInt(data[i]);
  			
  			if( value < 1 || value > 100)
  				return false;
  			
  			sortedStack.add(value);
  			stack.add(value);
  		}
  		
  		Collections.sort(sortedStack);
  		return true;
  	}
  	
  	public String parseStack()
  	{
  		String result = "";
  		int count = stack.size();
  		
  		while(!stack.equals(sortedStack))
  		{
  			// sortedSatck 끝의 값부터 stack 에서의 index 얻어오기. 
  			int targetIndex = stack.indexOf(sortedStack.get(count-1));
  		
  			// 맞는 위치에 있지 않는 것들만 Flip
  			if( (count-1) != targetIndex )
  			{
  				// stack 의 바꿀값을 일단 맨위로 올린뒤 
  				if( targetIndex != 0 )
  				{
  					flip(stack.size() - targetIndex);
  					result += (stack.size() - targetIndex) + " ";
  				}
  					
  				// stack 의 해당 index 로 flip
  				flip(stack.size() - (count-1));
  				result += (stack.size() - (count-1)) + " ";
  			}
  			
  			count--;
  		}
  		
  		result += "0";
  		
  		return result;
  	}
  
  	public void flip(int point)
  	{
  		ArrayList<Integer> newStack = new ArrayList<Integer>();
  
  		// stack -> newStack  copy
  		for(int i=0; i< stack.size(); i++)
  		{
  			newStack.add(stack.get(i));
  		}
  		
  		// point 까지의 값을 newStack 에 반대로 flip 하여 저장
  		for(int i= 0 ,j= stack.size() - point ; j >= 0 ; i++,j--)
  		{
  			newStack.set(j,stack.get(i));
  		}
  		
  		// newStack -> stack  Copy
  		for(int i=0; i< stack.size(); i++)
  		{
  			stack.set(i,newStack.get(i));
  		}
  		
  	}
  	
  	public void printStack()
  	{
  		for(int i=0; i< stack.size(); i++)
  		{
  			System.out.print(stack.get(i) + " ");
  		}
  
  		System.out.println("");
  	}	
  	
  	public static String readLine()
  	{
  		String data = null;
  		
  		try
  		{
  			BufferedReader is = new BufferedReader(new InputStreamReader(System.in));
  			data = is.readLine();
  		}
  		catch(IOException e)
  		{
  			System.out.println("IOException " +e);
  		}
  		
  		return data;		
  	}
  	
  }

  • Junit

      import java.util.ArrayList;
  
  import junit.framework.TestCase;
  
  
  public class FlapJackMainTest extends TestCase {
  
  	FlapJackMain jack = new FlapJackMain();
  	
  	public void testRun() {
  		
  		
  	}
  	
  	public void testParseStack() {
  		
  		jack.initStack("5 4 3 2 1");
  		assertEquals(false,jack.stack.equals(jack.sortedStack));
  		jack.parseStack();
  		assertEquals(true,jack.stack.equals(jack.sortedStack));
  		
  		jack.initStack("5 4 3 2 1");
  		assertEquals("1","1 0",jack.parseStack());
  		
  		jack.initStack("5 1 2 3 4");
  		assertEquals("1","1 2 0",jack.parseStack());
  
  		jack.initStack("3 2 1 8 9");
  		assertEquals("1","3 0",jack.parseStack());
  
  		jack.initStack("1 1 2 2 4 4 3");
  		assertEquals("1","3 1 6 2 4 0",jack.parseStack());
  	}
  	
  	public void testFlip() {
  					
  		ArrayList<Integer> fir = new ArrayList<Integer>();
  		fir.add(1);
  		fir.add(2);
  		fir.add(3);
  		fir.add(4);
  		fir.add(5);
  		
  		jack.initStack("5 4 3 2 1");
  		jack.flip(1);
  		assertEquals(true,jack.stack.equals(fir));
  
  		jack.flip(2);
  		assertEquals(false,jack.stack.equals(fir));
  		fir.set(0, 4);
  		fir.set(1, 3);
  		fir.set(2, 2);
  		fir.set(3, 1);
  		fir.set(4, 5);
  		assertEquals(true,jack.stack.equals(fir));
  		
  		jack.flip(3);
  		fir.set(0, 2);
  		fir.set(1, 3);
  		fir.set(2, 4);
  		fir.set(3, 1);
  		fir.set(4, 5);
  		assertEquals(true,jack.stack.equals(fir));		
  
  		jack.flip(4);
  		fir.set(0, 3);
  		fir.set(1, 2);
  		fir.set(2, 4);
  		fir.set(3, 1);
  		fir.set(4, 5);
  		assertEquals(true,jack.stack.equals(fir));		
  			
  	}
  
  }

CynicJJ

  • 동일 크기는 처리하지 않음
  • Java는 컴파일 에러. 버전 때문인가?
  • IsOrdered() 에서 pos < flapjackSizes.size()-1 이 맞음. ㅋ

!FlapjackStack.vb

    ' $Id: FlapjackStack.vb 90 2008-02-13 23:49:10Z 정희종 $
    
    Public Class FlapjackStack
    	Private _flapjackSizes As List(Of Integer) = New List(Of Integer)
    	Private _inputFlapjackSizes As List(Of Integer) = New List(Of Integer)
    	Private _flipPositions As List(Of Integer) = New List(Of Integer)
    
    	ReadOnly Property FlipPositions() As List(Of Integer)
    		Get
    			Return _flipPositions
    		End Get
    	End Property
    
    	ReadOnly Property InputFlapjackSizes() As List(Of Integer)
    		Get
    			Return _inputFlapjackSizes
    		End Get
    	End Property
    
    	Sub SetupFlapjacks(ByVal flapjacsSizes() As Integer)
    		_flapjackSizes.Clear()
    		' 위치는 1부터 시작하므로 빈 엔트리 하나 추가
    		_flapjackSizes.Add(Nothing)
    		' 뒤집에서 추가
    		Array.Reverse(flapjacsSizes)
    		_flapjackSizes.AddRange(flapjacsSizes)
    
    		' 최초 입력 저장
    		_inputFlapjackSizes.Clear()
    		_inputFlapjackSizes = _flapjackSizes.GetRange(0, _flapjackSizes.Count)
    
    		' flip 위치 초기화
    		_flipPositions.Clear()
    	End Sub
    
    	Function GetSize(ByVal position As Integer) As Integer
    		Dim isValid = (position >= 1 And position < _flapjackSizes.Count)
    		If isValid Then
    			Return _flapjackSizes(position)
    		Else
    			Return 0
    		End If
    	End Function
    
    	Sub Flip(ByVal position As Integer)
    		Dim flipCount = _flapjackSizes.Count - position
    
    		Dim subList As List(Of Integer) = _flapjackSizes.GetRange(position, flipCount)
    		subList.Reverse()
    
    		_flapjackSizes.RemoveRange(position, flipCount)
    		_flapjackSizes.InsertRange(position, subList)
    
    		' flip 위치 보관
    		_flipPositions.Add(position)
    	End Sub
    
    	Function IsOrdered() As Boolean
    		For pos As Integer = 1 To _flapjackSizes.Count - 1
    			If GetSize(pos) < GetSize(pos + 1) Then
    				Return False
    			End If
    		Next
    		Return True
    	End Function
    
    	Function GetSizeOrderOf(ByVal order As Integer) As Integer
    		Dim sorted As List(Of Integer) = New List(Of Integer)
    		sorted = _flapjackSizes.GetRange(0, _flapjackSizes.Count)
    		sorted.Sort()
    
    		Return sorted(sorted.Count - order)
    	End Function
    
    	Function GetPositionOrderOf(ByVal order As Integer) As Integer
    		For i As Integer = _flapjackSizes.Count - 1 To 1 Step -1
    			If GetSizeOrderOf(order) = _flapjackSizes(i) Then
    				Return i
    			End If
    		Next
    	End Function
    
    	Function IsLocateLastSizeOrderOf(ByVal order As Integer) As Boolean
    		Return (GetSizeOrderOf(order) = _flapjackSizes(_flapjackSizes.Count - 1))
    	End Function
    
    	Sub Order()
    		For order As Integer = 1 To InputFlapjackSizes().Count - 1
    			If IsOrdered() Then Exit For
    
    			Dim needFlip As Boolean = (GetPositionOrderOf(order) <> order)
    			If needFlip Then
    				If Not IsLocateLastSizeOrderOf(order) Then
    					Flip(GetPositionOrderOf(order))
    				End If
    				Flip(order)
    			End If
    		Next
    
    		If IsOrdered() Then
    			_flipPositions.Add(0)
    		End If
    	End Sub
    End Class

!ModuleTest.vb

    ' $Id: ModuleTest.vb 90 2008-02-13 23:49:10Z 정희종 $
    
    Imports Microsoft.VisualStudio.TestTools.UnitTesting
    
    Module ModuleTest
    	Private _stack As FlapjackStack = New FlapjackStack
    
    	Sub Setup()
    		Dim flapjackSizes() As Integer = {8, 4, 6, 7, 5, 2}
    		_stack.SetupFlapjacks(flapjackSizes)
    	End Sub
    
    	Sub Run()
    		Setup()
    
    		SetupFlapjacksTest()
    		SetupFlapjacksInvalidTest()
    		FlipTest()
    		GetInputStackSizesTest()
    		IsOrderedTest()
    		GetSizeOrderOfTest()
    		GetPositionOrderOfTest()
    		IsLocateLastSizeOrderOfTest()
    		OrderManuallyTest()
    		OrderImplTest()
    		OrderTest()
    		GetFlipPositionsTest()
    		NoNeedFlipTest()
    		DuplicatedTest()
    	End Sub
    
    	Sub DuplicatedTest()
    		Dim flapjackSizes() As Integer = {1, 1, 2, 2, 4, 4, 3}
    		_stack.SetupFlapjacks(flapjackSizes)
    		_stack.Order()
    		Assert.AreEqual(6, _stack.FlipPositions.Count)
    		Assert.AreEqual(3, _stack.FlipPositions(0))
    		Assert.AreEqual(1, _stack.FlipPositions(1))
    		Assert.AreEqual(6, _stack.FlipPositions(2))
    		Assert.AreEqual(2, _stack.FlipPositions(3))
    		Assert.AreEqual(4, _stack.FlipPositions(4))
    		Assert.AreEqual(0, _stack.FlipPositions(5))
    	End Sub
    
    	Sub NoNeedFlipTest()
    		Dim flapjackSizes() As Integer = {3, 2, 1, 8, 9}
    		_stack.SetupFlapjacks(flapjackSizes)
    		_stack.Order()
    		Assert.AreEqual(2, _stack.FlipPositions.Count)
    		Assert.AreEqual(3, _stack.FlipPositions(0))
    		Assert.AreEqual(0, _stack.FlipPositions(1))
    	End Sub
    
    	Sub GetFlipPositionsTest()
    		Setup()
    		_stack.Order()
    		Assert.AreEqual(8, _stack.FlipPositions.Count)
    		Assert.AreEqual(1, _stack.FlipPositions(0))
    		Assert.AreEqual(4, _stack.FlipPositions(1))
    		Assert.AreEqual(2, _stack.FlipPositions(2))
    		Assert.AreEqual(5, _stack.FlipPositions(3))
    		Assert.AreEqual(3, _stack.FlipPositions(4))
    		Assert.AreEqual(4, _stack.FlipPositions(5))
    		Assert.AreEqual(5, _stack.FlipPositions(6))
    		Assert.AreEqual(0, _stack.FlipPositions(7))
    	End Sub
    
    	Sub OrderTest()
    		Setup()
    		_stack.Order()
    		Assert.IsTrue(_stack.IsOrdered())
    	End Sub
    
    	Sub OrderImplTest()
    		Setup()
    		For order As Integer = 1 To _stack.InputFlapjackSizes().Count - 1
    			If Not _stack.IsLocateLastSizeOrderOf(order) Then
    				_stack.Flip(_stack.GetPositionOrderOf(order))
    			End If
    			_stack.Flip(order)
    		Next
    		Assert.IsTrue(_stack.IsOrdered())
    	End Sub
    
    	Sub OrderManuallyTest()
    		Setup()
    		Dim order As Integer = 1
    		Assert.IsTrue(_stack.IsLocateLastSizeOrderOf(order))
    		Assert.AreEqual(1, order)
    		_stack.Flip(1)
    
    		order += 1
    
    		Assert.AreEqual(4, _stack.GetPositionOrderOf(order))
    		_stack.Flip(4)
    		Assert.AreEqual(2, order)
    		_stack.Flip(2)
    
    		order += 1
    
    		Assert.AreEqual(5, _stack.GetPositionOrderOf(order))
    		_stack.Flip(5)
    		Assert.AreEqual(3, order)
    		_stack.Flip(3)
    
    		order += 1
    
    		Assert.IsTrue(_stack.IsLocateLastSizeOrderOf(order))
    		Assert.AreEqual(4, order)
    		_stack.Flip(4)
    
    		order += 1
    
    		Assert.IsTrue(_stack.IsLocateLastSizeOrderOf(order))
    		Assert.AreEqual(5, order)
    		_stack.Flip(5)
    
    		Assert.IsTrue(_stack.IsOrdered())
    	End Sub
    
    	Sub IsLocateLastSizeOrderOfTest()
    		Setup()
    		Assert.IsTrue(_stack.IsLocateLastSizeOrderOf(1))
    		Assert.IsFalse(_stack.IsLocateLastSizeOrderOf(2))
    		_stack.Flip(3)
    		Assert.IsTrue(_stack.IsLocateLastSizeOrderOf(2))
    	End Sub
    
    	Sub GetSizeOrderOfTest()
    		Setup()
    		Assert.AreEqual(8, _stack.GetSizeOrderOf(1))
    		Assert.AreEqual(7, _stack.GetSizeOrderOf(2))
    		Assert.AreEqual(6, _stack.GetSizeOrderOf(3))
    	End Sub
    
    	Sub GetPositionOrderOfTest()
    		Setup()
    		Assert.AreEqual(6, _stack.GetPositionOrderOf(1))
    		Assert.AreEqual(3, _stack.GetPositionOrderOf(2))
    	End Sub
    
    	Sub IsOrderedTest()
    		Assert.IsFalse(_stack.IsOrdered())
    
    		Dim flapjackSizes() As Integer = {1, 2, 3, 4}
    		Dim stack As FlapjackStack = New FlapjackStack
    		stack.SetupFlapjacks(flapjackSizes)
    		Assert.IsTrue(stack.IsOrdered())
    	End Sub
    
    	Sub GetInputStackSizesTest()
    		_stack.Flip(1)
    		Assert.AreEqual(2, _stack.InputFlapjackSizes(1))
    		Assert.AreEqual(5, _stack.InputFlapjackSizes(2))
    	End Sub
    
    	Sub FlipTest()
    		_stack.Flip(3)
    		Assert.AreEqual(7, _stack.GetSize(6))
    		Assert.AreEqual(6, _stack.GetSize(5))
    		Assert.AreEqual(4, _stack.GetSize(4))
    		Assert.AreEqual(8, _stack.GetSize(3))
    	End Sub
    
    	Sub SetupFlapjacksInvalidTest()
    		Assert.AreEqual(0, _stack.GetSize(0))
    		Assert.AreEqual(0, _stack.GetSize(7))
    	End Sub
    
    	Sub SetupFlapjacksTest()
    		Assert.AreEqual(2, _stack.GetSize(1))
    		Assert.AreEqual(7, _stack.GetSize(3))
    		Assert.AreEqual(8, _stack.GetSize(6))
    	End Sub
    
    End Module

!ModuleMain.vb

    ' $Id: ModuleMain.vb 90 2008-02-13 23:49:10Z 정희종 $
    
    Module ModuleMain
    
    	Sub Main()
    #Const UNITTEST = True
    #If UNITTEST Then
    		ModuleTest.Run()
    #End If
    
    #Const RUN = False
    #If RUN Then
    		While True
    			Dim input As String = Console.ReadLine()
    			Dim separator() As Char = {" "c}
    			Dim inputs() As String = input.Split(separator, StringSplitOptions.RemoveEmptyEntries)
    
    			Dim sizes As List(Of Integer) = New List(Of Integer)
    			For Each str As String In inputs
    				sizes.Add(Integer.Parse(str))
    			Next
    
    			Dim stack As FlapjackStack = New FlapjackStack
    			stack.SetupFlapjacks(sizes.ToArray())
    			stack.Order()
    
    			Dim output As String = ""
    			For Each flipPosition As Integer In stack.FlipPositions
    				output += String.Format("{0:D} ", flipPosition)
    			Next
    
    			Console.WriteLine(input)
    			Console.WriteLine(output)
    		End While
    #End If
    	End Sub
    
    End Module

!FlapjackStack.java

    /*
     * Main.java
     *  java program model for www.programming-challenges.com
     */
    
    package flapjack;
    
    import java.io.*;
    import java.util.*;
    
    class Main implements Runnable {
        static String ReadLn(int maxLength){  // utility function to read from stdin,
                                              // Provided by Programming-challenges, edit for style only
            byte line[] = new byte [maxLength];
            int length = 0;
            int input = -1;
            try{
                while (length < maxLength){//Read untill maxlength
                    input = System.in.read();
                    if ((input < 0) || (input == '\n')) break; //or untill end of line ninput
                    line [length++] += input;
                }
    
                if ((input < 0) && (length == 0)) return null;  // eof
                return new String(line, 0, length);
            }catch (IOException e){
                return null;
            }
        }
    
        public static void main(String args[])  // entry point from OS
        {
            Main myWork = new Main();  // Construct the bootloader
            myWork.run();            // execute
        }
    
        public void run() {
            new FlapjackStack().run();
        }
    }
    
    class FlapjackStack implements Runnable {
    	private static FlapjackStack stack = new FlapjackStack();
    	
    	public void run()
    	{
    		String input;
    		
    		while(!(input = readLine()).equals(""))
    		{
    			initStack(input);
    			stack.Order();
    			printStack();
    		}
    	}
    
    	public static void printStack()
    	{
    		for(int i=0 ; i<stack.getInputFlapjackSizes().size() ; i++) {
    			System.out.print(stack.getInputFlapjackSizes().get(i) + " ");
    		}
    		System.out.println();
    		for(int i=0; i< stack.getFlipPositions().size(); i++)
    		{
    			System.out.print(stack.getFlipPositions().get(i) + " ");
    		}
    
    		System.out.println("");
    	}	
    
    	public static boolean initStack(String in)
    	{
    		String[] data = in.split(" ");
    		
    		List<Integer> list = new ArrayList<Integer>();
    		for(int i =0; i< data.length; i++)
    		{
    			int value = Integer.parseInt(data[i]);
    			
    			list.add(value);
    		}
    
    		stack.SetupFlapjacks(list);
    		return true;
    	}
    
    	public static String readLine()
    	{
    		String data = null;
    		
    		try
    		{
    			BufferedReader is = new BufferedReader(new InputStreamReader(System.in));
    			data = is.readLine();
    		}
    		catch(IOException e)
    		{
    			System.out.println("IOException " +e);
    		}
    		
    		return data;		
    	}
    
    	private ArrayList<Integer> flapjackSizes = new ArrayList<Integer>();
    	public ArrayList<Integer> flipPositions = new ArrayList<Integer>();
    	public ArrayList<Integer> getFlipPositions() {
    		return flipPositions;
    	}
    
    	private ArrayList<Integer> inputFlapjackSizes = new ArrayList<Integer>();
    	public ArrayList<Integer> getInputFlapjackSizes() {
    		return inputFlapjackSizes;
    	}
    
    	public void SetupFlapjacks(List<Integer> sizes) {
    		flipPositions.clear();
    
    		inputFlapjackSizes.clear();
    		inputFlapjackSizes.addAll(sizes);
    
    		flapjackSizes.clear();
    		flapjackSizes.add(-1);
    		Collections.reverse(sizes);
    		flapjackSizes.addAll(sizes);
    	}
    
    	public Integer GetSize(int position) {
    		final boolean isValid = (position >= 1 && position < flapjackSizes.size());
    		if (isValid)
    			return flapjackSizes.get(position);
    		else
    			return 0;
    	}
    
    	public void Flip(int position) {
    		List<Integer> subList = flapjackSizes.subList(position, flapjackSizes.size());
    		Collections.reverse(subList);
    
    		flipPositions.add(position);
    	}
    
    	public boolean IsOrdered() {
    		for (int pos = 1; pos < flapjackSizes.size(); pos++) {
    			if (GetSize(pos) < GetSize(pos + 1)) {
    				return false;
    			}
    		}
    		return true;
    	}
    
    	public void Order() {
    		for (int order = 1; order < getInputFlapjackSizes().size(); order++) {
    			if (IsOrdered())
    				break;
    
    			boolean needFlip = (GetPositionSizeOrderOf(order) != order);
    			if (needFlip) {
    				if (!IsLocateLastSizeOrderOf(order)) {
    					Flip(GetPositionSizeOrderOf(order));
    				}
    				Flip(order);
    			}
    		}
    
    		if (IsOrdered()) {
    			flipPositions.add(0);
    		}
    	}
    
    	public boolean IsLocateLastSizeOrderOf(Integer order) {
    		List<Integer> sorted = new ArrayList<Integer>();
    		sorted.addAll(flapjackSizes);
    		Collections.sort(sorted);
    
    		int sizeOrderof = sorted.get(sorted.size() - order);
    		return (sizeOrderof == flapjackSizes.get(flapjackSizes.size() - 1));
    	}
    
    	public int GetPositionSizeOrderOf(Integer order) {
    		List<Integer> sorted = new ArrayList<Integer>();
    		sorted.addAll(flapjackSizes);
    		Collections.sort(sorted);
    
    		int sizeOrderof = sorted.get(sorted.size() - order);
    		for (int i = flapjackSizes.size() - 1; i > 0; i--) {
    			if (sizeOrderof == flapjackSizes.get(i)) {
    				return i;
    			}
    		}
    		return 0;
    	}
    }

!FlapjackStackTest.java

    package flapjack;
    
    import static org.junit.Assert.*;
    import java.util.Arrays;
    
    import org.junit.Test;
    
    public class FlapjackStackTest {
    	FlapjackStack _stack = new FlapjackStack();
    
    	@org.junit.Before
    	public void SetupFlapjackStacks() {
    		Integer[] flapjackSizes = { 8, 4, 6, 7, 5, 2 };
    		_stack.SetupFlapjacks(Arrays.asList(flapjackSizes));
    	}
    
    	@Test
    	public void SetupTest() {
    		assertEquals(2, _stack.GetSize(1));
    		assertEquals(7, _stack.GetSize(3));
    		assertEquals(8, _stack.GetSize(6));
    	}
    
    	@Test
    	public void SetupFlabjacksInvalidTest() {
    		assertEquals(0, _stack.GetSize(0));
    		assertEquals(0, _stack.GetSize(7));
    	}
    
    	@Test
    	public void FlipTest() {
    		_stack.Flip(3);
    		assertEquals(7, _stack.GetSize(6));
    		assertEquals(6, _stack.GetSize(5));
    		assertEquals(4, _stack.GetSize(4));
    		assertEquals(8, _stack.GetSize(3));
    	}
    
    	@Test
    	public void GetInputStackSizesTest() {
    		_stack.Flip(1);
    		assertEquals(2, _stack.getInputFlapjackSizes().get(1));
    		assertEquals(5, _stack.getInputFlapjackSizes().get(2));
    	}
    
    	@Test
    	public void IsOrderedTest() {
    		assertFalse(_stack.IsOrdered());
    
    		Integer[] flapjackSizes = { 1, 2, 3, 4 };
    		FlapjackStack stack = new FlapjackStack();
    		stack.SetupFlapjacks(Arrays.asList(flapjackSizes));
    		assertTrue(stack.IsOrdered());
    	}
    
    
    	@Test
    	public void GetPositionSizeOrderOfTest() {
    		assertEquals(6, _stack.GetPositionSizeOrderOf(1));
    		assertEquals(3, _stack.GetPositionSizeOrderOf(2));
    	}
    
    
    	@Test
    	public void IsLocateLastSizeOrderOfTest() {
    		assertTrue(_stack.IsLocateLastSizeOrderOf(1));
    		assertFalse(_stack.IsLocateLastSizeOrderOf(2));
    		_stack.Flip(3);
    		assertTrue(_stack.IsLocateLastSizeOrderOf(2));
    	}
    
    	@Test
    	public void OrderManuallyTest() {
    		int order = 1;
    		assertTrue(_stack.IsLocateLastSizeOrderOf(order));
    		assertEquals(1, order);
    		_stack.Flip(1);
    
    		order++;
    
    		assertEquals(4, _stack.GetPositionSizeOrderOf(order));
    		_stack.Flip(4);
    		assertEquals(2, order);
    		_stack.Flip(2);
    
    		order++;
    
    		assertEquals(5, _stack.GetPositionSizeOrderOf(order));
    		_stack.Flip(5);
    		assertEquals(3, order);
    		_stack.Flip(3);
    
    		order++;
    
    		assertTrue(_stack.IsLocateLastSizeOrderOf(order));
    		assertEquals(4, order);
    		_stack.Flip(4);
    
    		order++;
    
    		assertTrue(_stack.IsLocateLastSizeOrderOf(order));
    		assertEquals(5, order);
    		_stack.Flip(5);
    
    		assertTrue(_stack.IsOrdered());
    	}
    
    	@Test
    	public void OrderImplTest() {
    		for (Integer order = 1; order < _stack.getInputFlapjackSizes().size(); order++) {
    			if (!_stack.IsLocateLastSizeOrderOf(order)) {
    				_stack.Flip(_stack.GetPositionSizeOrderOf(order));
    			}
    			_stack.Flip(order);
    		}
    		assertTrue(_stack.IsOrdered());
    	}
    
    	@Test
    	public void OrderTest() {
    		_stack.Order();
    		assertTrue(_stack.IsOrdered());
    	}
    
    	@Test
    	public void GetFlipPositionsTest() {
    		_stack.Order();
    		assertEquals(8, _stack.getFlipPositions().size());
    		assertEquals(1, _stack.getFlipPositions().get(0));
    		assertEquals(4, _stack.getFlipPositions().get(1));
    		assertEquals(2, _stack.getFlipPositions().get(2));
    		assertEquals(5, _stack.getFlipPositions().get(3));
    		assertEquals(3, _stack.getFlipPositions().get(4));
    		assertEquals(4, _stack.getFlipPositions().get(5));
    		assertEquals(5, _stack.getFlipPositions().get(6));
    		assertEquals(0, _stack.getFlipPositions().get(7));
    	}
    
    	@Test
    	public void NoNeedFlipTest() {
    		Integer[] flapjackSizes = { 3, 2, 1, 8, 9 };
    		_stack.SetupFlapjacks(Arrays.asList(flapjackSizes));
    		_stack.Order();
    		assertEquals(2, _stack.getFlipPositions().size());
    		assertEquals(3, _stack.getFlipPositions().get(0));
    		assertEquals(0, _stack.getFlipPositions().get(1));
    	}
    
    	@Test
    	public void DuplicatedTest() {
    		Integer[] flapjackSizes = { 1, 1, 2, 2, 4, 4, 3 };
    		_stack.SetupFlapjacks(Arrays.asList(flapjackSizes));
    		_stack.Order();
    		assertEquals(6, _stack.getFlipPositions().size());
    		assertEquals(3, _stack.getFlipPositions().get(0));
    		assertEquals(1, _stack.getFlipPositions().get(1));
    		assertEquals(6, _stack.getFlipPositions().get(2));
    		assertEquals(2, _stack.getFlipPositions().get(3));
    		assertEquals(4, _stack.getFlipPositions().get(4));
    		assertEquals(0, _stack.getFlipPositions().get(5));
    	}
    }

kukuman

  • 해결 방법

    • flip의 동작을 구현하여 테스트함
    • 스택의 양끝으로 부터 중간으로 포인터를 이동하면서 왼쪽 끝이 오른쪽 끝보다 작은지 검사
      • 만약 다르다면 flip 수행 수행하며 결과 출력
      • 각 포인터가 교차 될때까지(모든비교가 완료된 시점)이면 검사종료

  • 코드

      import java.io.IOException;
  import java.util.ArrayList;
  import java.util.Scanner;
  
  class Main implements Runnable{
      static String ReadLn(int maxLength){  // utility function to read from stdin,
                                            // Provided by Programming-challenges, edit for style only
          byte line[] = new byte [maxLength];
          int length = 0;
          int input = -1;
          try{
              while (length < maxLength){//Read untill maxlength
                  input = System.in.read();
                  if ((input < 0) || (input == '\n')) break; //or untill end of line ninput
                  line [length++] += input;
              }
  
              if ((input < 0) && (length == 0)) return null;  // eof
              return new String(line, 0, length);
          }catch (IOException e){
              return null;
          }
      }
  
      public static void main(String args[])  // entry point from OS
      {
      	Main myWork = new Main();  // Construct the bootloader
          myWork.run();            // execute
      }
  
      public void run() {
      	ArrayList<String> result = new ArrayList<String>();
      	String line;
      	while((line = ReadLn(5000)) != null){
      		Flapjacks cakes = new Flapjacks(line);
      		result.add(line.trim());
      		result.add(cakes.getSortResult());
      	}
      	for(String curLine : result){
      		System.out.println(curLine);
      	}
      
      }
  }
  
  
  class Flapjacks implements Runnable{
  	private int [] cakes;
  	public Flapjacks(String line){
  		Scanner scan = new Scanner(line);
  		ArrayList<Integer> list = new ArrayList<Integer>();
  		while(scan.hasNext()){
  			list.add(scan.nextInt());
  		}
  		cakes = new int[list.size()];
  		int i=0;
  		for(Integer data : list){
  			cakes[i++] = data;
  		}
  	}
  	public Flapjacks(int[] cakes) {
  		this.cakes = cakes;
  	}
  
  	public void flip(int flipPos) {
  		if(cakes.length < flipPos || flipPos ==0){
  			return;
  		}
  		int i=0;
  		int j= cakes.length - flipPos;
  		while(i<j){
  			int temp = cakes[i];
  			cakes[i] = cakes[j];
  			cakes[j] = temp;
  			i++;
  			j--;
  		}
  	}
  
  	public int[] getCakes() {
  		return cakes;
  	}
  
  	public int getFlipPos() {
  		int result =1;
  		for(int i=0,j=cakes.length-1;i<j;i++,j--){
  			if(cakes[j] < cakes[i]){
  				return result;
  			}
  			result++;
  		}
  		return 0;
  	}
  
  	public String getSortResult() {
  		int pos = getFlipPos();
  		String result = new Integer(pos).toString();
  		while(pos != 0){
  			flip(pos);
  			pos = getFlipPos();
  			result = result+" "+pos;
  		}
  		return result;
  	}
  
  	public void run() {
  		
  	}
  
  }

  • 테스트 케이스

      import java.util.Arrays;
  
  import junit.framework.TestCase;
  
  
  public class FlapjascksTest extends TestCase {
  	
  	public void testFlip(){
  		int[] data1 = {8,4,6,7,5,2};
  		int[] data2 = {7,6,4,8,5,2};
  		int[] data3 = {2,5,8,4,6,7};
  		Flapjacks cakes = new Flapjacks(data1);
  		cakes.flip(3);
  		assertTrue(Arrays.equals(data2, cakes.getCakes()));
  		cakes.flip(1);
  		assertTrue(Arrays.equals(data3, cakes.getCakes()));
  	}
  	
  	public void testGetFlipPos(){
  		int[] data1 = {1,2,3,4,5};
  		Flapjacks cakes = new Flapjacks(data1);
  		assertEquals(0, cakes.getFlipPos());
  		
  		int[] data2 = {5,4,3,2,1};
  		Flapjacks cakes2 = new Flapjacks(data2);
  		assertEquals(1, cakes2.getFlipPos());
  
  		int[] data3 = {4,3,2,1,5};
  		Flapjacks cakes3 = new Flapjacks(data3);
  		assertEquals(2, cakes3.getFlipPos());
  	}
  	
  	public void testGetSortResult(){
  		int [] data1 = {1, 2, 3, 4, 5};
  		Flapjacks cakes = new Flapjacks(data1);
  		assertEquals("0", cakes.getSortResult());
  
  		int[] data2 = {5,4,3,2,1};
  		Flapjacks cakes2 = new Flapjacks(data2);
  		assertEquals("1 0", cakes2.getSortResult());
  
  		int[] data3 = {5,1,2,3,4};
  		Flapjacks cakes3 = new Flapjacks(data3);
  		assertEquals("1 2 0", cakes3.getSortResult());
  	}
  	public void testInit(){
  		int[] data3 = {5,1,2,3,4};
  		Flapjacks cakes3 = new Flapjacks("5 1 2 3 4");
  		assertTrue(Arrays.equals(data3, cakes3.getCakes()));
  		
  	}
  }

Mastojun

  • (비토와 친척들도 마찬가지지만)작년에 한번 풀어봤던거여서 문제를 보니 어떻게 풀었는지 기억나서 그대로 작성했습니다. 하지만 작년에 작성했던 코드를 보니 코드가 너무 다르더군요 ^^;

  • 역시 테스트는 적용하지 않았습니다. 모임에 나가서 배워와야겠어요.

      #include <stdio.h>
  #include <stdlib.h>
  #include <string.h>
  
  char Input[200];
  int count;
  int PanCake[31];
  
  void InputPanCake()
  {
  	char *word;
  	count = 0;
  
  	word = strtok(Input," ");
  	while(word != NULL)
  	{
  		PanCake[count] = atoi(word);
  
  		word = strtok(NULL, " ");
  		count++;
  	}	
  }
  
  void Reverse(int s, int e)
  {
  	int temp;
  	while( s < e )
  	{
  		temp = PanCake[s];
  		PanCake[s] = PanCake[e];
  		PanCake[e] = temp;
  		s++;
  		e--;
  	}
  }
  
  void CalResult()
  {
  	int CompleteStak = 1;
  	int BiggerNum;
  	int BiggerIndex;
  
  	while( CompleteStak < count )
  	{
  		BiggerNum = PanCake[count-CompleteStak];
  		BiggerIndex = count-CompleteStak;
  		for(int i = count-CompleteStak; i >= 0; --i )
  		{
  			if( BiggerNum < PanCake[i] )
  			{
  				BiggerNum = PanCake[i];
  				BiggerIndex = i;
  			}
  		}
  
  		if( BiggerIndex == 0 )
  		{
  			printf("%d ", CompleteStak);
  			Reverse(0, count-CompleteStak);
  		}
  		else if( BiggerIndex != count-CompleteStak )
  		{
  			printf("%d ", count-BiggerIndex);
  			Reverse(0, BiggerIndex);
  			CompleteStak--;
  		}
  		CompleteStak++;
  	}
  
  }
  
  int main()
  {
  	while( gets(Input) && Input[0] )
  	{
  		puts(Input);
  		InputPanCake();
  		CalResult();
  		printf("0\n");
  	}
  
  	return 0;
  }

Outbreak

문제 요약

  • 스택의 특정 위치부터 Top 까지를 통째로 뒤집어 가며 작은 수가 스택의 위에 큰 수가 스택의 아래에 위치하도록 정렬하는 문제

문제 해결

  • 일전에 풀어본 문제라 다른 풀이 방법으로 시도
    • 최초 입력 값을 정렬한 다음 문자열 패턴으로 만듬
    • 정렬된 문자열 패턴과 일치하는 값을 찾기 위해 백트래킹 해가며 모든 경우를 찾음
    • 이 알고리즘은 '''실패'''

기타

  • 으아.. 괜히 재귀형태로 만들어서 낭패
  • 연산을 줄일 방책을 생각해야 함. 입력값이 5개만 되도 처리 시간이 엄청 길다.

코드

    using System;
    using System.Collections.Generic;
    using System.Text;
    
    // 정렬된 결과를 찾는다
    
    // 정렬된 결과 패턴이 나올 때까지 반복
    
    // 만약 처음 패턴 또는 중간에 이미 구한 패턴이 나타나면 중지 
    
    // 최대 패턴 수는 숫자 개수의 순열이므로 n!
    
    namespace PanCake
    { 
        class Solver
        {
            List<List<string>> 추적로그 = new List<List<string>>();
            List<List<int>> 답 = new List<List<int>>();
    
            string goal = "";
    
            public Solver(int[] array)
            {
                int[] tmpArray = new int[array.Length];
                Array.Copy(array, tmpArray, array.Length);
                Array.Sort<int>(tmpArray);
    
                foreach (int i in tmpArray)
                {
                    goal += i;
                }
            }
    
            public void Flip(Stack<int> a, int pos)
            {
                int popCnt = a.Count - pos;
    
                List<int> list = new List<int>();
    
                while (popCnt-- >= 0)
                {
                    list.Add(a.Pop());
                }
    
                foreach (int i in list)
                {
                    a.Push(i);
                }
            }
    
            void Solve(int[] array, int pos, string[] traceArray, int[] tracePosArray)
            {
                Stack<int> stack = new Stack<int>(array);
                List<string> trace = new List<string>(traceArray);
                List<int> tracePos = new List<int>(tracePosArray);
    
                Flip(stack, pos);
    
                string traceString = "";
                foreach (int i in stack)
                {
                    traceString += i;
                }
    
                if (traceString == goal)
                {
                    trace.Add(traceString);
                    tracePos.Add(pos);
    
                    추적로그.Add(new List<string>(trace));
                    답.Add(new List<int>(tracePos));
    
                    return;
                }
    
                foreach (string s in trace)
                {
                    if (s == traceString)
                    {
                        return;
                    }
                }
    
                trace.Add(traceString);
                tracePos.Add(pos);
    
                int[] tmpArray = stack.ToArray();
                Array.Reverse(tmpArray);
    
                string[] tmpTraceArray = trace.ToArray();
                int[] tmpTracePosArray = tracePos.ToArray();
    
                for (int i = 1; i < stack.Count; i++)
                {
                    Solve(tmpArray, i, tmpTraceArray, tmpTracePosArray);
                }
            }
    
            public static List<List<int>> Exec(int[] array)
            {
                Array.Reverse(array);
    
                Solver solver = new Solver(array);
    
                for (int i = 1; i <= array.Length; i++)
                {
                    solver.Solve(array, i, (new List<string>()).ToArray(), (new List<int>()).ToArray());
                }
    
                return solver.답;
            }
    
        }
        
        class Program
        {
            static void Main(string[] args)
            {          
                Solver.Exec(new int[] { 1, 3, 2 });
            }
        }
    }
Clone this wiki locally