Sep 23 2008

간단한 문제…(연속된 숫자 그룹 맺어주기)

분류: DS/Algorithm 태그: ,Heart @ 11:25 오후

Trackback : http://dev.heartsavior.net/archives/219/trackback/

프로그래밍 갤러리에서 간단한 문제가 하나 올라오길래 오랜만에 C 코딩도 해볼 겸 풀어봤다.

문제 정의)
입력 : 1 2 3 10 11 12 13 19 199 200 201 202 300 305 499
출력 : 1-3, 10-13, 19, 199-202, 300, 305, 499.

연속된 숫자가 입력될 때 해당 숫자의 범위를 ‘-’ 로 이어주는 문제이다.
숫자 혹은 범위 간에는 ‘,’ 를 출력하고, 마지막 출력은 ‘.’ 이다.
입력 숫자는 1<=i<=500 이고, 입력 갯수는 1<=n<=500 이다.

내가 푼 답)

@ codepad 사이트에 입력한 코드

새로 들어오는 값이 마지막으로 들어온 값과 연속되는 값인지만 체크하면 문제가 될 만한 것은 없다.
나머지는 다 입출력의 문제…

#include <cstdio>
#include <cstdlib>
#include <cstring>
 
const char * DELIMETER = " ";
 
int main(void)
{
	char pszInput[] = "1 2 3 10 11 12 13 19 199 200 201 202 300 305 499";
 
	char * token = strtok(pszInput, DELIMETER);
 
	bool bFirstNumber = true;		// for check ',' print
	bool bContinue = false;			// for check continuous
	int nLastNumber = -10;			// Should not continue the first input
 
	while( NULL != token )
	{
		int nCurrentNumber = atoi(token);
 
		if( (nLastNumber + 1) == nCurrentNumber )
		{
			// continuous number
			bContinue = true;
		}
		else
		{
			if( bContinue )
			{
				// print last
				printf("-%d", nLastNumber);
 
				bContinue = false;
			}
 
			if( bFirstNumber )
			{
				printf("%d", nCurrentNumber);
				bFirstNumber = false;
			}
			else
				printf(",%d", nCurrentNumber);
 
		}
 
		nLastNumber = nCurrentNumber;
 
		token = strtok( NULL, DELIMETER );
	}
 
	printf(".");
 
	return 0;
}
</cstring></cstdlib></cstdio>

Jun 12 2008

바람개비 별찍기(for 문 2개 이용)

분류: DS/Algorithm 태그: ,Heart @ 1:30 오전

Trackback : http://dev.heartsavior.net/archives/144/trackback/

@ 바람개비 떡밥

이제는 바야흐로 삼각형 별찍기의 시대가 가고 바람개비 별찍기의 시대가 오나보다.

이걸 뭐 for문을 2개 쓰니 4개 쓰니 말이 많은데, 어거지를 발휘하면 2개로 가능하다.
(물론 패턴 분석이 필요하지만…)

여러 방법이 있을 것 같은데, 직관적인 방법은 삼각형 4개를 쪼개서 각각을 생각하는 것인 것 같다.
그래서 사분면을 나누고, 각 사분면에 따라 *을 찍느냐 공백을 찍느냐를 판별하였다.

#include <stdafx .h>
#include <iostream>
using namespace std;
 
int _tmain(int argc, _TCHAR* argv[])
{
	int size;
	cout < < "Enter a size:" << endl;
	cin >> size;
 
	for( int i = 0 ; i < 2 * size ; i++)
	{
		for( int j = 0 ; j < 2 * size ; j++)
		{
			int iQuadrant = 1;
 
			// 사분면 판정
			if( i < size && j <= size )
				iQuadrant = 1;
			else if( i < size && j < size )
				iQuadrant = 2;
			else if( i >= size && j < size )
				iQuadrant = 3;
			else
				iQuadrant = 4;
 
			// 사분면에 따라 '*' 인지 ' ' 인지 결정하는 로직이 다름
			switch( iQuadrant )
			{
			case 1:
				if( ( (j - size) - (size - 1) + i) >= 0 )
					cout < < "*";
				else
					cout << " ";
 
				break;
 
			case 2:
				if( i > j )
					cout < < " ";
				else
					cout << "*";
 
				break;
 
			case 3:
				if( ( (i - size) - (size - 1) + j) <= 0 )
					cout << "*";
				else
					cout << " ";
				break;
 
			case 4:
				if( (i - size) < (j - size) )
					cout << " ";
				else
					cout << "*";
 
				break;
 
			}
 
		}
 
		cout << endl;
	}
 
	return 0;
}


May 23 2008

자기복제수 문제

분류: DS/Algorithm 태그: ,, Heart @ 3:18 오후

Trackback : http://dev.heartsavior.net/archives/142/trackback/

