아찌방 하우스

문제

문제 설명

제한사항

제한사항

• -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

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

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

 
 

문제

등차수열 혹은 등비수열 common이 매개변수로 주어질 때, 마지막 원소 다음으로 올 숫자를 return 하도록 solution 함수를 완성해보세요.

제한사항

• 2 < common의 길이 < 1,000
• -1,000 < common의 원소 < 2,000
• 등차수열 혹은 등비수열이 아닌 경우는 없습니다.
• 공비가 0인 경우는 없습니다.

입출력 예

입출력 예 #1

• [1, 2, 3, 4]는 공차가 1인 등차수열이므로 다음에 올 수는 5이다.

입출력 예 #2

• [2, 4, 8]은 공비가 2인 등비수열이므로 다음에 올 수는 16이다.

코드

class Solution {
    public int solution(int[] common) {
        int answer = 0;
        int len = common.length;
        if(common[1]-common[0] == common[len-1]-common[len-2]) // 등차수열이면
        {
             answer = common[len-1]+(common[1]-common[0]);
        }
        else // 등비수열이면
        {
             answer = common[len-1]*(common[1]/common[0]);
        }
        return answer;
    }
}

풀이

등차수열, 등비수열이란?

답을 위해서는

1. 이 두가지를 구별한 후

2. common 배열의 마지막 값에 

공차를 더한 값 또는 공비를 곱한 값을 구한다!

이 두가지를 구별하는 방법?

 등차수열은 두번째 수와 첫번째 수의 차이와 마지막 수와 마지막 두번째 수의 차이가 같고

if(common[1]-common[0] == common[len-1]-common[len-2])

등비수열은 두번째 수를 첫번째 수와 나눈값와 마지막 수를 마지막 두번째 수로 나눈값과 같다.

if(common[1]/common[0] == common[len-1]/common[len-2])

문제

최빈값은 주어진 값 중에서 가장 자주 나오는 값을 의미합니다. 정수 배열 array가 매개변수로 주어질 때, 최빈값을 return 하도록 solution 함수를 완성해보세요. 최빈값이 여러 개면 -1을 return 합니다.

제한사항

• 0 < array의 길이 < 100
• 0 ≤ array의 원소 < 1000

입출력 예

코드

import java.util.*;

class Solution {
    public int solution(int[] array) {
        int answer = 0;
        
        Arrays.sort(array); // 체크할 배열의 크기를 알기 위해
        int size = array[array.length-1]+1; // 마지막 값(가장 큰 값) + 1의 크기로 배열생성
        int[] check = new int[size]; // 빈도 수 세기
        int max = 0; // 가장 많은 빈도 수 체크
        int count = 0; // 가장 많은 빈도 수가 두개 이상인지 체크
        
        for(int i = 0; i < array.length; i++)
        {
            check[array[i]]++;
        }
        
        for(int i = 0; i < size; i++)
        {
            if(check[i] >= max)
            {
                max = check[i];
                answer = i;
            }
        }
        
        for(int i = 0; i < size; i++)
        {
            if(check[i] == max)
            {
                count++;
                if(count > 1)
                {
                    answer = -1;
                    break;
                }
            }
        }
        return answer;
    }
}

풀이

최빈값이란

나온 횟수가 가장 많은 값을 말한다.

check 배열을 만드는 이유

이 배열의 주소를 array 의 값이라고 생각하고 

주소에 그 값이 나올때마다 1을 더해준다.

sort()한 이유는

check 배열의 사이즈를 알기 위해서이다.

array 배열에 포함 되어 있는 숫자가 check 배열의 주소값과 맞추기 위해서

array 배열 내에 가장 큰 값을 알아내기 위해서다.

int size = array[array.length-1]+1; 

여기서 +1을 한 이유는

조건에서 원소값이 0부터 시작할 수 있다는 것과

값과 주소를 일치하기 위해서다.

(이렇게 하지 않을 경우 배열은 0부터 시작하기 때문에 일치하지 않는다.)

그런 준비가 끝나면 빈도 수를 check 배열에 저장하면서

최대 빈도수(max)를 찾는다.

그 후 최대 빈도수(max)와 같은게 몇개 인지 센다.(count)

그 수(count)가 1이면 answer에 최대 빈도값을 출력, 

그 수가 2 이상이면 -1을 출력한다.

문제

첫 번째 분수의 분자와 분모를 뜻하는 denum1, num1, 두 번째 분수의 분자와 분모를 뜻하는 denum2, num2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

제한사항

• 0 <denum1, num1, denum2, num2 < 1,000

입출력 예

코드

class Solution {
    public int[] solution(int denum1, int num1, int denum2, int num2) {
        int[] answer = new int[2];
        int denum = (denum1*num2)+(denum2*num1);
        int num = num1*num2;
        int n = gcd(denum, num);
        answer[0] = denum/n;
        answer[1] = num/n;
        return answer;
    }
    public static int gcd(int num1, int num2)
    {
        if(num1%num2 == 0)
        {
            return num2;
        }
        return gcd(num2, num1%num2);
    }
        
}

