algorithm reverse and add - andstudy/forge GitHub Wiki

Mastojun

문제 풀이

숫자를 입력받아, 그 숫자를 뒤집고 서로 더해서 회문인지 검사하는 문제입니다. 정수형 변수를 가지고 이러한 작업을 하기 위해서는 나누기 곱하기 나머지 등의 산수를 복잡하게 사용해야 해서 문자열의 힘을 빌려 풀었습니다.

소스코드 (ANSI C)

    #include <stdio.h>
    #include <string.h>
    
    int isOk(char *P)
    {
    	int len = strlen(P) - 1;
    	int i;
    
    	for(i = 0; i <= len/2; i++ )
    	{
    		if( P[i] != P[len-i] ) return 0;
    	}	
    
    	return 1;
    }
    
    void Reverse(char *P)
    {
    	int i;
    	char TempP[11]={0};
    	int len = strlen(P)-1;
    
    	for(i = 0; P[i]; ++i )
    	{
    		TempP[len-i] = P[i];
    	}
    
    	strcpy(P, TempP);
    }
    
    void ReverseAdd(char *P)
    {
    	int i;
    	char TempP[11];
    	int carry = 0;
    
    	strcpy(TempP, P);
    	Reverse(TempP);
    
    	for(i = 0; P[i]; ++i )
    	{
    		P[i] = P[i]-'0'+TempP[i]-'0'+carry;
    		if(P[i] >= 10 )
    		{
    			P[i] -= 10;
    			carry = 1;
    		}
    		else
    		{
    			carry = 0;
    		}
    
    		P[i] += '0';
    	}
    
    	if(carry)
    	{
    		P[i] = carry+'0';
    		P[i+1] = 0;
    	}
    }
    
    int main()
    {
    	int N;
    	char P[11];
    	int result;
    	scanf("%d", &N);
    
    	while( N --> 0 )
    	{
    		scanf("%s", P);
    		Reverse(P);
    
    		result = 0;
    
    		while( !isOk(P) )
    		{
    			ReverseAdd(P);
    			result++;
    		}
    
    		printf("%d %s\n", result, P);
    	}
    
    	return 0;
    }

CynicJJ

입출력 처리 없음
각종 언어로 몇번이나 풀어봤던 문제
196 이 안된다는건 처음 알았음

!ReverseAndAdd.vb

    Public Class ReverseAndAdd
    
    	Private _count As Integer
    	ReadOnly Property Count() As Integer
    		Get
    			Return _count
    		End Get
    	End Property
    
    	Private _resultPalindrome As Integer
    	ReadOnly Property ResultPalindrome() As Integer
    		Get
    			Return _resultPalindrome
    		End Get
    	End Property
    
    	Sub Init()
    		_count = 0
    		_resultPalindrome = 0
    	End Sub
    
    	Function GetReversed(ByVal number As Integer) As Integer
    		Dim strNumber() As Char = String.Format("{0:D}", number).ToCharArray()
    		Array.Reverse(strNumber)
    		Return Integer.Parse(New String(strNumber))
    	End Function
    
    	Function IsPalindrome(ByVal number As Integer) As Boolean
    		Return (number = GetReversed(number))
    	End Function
    
    	Sub DoReverseAndAdd(ByVal number As Integer)
    		Init()
    
    		While Not IsPalindrome(number)
    			number += GetReversed(number)
    			_count += 1
    		End While
    
    		If IsPalindrome(number) Then
    			_resultPalindrome = number
    		End If
    	End Sub
    End Class

