아찌방 하우스

문제

정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다.

출력

N의 소인수분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

코드

import java.io.*;
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String args[]) throws IOException
	{
		/* 11653 소인수분해
		 * 정수 입력받아서 소인수 분해
		   */
		
		int n = sc.nextInt();
		
		for(int i = 2; i <= n;) //소인수는 1보다 큽니다, 그래서 2부터 시작
		{
			if(n%i == 0) // 나머지가 0이면 출력
			{
				n/=i;
				System.out.println(i);
			}
			else
			{
				i++;
			}
		}
			
	}
}ll

풀이

https://fall-in-dream.tistory.com/22

위의 문제랑 비슷한데

이 문제는 그냥 출략하면 되서 더 단순하다.

문제

정수 배열 array와 정수 n이 매개변수로 주어질 때, array에 들어있는 정수 중 n과 가장 가까운 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

제한사항

• 1 ≤ array의 길이 ≤ 100
• 1 ≤ array의 원소 ≤ 100
• 1 ≤ n ≤ 100
• 가장 가까운 수가 여러 개일 경우 더 작은 수를 return 합니다.

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

• 3, 10, 28 중 20과 가장 가까운 수는 28입니다.

입출력 예 #2

• 10, 11, 12 중 13과 가장 가까운 수는 12입니다.

코드

class Solution {
    public int solution(int[] array, int n) {
        
        int answer = 1000;
        int sub = 100; //n과의 거리가 현재 가장 가까운 값
        int temp = 0;
        
        for(int i = 0; i < array.length; i++)
        {
            temp = array[i] - n; //n과의 거리
            if(temp < 0) //음수이면 양수로 바꾸기 위해
            {
                temp*=-1; // Math.abs(arr[i] - i); 로 대체 가능합니다.
            }
            
        	if(temp < sub) // 현재 n과의 거리가 기존의 거리보다 가까우면
        	{
        		sub = temp;
        		answer = array[i]; // n과 가까운 값 저장
        	}
            else if(temp == sub && answer > array[i]) // n과의 거리가 동일할 경우 더 작은 값을 저장
            {
                sub = temp;
                answer = array[i];
            }
        }
        return answer;
    }
}

풀이

정렬 쓰기 싫었고, Math 쓰기 싫어서 이렇게 했습니다.

풀이 방법은 주석을 보시면 아시겠지만

주어진 정수(n)과 가장 가까운 수를 찾아야합니다.

그렇기때문에

배열(array)에 저장된 값을 주어진 정수(n)과 뺀 값이

sub(현재 가장 가까운 거리)보다 작으면

그 값을 sub으로 저장 및 비교하면서 

가장 가까이 있는 수를 찾아줍니다.

이때 주의점 2가지

1. n보다 배열에 작으면(arr[i]  <  n)

뺄때 음수가 나오니까 양수로 바꿔줍시다.

(-2 보다 1이 더 가깝지만, -2 < 1 이기 때문에)

2. 가장 가까운 수가 여러개 일때, 더 작은 수를 출력해야 합니다.

해결 방안

1. 음수라면 -1을 곱해서 양수로 만들어줍니다.

	temp = array[i] - n; //n과의 거리
	if(temp < 0) //음수이면 양수로 바꾸기 위해
	{
		temp*=-1; // Math.abs(arr[i] - i); 로 대체 가능합니다.
	}

2. sub이 동일할때 더 작은 수를 저장합니다.

            if(temp == sub && answer > array[i]) // n과의 거리가 동일할 경우 더 작은 값을 저장
            {
                sub = temp;
                answer = array[i];
            }

문제

문제 설명

제한사항

제한사항

• 2 ≤ n ≤ 10,000

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

• 12를 소인수분해하면 2 * 2 * 3 입니다. 따라서 [2, 3]을 return합니다.

입출력 예 #2

• 17은 소수입니다. 따라서 [17]을 return 해야 합니다.

입출력 예 #3

• 420을 소인수분해하면 2 * 2 * 3 * 5 * 7 입니다. 따라서 [2, 3, 5, 7]을 return합니다.

코드

import java.util.*;

