뿡야의 IT 기록

문제

세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오.

예를 들어 A = 150, B = 266, C = 427 이라면 A × B × C = 150 × 266 × 427 = 17037300 이 되고, 계산한 결과 17037300 에는 0이 3번, 1이 1번, 3이 2번, 7이 2번 쓰였다.

입력

첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다.

출력

첫째 줄에는 A × B × C의 결과에 0 이 몇 번 쓰였는지 출력한다. 마찬가지로 둘째 줄부터 열 번째 줄까지 A × B × C의 결과에 1부터 9까지의 숫자가 각각 몇 번 쓰였는지 차례로 한 줄에 하나씩 출력한다.

풀이

• 첫번째 풀이

//2577
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int n = A * B * C;
		String str = Integer.toString(n);
		
		for (int i = 0; i < 10; i++) {
			int count = 0;
			for (int j = 0; j < str.length(); j++) {
				if ((str.charAt(j) - '0') == i) {
					count++;
				}
			}
			System.out.println(count);
		}
		sc.close();
	}
}

• 두번째 풀이

//2577
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		String str = Integer.toString(A * B * C);
		int[] m = new int[10];
		
		for (int i = 0; i < str.length(); i++) {
			m[(str.charAt(i) - 48)]++;
		}
		
		for (int i = 0; i < 10; i++) {
			System.out.println(m[i]);
		}
		
		sc.close();
	}
}

문제

첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

첫째 줄부터 N번째 줄까지 차례대로 별을 출력한다.

풀이

이중 반복문을 사용하였다.

i가 증가한 만큼 별을 찍도록 하였다.

//2438
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < i + 1; j++) {
				System.out.print("*");
			}
			System.out.println();
		}
		
		sc.close();
	}
}

문제

알파벳 소문자로만 이루어진 단어 S가 주어진다. 각 알파벳이 단어에 몇 개가 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다.

출력

단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다.

풀이

• 아스키 코드를 사용하였다.
• 새로 배운 함수 -> charAt()

charAt() 함수는 문자열 중 한 글자만 선택해서 문자 형태로 바꿔주는 함수이다.

//10808
import java.util.*;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		String str = sc.next();
		int[] n = new int[26];
		
		for (int i = 0; i < str.length(); i++) {
			n[str.charAt(i) - 97]++;
		}
		
		for (int i = 0; i < 26; i++) {
			System.out.print(n[i] + " ");
		}
		
		sc.close();
	}
}

참고

https://colossus-java-practice.tistory.com/31

문제

두 수 A, B를 입력받아, A+B, A-B, A×B를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 A가, 둘째 줄에 B가 주어진다. 각각의 수는 10진수로 1,000자리를 넘지 않으며 양수와 음수가 모두 주어질 수 있다.

출력

첫째 줄에 A+B, 둘째 줄에 A-B, 셋째 줄에 A×B를 출력한다. 각각을 출력할 때, 답이 0인 경우를 제외하고는 0으로 시작하게 해서는 안 된다(1을 01로 출력하면 안 된다는 의미).

풀이

큰 숫자를 다루기 위해 BigInteger형으로 정수를 입력받았다.

//2338
import java.util.Scanner;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		BigInteger A = sc.nextBigInteger();
		BigInteger B = sc.nextBigInteger();
		
		System.out.print(A.add(B) + "\n" + A.subtract(B) + "\n" + A.multiply(B));
		
		sc.close();
	}
}

문제

입력

출력

풀이

• 첫번째 풀이

단순하게 접근하여 Int형으로 정수를 입력받아 나눗셈과 나머지를 사용하였다.

// 1271
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		sc.close();
		
		System.out.println(n/m);
		System.out.println(n%m);
	}
}

이 코드는 더 큰 정수를 처리할 수 없어 런타임 에러가 발생하였다.

• 두번째 풀이

더 큰 정수를 처리하기 위해 BigInteger형으로 정수를 입력받았다.

BigInteger n = sc.nextBigInteger();
BigInteger m = sc.nextBigInteger();

이렇게 설정하게 되면 /나 %연산자를 사용할 수 없기 때문에 divide() 메소드와 remainder()메소드를 사용했다.

// 1271
import java.util.Scanner;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		BigInteger n = sc.nextBigInteger();
		BigInteger m = sc.nextBigInteger();
		
		sc.close();
		
		System.out.println(n.divide(m));
		System.out.println(n.remainder(m));
	}
}

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

풀이

처음에 푼 방식

n부터 m까지 x에 대해 1부터 x까지 소수를 판별하는 방법으로 코드를 짰다. 그러나 이 코드는 시간 초과로 실패하였다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

int isPrime(int a)
{
	int cnt = 0;

	for (int i = 1; i <= a; i++)
		if (a % i == 0)
			cnt++;

	if (cnt == 2)
		return 1;
	else
		return 0;
}

int main(void)
{
	int n, m;

	scanf("%d %d", &n, &m);

	for (int i = n; i <= m; i++) {
		if (isPrime(i) == 1)
			printf("%d\n", i);
		else
			continue;
	}

	return 0;
}

무엇이 잘못되었을까 검색을 해봤는데 이 문제는 에라토스테네스의 체 알고리즘을 이용해야한다는 것을 알아냈다.

두번째로 푼 방식

소수:  1과 자기 자신으로만 나눠지는 숫자

에라토스테네스의 체: 소수를 빠르게 찾는 방법이다.