!ReverseAndAddTest.vb

    <TestClass()> _
    Public Class ReverseAndAddTest
    
    	<TestMethod()> _
    	Public Sub GetReversedTest()
    		Dim rna As ReverseAndAdd = New ReverseAndAdd
    		Assert.AreEqual(321, rna.GetReversed(123))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub IsPalindromeTest()
    		Dim rna As ReverseAndAdd = New ReverseAndAdd
    		Assert.IsTrue(rna.IsPalindrome(1221))
    	End Sub
    
    	<TestMethod()> _
    	Public Sub DoReverseAndAddTest()
    		Dim rna As ReverseAndAdd = New ReverseAndAdd
    		rna.DoReverseAndAdd(195)
    		Assert.AreEqual(4, rna.Count)
    		Assert.AreEqual(9339, rna.ResultPalindrome)
    	End Sub
    
    	<TestMethod()> _
    	Public Sub DoReverseAndAddTestMore()
    		Dim rna As ReverseAndAdd = New ReverseAndAdd
    
    		rna.DoReverseAndAdd(265)
    		Assert.AreEqual(5, rna.Count)
    		Assert.AreEqual(45254, rna.ResultPalindrome)
    
    		rna.DoReverseAndAdd(750)
    		Assert.AreEqual(3, rna.Count)
    		Assert.AreEqual(6666, rna.ResultPalindrome)
    	End Sub
    End Class

kukuman

계속 wrong answer이네요 ㅠㅠ 이리저리 고쳐보다 포기 ㅠㅠ
- UVa에 제출하면 Runtime Error가 발생하네요
- 온라인 판사님에겐 신경 끄기로 했는데 그게 잘 안되네요.
  - 51814 무한 루프 도는것 같은데
  - {{{double addend = getReverseNum(curSum);}}} 에서 long 으로 바꿔야 함
  - 그래도 wrong answer
- Solved 판정 받은 Mastojun님 풀이는 001과 1을 다르게 처리함
  - 혹시 이것 때문이라면 OTL
  - 작년에 제출했던 코드는 001과 1을 같게 처리하는데 Solved받았어요.

코드

  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  
  class Main implements Runnable{
  	public Long readLine(){
  		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
  		try {
  			return new Long( reader.readLine().trim() );
  		} catch (Exception e) {
  			return null;
  		}
  	}
  	public static void main(String[] args) {
  		Main myWork = new Main();  // Construct the bootloader
  		myWork.run();            // execute
  	}
  	
  	public void run() {
  		long caseCount = readLine().longValue();
  		for(int i=0;i<caseCount;i++){
  			String result = ReverseAdder.GetReverseResult(readLine().longValue());
  			System.out.println(result);
  		}
  	}
  }
  
  
  class ReverseAdder {
  	public static long getReverseNum(long num){
  		String strNum = new Long(num).toString();
  		StringBuilder builder = new StringBuilder();
  		for(int i=0;i<strNum.length();i++){
  			builder.insert(0,strNum.charAt(i));
  		}
  		return Long.parseLong(builder.toString());
  		
  	}
  
  	public static String GetReverseResult(long num) {
  		int loopCount =0;
  		long curSum = num;
  		while(curSum != getReverseNum(curSum)){
  			loopCount++;
  			double addend = getReverseNum(curSum);
  			curSum += addend;
  		}
  		return loopCount + " "+ curSum;
  	}
  }

테스트 케이스

  import junit.framework.TestCase;
  
  
  public class ReverseTestCase extends TestCase {
  	public void testGetReverse(){
  		assertEquals(123,  ReverseAdder.getReverseNum(321));
  		assertEquals(1234,  ReverseAdder.getReverseNum(4321));
  		assertEquals(3,  ReverseAdder.getReverseNum(3));
  		assertEquals(13,  ReverseAdder.getReverseNum(31));
  	}
  	public void testCheckPalindrome(){
  		assertEquals(123, ReverseAdder.getReverseNum(ReverseAdder.getReverseNum(123)));
  	}
  	
  	public void testGetReverseResult(){
  		assertEquals("4 9339", ReverseAdder.GetReverseResult(195));
  		assertEquals("5 45254", ReverseAdder.GetReverseResult(265));
  		assertEquals("3 6666", ReverseAdder.GetReverseResult(750));
  	}
  }

soomong