프로그래밍 갤러리에서 다시 자기복제수 떡밥이 돌길래 덥썩 물고 구현해 봤다.
(참고로 자기복제수란, N을 제곱했을 때 맨 뒷자리에 N이 다시 나타나는 수를 말한다. 예를 들어, 76은 자기복제수이다. 76 * 76 = 57′76′ 이기 때문이다.)

프갤의 떡밥은 자기복제수를 계속 찾아나가면서 몇이 나왔을 때 사양이 어떻게 되고 몇 ms 가 걸렸는지인데, 난 그냥 회사에서 잠깐 짬 내서 하는 것이니까 구글링하다 찾은 문제의 스펙대로만 풀었다. 그래서 큰 수의 처리도 없고(N의 제곱이 INT_MAX보다 작아야 함) 처리 속도도 크게 신경 안썼다. 감으로 바로 떠오른 알고리즘을 통해 풀어 보았다.

package practice;
 
import java.util.Scanner;
 
/**
 * '자기복제수' 체크<br />
 * <br />
 * 자기복제수 : 어떤 자연수 N 을 제곱했을 때, 그 제곱수의 맨 뒷자리에 원래의 수 N이 다시 나타나는 경우<br />
 * 그 수 N을 자기복제수라고 한다.<br />
 * <br />
 * 입력<br />
 * 입력은 표준입력(standard input)을 통해 받아들인다. <br />
 * 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 20)가 주어진다. <br />
 * 각 테스트 케이스는 한 줄로 이루어져 있으며 자연수 N (1 ≤ N ≤ 1000) 이 주어진다.<br />
 * <br />
 * 출력<br />
 * 출력은 표준출력(standard output)을 통하여 출력한다. <br />
 * 각 테스트 케이스에 대해, 주어진 자연수가 자기복제수이면 YES를 아니면 NO를 출력한다.<br /> 
 */
public class PracticeSelfCloning {
	public static final int MAX_INPUT_NUM = 1000;
	public static final int MIN_INPUT_NUM = 1;
 
	public static final int MAX_INPUT_COUNT = 20;
	public static final int MIN_INPUT_COUNT = 1;
 
	private int inputCount = 0;
	private int[] inputDataList = null;
 
	public PracticeSelfCloning() {
		inputCount = 0;
		inputDataList = null;
	}
 
	public boolean inputData( ) {
		Scanner scan = new Scanner(System.in);
		inputCount = scan.nextInt();
 
		if( inputCount > MAX_INPUT_NUM || inputCount < MIN_INPUT_COUNT ) {
			System.err.println("테스트 케이스의 갯수가 " + MIN_INPUT_COUNT + 
					"<=T<=" + MAX_INPUT_COUNT + " 을 만족하지 않습니다.");
			return false;
		}
 
		inputDataList = new int[inputCount];
 
		for( int i = 0 ; i < inputCount ; i++ ) {
			inputDataList[i] = scan.nextInt();
 
			if( inputDataList[i] > MAX_INPUT_NUM || inputDataList[i] < MIN_INPUT_NUM ) {
				System.err.println("테스트 케이스가 " + MIN_INPUT_NUM + 
						"<=N<=" + MAX_INPUT_NUM + " 을 만족하지 않습니다.");
				return false;
			}
		}
 
		scan.close();
 
		return true;
	}
 
	public void printCheckSelfCloning() {
 
		for ( int i = 0 ; i < inputCount ; i++ ) {
			if( checkSelfCloning( inputDataList[i] ) )
				System.out.println("YES");
			else
				System.out.println("NO");
		}
	}
 
	private boolean checkSelfCloning(int value) {
		int squareVal = value * value;
		int valueOri = value;
 
		/* 
		 * 알고리즘 : 원래의 수를 N이라 하고 N의 자릿수를 c라 하면,
		 * N^2를 10^c로 나눈 나머지가 N이 되어야 자기복제 수이다.
		 */
		int modVal = 10;
		int valueCipher = 1;
		while( value / 10 > 0 ) {
			valueCipher++;
			value = value / 10;
			modVal = modVal * 10;
		}
 
		int mod = squareVal % modVal;
		if( mod == valueOri )
			return true;
 
		return false;
	}
 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		if( !checkCondition() )
			return;
 
		PracticeSelfCloning selfCloning = new PracticeSelfCloning();
 
		selfCloning.inputData();
		selfCloning.printCheckSelfCloning();		
	}
 
	public static boolean checkCondition() {
		// MAX_INPUT_NUM * MAX_INPUT_NUM 이 int 의 한계를 넘어설 경우를 체크
		if( Integer.MAX_VALUE / MAX_INPUT_NUM < MAX_INPUT_NUM ) {
			System.err.println("MAX_INPUT_NUM 의 값을 낮추거나 BigInteger를 사용해야 합니다.");
			return false;
		}
 
		// MAX_INPUT_COUNT 는 체크할 필요 없음 -> 컴파일 시에 오버플로우 체크
		return true;
	}
}

아마도 많은 최적화 방법이 있지 않을까 생각한다.


뒷 쪽 »