에라토스테네스의 체를 이용하여 소수를 찾는 순서 >>

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다.
2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색)
3. 자기 자신을 제외한 2의 배수를 모두 지운다.
4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색)
5. 자기 자신을 제외한 3의 배수를 모두 지운다.
6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색)
7. 자기 자신을 제외한 5의 배수를 모두 지운다.
8. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. (노란색)
9. 자기 자신을 제외한 7의 배수를 모두 지운다.
10. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. (보라색)

이 방식을 사용하면 1부터 자기 자신까지 소수를 판별하지 않아 시간을 단축할 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

int main(void)
{
	int n, m;
	int primeNum[1000001] = {0, 1};

	scanf("%d %d", &n, &m);

	for (int i = 2; i <= m; i++)
		for (int j = 2; j * i <= m; j++)
			primeNum[j * i] = 1;

	for (int i = n; i <= m; i++)
		if (primeNum[i] == 0)
			printf("%d\n", i);

	return 0;
}

참고글1

참고글2

참고글3

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

풀이

최소공배수는 두 수를 곱한 후 최대공약수로 나누면 구할 수 있다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int a, b;
	int i, j;

	scanf("%d %d", &a, &b);

	// 최대공약수 구하기

	if (a < b)
		i = a;
	else
		i = b;

	while (1) {
		if (a % i == 0 && b % i == 0)
			break;
		else
			i--;

		if (i == 1)
			break;
	}

	printf("%d\n", i);
	printf("%d", (a * b) / i);

	return 0;
}

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

자연수 N이 주어졌을 때, g(N)을 구해보자.

풀이

처음에 푼 방식

1부터 N까지 하나씩 약수를 확인한 후 약수의 합을 구했다. i가 1부터 4까지, j가 1부터 i까지 도는 이중 for문을 사용하였다. 

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int N;
	int sum = 0;

	scanf("%d", &N);

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= i; j++) {
			if (i % j == 0)
				sum += j;
		}
	}

	printf("%d\n", sum);

	return 0;
}

그러나 이 방식은 시간 초과로 실패하였다. 

두 번째 푼 방식

몫을 활용한다.

예를 들어, N을 5로 가정

5 이하의 수 중 1을 약수로 가지는 수의 개수: 5

5 이하의 수 중 2을 약수로 가지는 수의 개수: 2

5 이하의 수 중 3을 약수로 가지는 수의 개수: 1

5 이하의 수 중 4을 약수로 가지는 수의 개수: 1

5 이하의 수 중 5을 약수로 가지는 수의 개수: 1

여기서 개수는 5를 어떤 수로 나눴을 때, 몫이 된다. >> N / i

N = 5, g(N) = 21

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
	int N;
	long long sum = 0;

	scanf("%d", &N);

	for (int i = 1; i <= N; i++) {
		sum += (N / i) * i;
	}

	printf("%d\n", sum);

	return 0;
}

문제

9095번을 숫자 하나를 입력하면 순서를 고려하지 않은 더하기 경우의 수를 출력하도록 변형했다.

입력

• 4

출력

• 5

경우의 수 >>

1 + 1 + 1 + 1

1 + 1 + 2

1 + 3

2 + 2

4

풀이

풀이 핵심

>> 조합 사용

1) bucket 정보

    n개의 공간 동적으로 할당

2) 경우의 수를 셀 전역 변수 사용

    pick 함수 내에서 변수를 선언한다면 재귀 호출이 되었을 때 0으로 돌아가기 때문에 전역변수로 받았다. 물론 함수 매개변수로 받아도 문제는 없다. 

// 1, 2, 3 더하기 쉽게 변형
// 중복 조합
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

int result = 0;

void pick(int n, int* bucket, int m, int k)
{
	int i, lastIndex, smallest;
	int total = 0;

	lastIndex = m - k - 1;

	for (i = 0; i <= lastIndex; i++)
		total += bucket[i] + 1;

	if (total == n) { // 다 뽑았으면
		result++;
		return;
	}
	else if (total > n)
		return;

	if (m == k)
		smallest = 0;
	else
		smallest = bucket[lastIndex];

	for (i = smallest; i < n; i++) {
		bucket[lastIndex + 1] = i;
		pick(n, bucket, m, k - 1);
	}
}

int main(void)
{
	int n;
	int* bucket;

	scanf("%d", &n);
	bucket = (int*)malloc(sizeof(int) * n);

	pick(n, bucket, n, n);
	printf("%d\n", result);

	return 0;
}

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

// selection sort
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <stdlib.h>

void selectionSort(int* A, int n)
{
	int i, j;
	int max, max_index;

	for (i = 0; i < n - 1; i++) {
		max = A[0];
		max_index = 0;

		for (j = 1; j < n - i; j++) {
			if (max < A[j]) {
				max = A[j];
				max_index = j;
			}
		}

		A[max_index] = A[n - 1 - i];
		A[n - 1 - i] = max;
	}
}

int main(void)
{
	int* A;
	int n; 

	scanf("%d", &n);

	A = (int*)malloc(sizeof(int) * n);
	if (!A)
		return 0;

	for (int i = 0; i < n; i++)
		scanf("%d", &A[i]);

	selectionSort(A, n);

	for (int i = 0; i < n; i++)
		printf("%d\n", A[i]);

	free(A);
	return 0;
}

풀이

선택정렬(selection sort) 활용