입력은 생략하였습니다. accept 받는것도 계속 생략하게 되네요 ^^;;

  public class ReverseAdd {
  
  	
  	public boolean isPalindrome(char[] num) {
  	
  		for(int i=0, j= num.length-1 ; i< num.length && i<=j ; i++, j--)		{
  
  			if( num[i] != num[j] )
  				return false;
  		}
  				
  		return true;	
  	}
  
  	public char[] reverse(char[] num) {
  		
  		char[] temp = new char[num.length];
  		
  		for(int i=0, j=num.length-1; i< num.length ; i++,j--) {
  			temp[j] = num[i];
  		}
  		
  		return temp;
  	}
  
  	public char[] add(char[] fir, char[] sec) {
  		
  		int result = Integer.parseInt(String.valueOf(fir)) + Integer.parseInt(String.valueOf(sec));
  		
  		return String.valueOf(result).toCharArray();
  	}
  
  
  
  	public int calReverseCount(char[] num) {
  	
  		int count =0;
  		
  		while(isPalindrome(num) == false && count < 1000 ) {
  		
  			num = add(num,reverse(num));
  			count++;
  			
  		}
  		
  		System.out.println(count+" "+ String.valueOf(num));
  		
  		return count;
  	}
  
  
  }



  import java.util.Arrays;
  
  import junit.framework.TestCase;
  
  
  public class ReverseAddTest extends TestCase {
  
  	ReverseAdd ra = new ReverseAdd();
  	
  	public void testIsPalindrome() {
  	
  		assertTrue(ra.isPalindrome(new char[] {'9','3','3','9'}));
  		assertFalse(ra.isPalindrome(new char[] {'9','2','3','3','9'}));
  		assertTrue(ra.isPalindrome(new char[] {'4','5','2','5','4'}));
  		assertTrue(ra.isPalindrome(new char[] {'6','6','6','6'}));
  		assertTrue(ra.isPalindrome(new char[] {'1'}));
  		assertFalse(ra.isPalindrome(new char[] {'1','2'}));
  	}
  	
  	public void testReverse() {
  		
  		assertTrue(Arrays.equals(ra.reverse(new char[] {'1','9','5'}),new char[] {'5','9','1'}));
  		assertTrue(Arrays.equals(ra.reverse(new char[] {'7','8','6'}),new char[] {'6','8','7'}));
  		assertTrue(Arrays.equals(ra.reverse(new char[] {'1','4','7','3'}),new char[] {'3','7','4','1'}));
  		assertTrue(Arrays.equals(ra.reverse(new char[] {'5','2','1','4'}),new char[] {'4','1','2','5'}));
  		assertFalse(Arrays.equals(ra.reverse(new char[] {'5','2','1','4'}),new char[] {'4','1','3','5'}));
  		assertTrue(Arrays.equals(ra.reverse(new char[] {'1'}),new char[] {'1'}));
  	}
  	
  	public void testAdd() {
  		assertTrue(Arrays.equals(ra.add(new char[] {'1','9','5'},new char[] {'5','9','1'}),new char[] {'7','8','6'}));
  		assertTrue(Arrays.equals(ra.add(new char[] {'7','8','6'},new char[] {'6','8','7'}),new char[] {'1','4','7','3'}));
  		assertTrue(Arrays.equals(ra.add(new char[] {'1','9'},new char[] {'5','9'}),new char[] {'7','8'}));
  		assertFalse(Arrays.equals(ra.add(new char[] {'1','0'},new char[] {'5','0'}),new char[] {'6','8'}));
  	}
  	
  	public void testCalReverseCount() {
  		assertEquals(4,ra.calReverseCount(new char[] {'1','9','5'}));
  		assertEquals(5,ra.calReverseCount(new char[] {'2','6','5'}));
  		assertEquals(3,ra.calReverseCount(new char[] {'7','5','0'}));
  		assertEquals(0,ra.calReverseCount(new char[] {'1','1','1'}));
  		assertEquals(0,ra.calReverseCount(new char[] {'1','1','1'}));
  	}
  	
  }

ParkPD

compile 에러랍니다. gcc 에서는 include 같은 걸 다르게 해 줘야 하나 보네요.
언제 GCC 쓰는 법 한 번 배워야 겠어요.