class Solution {
    public int[] solution(int n) {
        int[] answer;
        HashMap<Integer, Integer> map = new HashMap<>();
        int index = 0;
        
        for(int i = 2; i <= n;) //소인수는 1보다 크기에 2부터 시작
        {
        	if(n%i==0) // 나눠지면 인수라는 것
        	{
        		map.put(i, i); //해시맵에 저장
        		n/=i; // n을 소인수로 나누기
        	}
        	else // 나눠지지 않으면 i++;
        	{
        		i++;
        	}
        	
        }
        
        answer = new int[map.size()]; //해시맵 크기만큼
        for(Integer i : map.keySet()) //배열에 값 넣기
        {
        	answer[index] = map.get(i);
        	index++;
        }
        Arrays.sort(answer); //해시맵은 정렬된 상태가 아니기 때문에 정렬
        return answer;
    }
}

풀이

소인수를 구하기 위해서는

소인수분해를 해야하고

소인수분해는

이런 과정을 통해 이루어집니다!

자! 여기서 우리는 중복된 수를 제거해야합니다.

배열을 쓰면서도 할 수 있겠지만

저는 자동으로 중복제거를 해주는 HashMap이 좋겠다 싶어서

HashMap을 이용해 봤습니다 ㅎㅎ

12(n) 가 소수(i)로 나눴을 때 나머지가 0 이면

그 소수가 소인수가 되니까 map 에 put 하고

나머지가 0이 아니라면 다음 소수로 넘어갑니다.

그리고 그렇게 HashMap에 저장된 값을 배열에 저장하는 이유는

HashMap은 정렬된 것처럼 보이지만 사실은 정렬되어 있지 않기 때문입니다!!

그래서 배열에 값을 넣어준 후 정렬시켜 준 것이죠 ㅎㅎ

문제

문제 설명

제한사항

제한사항

• -10,000 ≤ numbers의 원소 ≤ 10,000
• 2 ≤ numbers 의 길이 ≤ 100

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

• 두 수의 곱중 최댓값은 -3 * -5 = 15 입니다.

입출력 예 #2

• 두 수의 곱중 최댓값은 10 * 24 = 240 입니다.

입출력 예 #3

• 두 수의 곱중 최댓값은 20 * 30 = 600 입니다.

코드

class Solution {
    public int solution(int[] numbers) {
        int answer = numbers[0]*numbers[1]; //요게 포인트
        
        for(int i = 0; i < numbers.length-1; i++)
        {
            for(int j = i+1; j < numbers.length; j++)
            {
                if(numbers[i]*numbers[j] >= answer)
                {
                    answer = numbers[i]*numbers[j];
                }
            }
        }
        return answer;
    }
}

풀이

혹시 7번 테스트가 안되서 찾아오셨나요?

혹시 answer = 0 또는 일정값으로 초기화 하셨나요?

보통 값을 비교할 때 (MAX, MIN 등)

일정한 값으로 초기화 하고 사용하는데

이 문제의 경우 음수도 사용하기 때문에

만약 두 수를 곱한 값들이 모두 음수라면

0보다 작을 수 있고, 어떤 값인지 알기가 어렵겠죠?

그렇기 때문에 저는 

answer = numbers[0] * numbers[1];

이렇게 배열의 1, 2 번째에 있는 값을 곱한 값으로 초기화를 했습니다.

참 쉽죠~?

문제

문제 설명

제한사항

 
제한사항

• 1 ≤ balls ≤ 30
• 1 ≤ share ≤ 30
• 구슬을 고르는 순서는 고려하지 않습니다.
• share ≤ balls

입출력 예

 
입출력 예

 
입출력 예 설명
입출력 예 #1

• 서로 다른 구슬 3개 중 2개를 고르는 경우의 수는 3입니다. 

  

입출력 예 #2

• 서로 다른 구슬 5개 중 3개를 고르는 경우의 수는 10입니다.

코드

import java.math.BigInteger;

class Solution {
    public BigInteger solution(int balls, int share) {
        BigInteger bigBalls = BigInteger.valueOf(balls);
        BigInteger bigShare = BigInteger.valueOf(share);
        
    	return factorial(bigBalls).divide(factorial(bigBalls.subtract(bigShare)).multiply(factorial(bigShare)));
    }
    
    public static BigInteger factorial(BigInteger n) {
        if(n.intValue() <= 1)
        {
        	return BigInteger.ONE;
        }
    
        return n.multiply(factorial(n.subtract(BigInteger.ONE)));
    }
}

풀이
 

Hint
서로 다른 n개 중 m개를 뽑는 경우의 수 공식은 다음과 같습니다. 

와! 이번 문제는 힌트까지 주네~
공식 찾아 볼 필요도 없다 ㅎㅎ
 

class Solution {
    public int solution(int balls, int share) {
    	return factorial(balls)/(factorial(balls - share))*(factorial(share)));
    }
    
    public static int factorial(int n) {
        if(n() <= 1)
        {
        	return 1;
        }
    
        return n(factorial(n-1));
    }
}