해설

결과를 기약 분수의 형태로 나타내야 한다.

즉

이렇게 결과 값이 나와야 한다.

1단계를 구한 후

2단계에서 GCD로 나누면 

3단계 결과가 나온다.

GCD를 구하는 방법은 유클리드 호제법을 활용했다.

이에 대해서는 

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

여길 참고해주세요.

최대 공약수와 최대 공배수의 개념

1) 공약수

두 정수의 공통 약수를 공약수라고 한다.
두 정수 a, b에 대하여 e가 a의 약수이면서 b의 약수일 때 e를 a, b의 공약수라고 한다.

2) 최대공약수

두 정수의 공약수 중 가장 큰 것을 최대공약수라고 한다.
또한 최대공약수는 다음의 성질을 만족한다.
a, b의 최대공약수가 g이다. ⇔ a = ga′, b = gb′이면 a′, b′는 서로소이다.

3) 공배수

두 정수의 공통 배수를 공배수라고 한다.
두 정수 a, b에 대하여 c가 a의 배수이면서 b의 배수일 때 c를 a, b의 공배수라고 한다.

4) 최소공배수

양의 공배수 중 가장 작은 것을 최소공배수라고 한다.

코드

내가 이것을 보고 생각했을 때 짠 코드이다.

class Solution
{
	public static void main(String args[]) throws Exception
	{
		int num1 = 1250;
		int num2 = 80;
        	int g = gcd(num1, num2, num2);
        	int l = (num1*num2)/g;
		System.out.println("1250과 80의 GCD : "+g);
		System.out.println("1250과 80의 LCM : "+l);
	}
    public static int gcd(int num1, int num2, int n)
    {
        if(num1%n == 0 && num2%n == 0)
        {
            return n;
        }
        return gcd(num1, num2, n-1);
    }
}

유클리드 호제법

여기서  Q = A/B(A를 B로 나눈 몫), R = A%B (나머지) 이다.

예시

 1250과 580의 최대공약수를 구하라.

• A = B X Q + R
• 1250 = 580 X 2 + 90
• 580 = 90 X 6 + 40
• 90 = 40 X 2 + 10
• 40 = 10 X 4

4번째에서 R = 0 가 되니까, 직전의 R 인 10이 1250과 580의 최대공약수가 됩니다.

코드

class Solution
{
	public static void main(String args[]) throws Exception
	{
		int num1 = 1250;
		int num2 = 80;
        	int g = gcd(num1, num2);
        	int l = (num1*num2)/g;
		System.out.println("1250과 80의 GCD : "+g);
		System.out.println("1250과 80의 LCM : "+l);
	}
    public static int gcd(int num1, int num2)
    {
        if(num1%num2 == 0)
        {
            return num2;
        }
        return gcd(num2, num1%num2);
    }
}

코드

class Solution
{
	static Scanner sc = new Scanner(System.in);
	
	public static void main(String args[]) throws Exception
	{
		int T = sc.nextInt();
		
		for(int test_case = 1; test_case <= T; test_case++)
		{
			int[] arr = new int[10];
			double sum = 0;
			
			for(int i = 0; i < 10; i++)
			{
				arr[i] = sc.nextInt();
			}
			
			Arrays.sort(arr);
			
			for(int i = 1; i < 9; i++)
			{
				sum+=arr[i];
			}
			int average = (int)Math.round(sum/8);
			System.out.println("#"+test_case+" "+average);
		}
	}
}

해설

 10개의 숫자 중 min, max 값을 빼고 평균 값을 구해야 한다.

그냥 단순한게 입력을 받은 값들을 정렬해서

가장 앞, 가장 뒤의 값을 빼고 값을 더해서 평균값을 구했다.

문제 설명

코드

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;

class Solution {
    public String solution(String[] participant, String[] completion) {
        String answer = "";
        HashMap<String, Integer> map = new HashMap<>();
       
        for (String c:completion){ //해시맵에 완주자 목록을 넣기위해
            if(map.get(c) != null) // 동명이인을 위해
            {
                map.put(c,map.get(c)+1);
            }
            else
                map.put(c,1);
        }
        
        for (String p:participant)  
        {
            if(map.get(p) == null || map.get(p) == 0) //완주자 목록에 없거나 동명이인 중 못들어온 사람이 있는 경우
            {
                answer = p;
            }
            else if(map.get(p) >= 1) //완주한게 확인 되면 value 값에 -1
            {
                map.put(p, map.get(p)-1);
            }
        }
        return answer;
    }
}

의도

 HasMap을 하도 안 쓰다보니 다시 공부하고 코딩을 했다.

HasMap 선언 후  완주자 목록을 집어 넣는다. key = 완주자 이름, value은 완주자 한 명당 1씩 증가.

그 후 key 가 참가자(participant) 목록에 있으면 -1을 해준다.

또는 참가자(participant) 목록에 없거나(Null) value 값이 0이면 그 참가자가 미완주자이다.

결과