에러...

  In file included from /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/include/g++-v4/backward/strstream:51,
                   from pgdaemon.tmp.cpp:12:
  /usr/lib/gcc/i686-pc-linux-gnu/4.1.2/include/g++-v4/backward/backward_warning.h:32:2: warning: #warning This file includes at least one deprecated or antiquated header. Please consider using one of the 32 headers found in section 17.4.1.2 of the C++ standard. Examples include substituting the <X> header for the <X.h> header for C++ includes, or <iostream> instead of the deprecated header <iostream.h>. To disable this warning use -Wno-deprecated.
  pgdaemon.tmp.cpp:169:26: warning: no newline at end of file
  pgdaemon.tmp.cpp: In static member function 'static std::string CReverseAdder::ToString(int)':
  pgdaemon.tmp.cpp:84: error: '_itoa' was not declared in this scope

C언어 해더를 C++표준형식으로 바꾸셔야 합니다. stdlib.h -> cstdlib
itoa는 비표준입니다. gcc/g++에서는 구현되어 있지 않습니다.

소스코드의 마지막에는 빈줄이 꼭 있어야 합니다. 왜그런진 모르겠지만요

  /* @JUDGE_ID:parkpd 10038 C "test" */
  
  /* @BEGIN_OF_SOURCE_CODE */
  
  #define _CRT_SECURE_CPP_OVERLOAD_STANDARD_NAMES 1
  #define _CRT_SECURE_NO_DEPRECATE 1 
  
  #include <stdlib.h>
  #include <iostream>
  #include <vector>
  #include <set>
  #include <strstream>
  #include <algorithm>
  
  using namespace std;
  
  //#define _UNIT_TEST
  
  #ifdef _UNIT_TEST
  
  #include "../../UnitTest++/src/UnitTest++.h"
  
  int main()
  {
  	UnitTest::RunAllTests();
  
  	char temp;
  	cin >> temp;
  
  	return 0;
  }
  
  #endif
  
  class CReverseAdder
  {
  public:
  	static void GetOutput(int num, int& iter, int& palindrome);
  	static int MakeReverse(int num);
  	static bool IsPalindrome(int num);
  	static string ToString(int num);
  	static int ToInt(string s);
  };
  
  void CReverseAdder::GetOutput(int num, int& iter, int& palindrome)
  {
  	iter = 0;
  	while (!IsPalindrome(num))
  	{
  		num += MakeReverse(num);
  		iter++;
  	}
  	palindrome = num;
  }
  
  bool CReverseAdder::IsPalindrome(int num)
  {
  	string s = ToString(num);
  	const int size = s.size();
  	for (int i = 0; i < size / 2; ++i)
  	{
  		char a = s[i];
  		char b = s[size - i - 1];
  		if (a != b)
  		{
  			return false;
  		}
  	}
  
  	return true;
  }
  
  int CReverseAdder::MakeReverse(int num)
  {
  	string s = ToString(num);
  	reverse(s.begin(), s.end());
  	return ToInt(s.c_str());
  }
  
  std::string CReverseAdder::ToString( int num )
  {
  	// max : 4,294,967,295
  	char buffer[12];
  	_itoa(num, buffer, 10);
  	return string(buffer);
  }
  
  int CReverseAdder::ToInt( string s )
  {
  	return atoi(s.c_str());
  }
  
  #ifndef _UNIT_TEST
  
  int main()
  {
  	vector<int> testNums;
  
  	int count;
  	cin >> count;
  
  	int num;
  	for (int i = 0; i < count; ++i)
  	{
  		cin >> num;
  		testNums.push_back(num);
  	}
  
  	int iter;
  	int palindrome;
  	for (int i = 0; i < count; ++i)
  	{
  		CReverseAdder::GetOutput(testNums[i], iter, palindrome);
  		cout << iter << " " << palindrome << "\n";
  	}
  
  	return 0;
  }
  
  #else
  
  struct FixtureReverseAdder : public CReverseAdder
  {
  	int iter;
  	int palindrome;
  };
  
  TEST_FIXTURE(FixtureReverseAdder, ToStringToInt)
  {
  	string s = ToString(1423);
  	CHECK_EQUAL("1423", s);
  	int n = ToInt(s);
  	CHECK_EQUAL(1423, n);
  }
  
  TEST_FIXTURE(FixtureReverseAdder, MakeReverse)
  {
  	int n = 5214;
  	n = MakeReverse(n);
  	CHECK_EQUAL(4125, n);
  	n = MakeReverse(n);
  	CHECK_EQUAL(5214, n);
  }
  
  TEST_FIXTURE(FixtureReverseAdder, IsPalindrome)
  {
  	CHECK(!IsPalindrome(5214));
  	CHECK(IsPalindrome(9339));
  	CHECK(IsPalindrome(45254));
  }
  
  TEST_FIXTURE(FixtureReverseAdder, GetOutput)
  {
  	GetOutput(195, iter, palindrome);
  	CHECK_EQUAL(4, iter);
  	CHECK_EQUAL(9339, palindrome);
  
  	GetOutput(265, iter, palindrome);
  	CHECK_EQUAL(5, iter);
  	CHECK_EQUAL(45254, palindrome);
  
  	GetOutput(750, iter, palindrome);
  	CHECK_EQUAL(3, iter);
  	CHECK_EQUAL(6666, palindrome);
  }
  
  #endif
  
  /* @END_OF_SOURCE_CODE */