Okay! 테스트 가볍게 통과~
채점 해볼까

이게 뭐야? 왜 실패한거지?
결과값 출력을 해볼까?

-1 이 왜 나오지?

.........
30개의 볼을 29개로 나누는 방법은 30이 나와야 할텐데???

 
WHY!!!!!!!!!

이유?

이유는 간단하다 
30! = 265252859812191058636308480000000 이다
 
int 는 이렇게 큰 수를 다를 수 없다 ㅠㅠ
그렇기 때문에 이런 큰 수를 다루기 위해 !!!
 

BigInteger

 
이름만 봐도 큰 수를 다룰 것 같은 이 친구를 사용하는 것이다.

이를 활용한 풀이가 첫번째 코드입니다

 
 

https://fall-in-dream.tistory.com/16

1차원 배열은 해결 완료!!!

그런데

2차원 배열을 출력할 때 Arrays.toString(arr); 을 사용하면 어떻게 될까요?

class Solution
{
	static Scanner sc = new Scanner(System.in);
	public static void main(String args[]) throws Exception
	{
		System.out.print(Arrays.toString(arr_test()));
	}
    
    public static int[][] arr_test()
    {
    	int[][] arr = {{1, 2}, {3, 4}, {5, 6}, {7, 8}};
    	return arr;
    }
}

결과물

[[I@74a14482, [I@1540e19d, [I@677327b6, [I@14ae5a5]

전에 함수에서 리턴한 배열을 그냥 출력하려고 할 때 나왔던 애들이 이제는 4개나!!!!

그러면 어떡해야 하느냐

Arrays.deepToString(출력하고 싶은 배열);

(참고, import java.util.Arrays; 필요합니다.)

class Solution
{
	static Scanner sc = new Scanner(System.in);
	public static void main(String args[]) throws Exception
	{
		System.out.print(Arrays.deepToString(arr_test()));
	}
    
    public static int[][] arr_test()
    {
    	int[][] arr = {{1, 2}, {3, 4}, {5, 6}, {7, 8}};
    	return arr;
    }
}

결과물

[[1, 2], [3, 4], [5, 6], [7, 8]]

글자가 조금 달라지자

이렇게 잘 출력되는 모습을 볼 수 있습니다.

2차원 배열 뿐만 아니라 다차원 배열도 사용 가능하니 편하게 사용해보세요!!

보통 배열을 출력하려고 하면 반복문을 사용하죠?

반복문을 사용한 출력

class Solution
{	
	public static void main(String args[]) throws Exception
	{
		int[] arr = {1, 2, 3, 4, 5, 6, 7, 8}; // 배열 선언
		for(int i = 0; i < arr.length; i++)
		{
			System.out.print(arr[i]+" ");
		}
	}
}

결과물

1 2 3 4 5 6 7 8

이렇게 할거라고 생각합니다.

근데 혹시 함수에서 return 값으로 배열을 받아올 때, 이걸 어떡하지 생각한 적 있지 않으신가요?

함수에서 배열을 return 받았을 때

class Solution
{
	static Scanner sc = new Scanner(System.in);
	public static void main(String args[]) throws Exception
	{
		System.out.print(arr_test);
	}
    
    public static int[] arr_test()
    {
    	int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
    	return arr;
    }
}

결과물

[I@74a14482

이 코드를 실행하면 이렇게 이상한게 나온다.

배열(arr)이 가지고 있는 값이 아닌, 그 값을 갖고 있는 주소값을 출력하게 되기 때문!!!!

그러면 어떡해야 할까?

Arrays.toString(출력하고 싶은 배열의 이름);

(참고. import java.util.Arrays 해줘야 사용 가능합니다.)

class Solution
{
	static Scanner sc = new Scanner(System.in);
	public static void main(String args[]) throws Exception
	{
		System.out.print(Arrays.toString(arr_test()));
	}
    
    public static int[] arr_test()
    {
    	int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
    	return arr;
    }    
}

그러면 

[1, 2, 3, 4, 5, 6, 7, 8]

짜잔~~~ 하고 배열이 모두 출력된다.

하지만 이 방법으로는 2차원 배열은 출력할 수 없습니다!!!!!

그러면 어떡해야하냐.............는 다음 시간에 올리도록 하겠습니다. ㅎㅎ

어떻게 해야하는지 밑에 올려놨습니다.

https://fall-in-dream.tistory.com/17