MovingSpotlight

1차 풀이

웹에서 검사는 안받았으나, wrong answer이지 않을까 싶네요...

  #include <iostream>
  #include <vector>
  
  #ifdef	_UNITTEST
  	#include "../UnitTest++/src/UnitTest++.h"
  	#include "../UnitTest++/src/TestReporterStdout.h"
  #endif	//_UNITTEST
  
  using namespace std;
  
  int GetReverseInt(int n)
  {
  	int reverse_int = 0;
  	int each_digit = 0;
  
  	while(n > 0)
  	{
  		reverse_int *= 10;
  		reverse_int += n % 10;
  		n /= 10;
  	}
  
  	return reverse_int;
  }
  
  bool IsPalindromeInt(int n)
  {
  	int org = n;
  	int cmp = GetReverseInt(n);
  
  	return (org == cmp);
  }
  
  bool GetCountMakePalindrome(int n, int *out_count, int *out_palindrome)
  {
  	bool bRet = true;
  	*out_count = 0;
  	*out_palindrome = 0;
  
  	int reverse_int = 0;
  	int temp_int = n;
  
  	while(1)
  	{
  		(*out_count)++;			
  
  		reverse_int = GetReverseInt(n);
  		temp_int = reverse_int + n;
  
  		if(!IsPalindromeInt(temp_int))		
  			n = temp_int;		
  		else
  		{
  			*out_palindrome = temp_int;
  			break;
  		}
  
  		if(*out_count >= 1000)
  		{
  			*out_count = 0;
  			*out_palindrome = 0;
  			bRet = false;
  			break;
  		}
  	}
  
  	return bRet;
  }
  
  int main()
  {
  #ifdef	_UNITTEST
  	UnitTest::RunAllTests();
  #endif	//_UNITTEST
  
  	return 0;
  }
  
  #ifdef	_UNITTEST
  //TEST(testSetUp)
  //{
  //}
  //TEST(testTearDown)
  //{
  //}
  
  TEST(testGetReverseInt)
  {
  	CHECK_EQUAL(321, GetReverseInt(123));
  	CHECK_EQUAL(591, GetReverseInt(195));
  }
  
  TEST(testIsPalindromeInt)
  {
  	CHECK_EQUAL(true, IsPalindromeInt(9339));
  	CHECK_EQUAL(false, IsPalindromeInt(9338));
  }
  
  TEST(testGetCountMakePalindrome)
  {
  	int count;
  	int palindrome;
  
  	CHECK_EQUAL(true, GetCountMakePalindrome(195, &count, &palindrome));
  	CHECK_EQUAL(4, count);
  	CHECK_EQUAL(9339, palindrome);
  }
  
  #endif	//_UNITTEST

algorithm reverse and add - andstudy/forge GitHub Wiki

Mastojun

문제 풀이

소스코드 (ANSI C)

CynicJJ

!ReverseAndAdd.vb

!ReverseAndAddTest.vb

kukuman

soomong

ParkPD

MovingSpotlight

1차 풀이

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️