아찌방 하우스

문제

 

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록solution 함수를 완성하세요.

제한사항

삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

코드

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int N = triangle.length;
        int M = triangle[N-1].length;
        int[][] dp = new int[N][M];

        dp[0][0] = triangle[0][0];

        for(int i = 0; i < N-1; i++){
            for(int j = 0; j < triangle[i].length; j++){
                for(int k = j; k < j+2; k++){
                    int num = dp[i][j] + triangle[i+1][k];
                    dp[i+1][k] = Math.max(dp[i+1][k], num);
                }
            }
        }

        for(int i = 0; i < M; i++){
            answer = Math.max(answer, dp[N-1][i]);
        }
        return answer;
    }
}

풀이

이 문제를 왜 DP로 풀어야 하나요?!

문제 분류가 DP 이기 때문에?

뭐 솔직히 그것도 맞긴한데

이걸 dsp로 푼다고 해봅시다.

그러면 위에서부터 쭉 내려와서 하나 계산

또 쭉 내려와서 하나 계산

이렇게 계~~~~속 할 거란 말이에요.

그러면 뭐가 문제냐!

시간 초과?

맞죠!

근데 왜 시간 초과가 나는가 하면

중복된 연산이 계속 반복 되고 있기 때문입니다.

첫번째 사진과 두번째 사진을 보면

마지막의 숫자가 하나 다른 걸로 

맨 위에서 부터 다시 내려오죠?

그렇게 중복된 연산이 반복되니까 시간이 많이 걸린다~~~~

그러면 어떻게 해야한다?

중복된 연산을 줄여야 한다.

그래서 위에서부터 내려오면서 

가장 최적의 경우를 확인하면서 내려오자 이겁니다.

저 위에꺼는 제가 처음에 풀면서

좀 복잡하게 푼 거여서

다른 소스를 봅시다.

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        int N = triangle.length;
        int M = triangle[N-1].length;
        
        for(int i = 1; i < N; i++){
            triangle[i][0] += triangle[i-1][0];
            triangle[i][i] += triangle[i-1][i-1];
            for(int j = 1; j < i; j++){
                triangle[i][j] += Math.max(triangle[i-1][j-1], triangle[i-1][j]);
            }
        }
        
        for(int i = 0; i < M; i++){
            answer = Math.max(answer, triangle[N-1][i]);
        }
        return answer;
    }
}

맨 처음, 즉 맨 위의 값은

무조건 본인이 최적이니까

그 다음칸 부터 봅시다.

내가 봐야하는건 내 왼쪽 위, 내 바로 위의 값 중 큰 값이 무엇인지 입니다.

그런데 배열의 첫번째, 맨 마지막에 위치하는 애들은 좀 달라요.

첫번째 애는 자기 바로 위의 값도 가장 첫번째 값이에요.

그러니까 왼쪽 위가 없죠?

그러니까 맨 처음값은 항상 본인의 위의 값이 최대값이 되는 겁니다.

마지막 애는 자기 위의 값이 없죠?

배열이 밑으로 갈수록 하나씩 길어지니까요.

그러니까 항상 왼쪽 위의 값이 최대값이 됩니다.

그 외에, 그러니까 맨 처음과 맨 끝 사이 애들은

이제 좀 따져봐야 합니다.

어떤 애들을?

본인의 왼쪽 위와 바로 위의 값 중 어느게 더 큰 값인지!

그래서 더 큰 값을 본인의 값과 더 하면

그 위치까지 갈 때의 최대값이 된다~~~

그렇게 해서 쭉 구하고나면

이제 마지막 줄을 보면

거기에 도달하기 위한 방법 중

가장 큰 값이 저장되어 있습니다.

그 중에서 가장 큰 값이 우리가 원하는 값이겠죠?

방법은 여러가지 있겠지만 

저는 마지막 줄을 한 번 쭉 봐서

가장 큰 값을 반환해 주었습니다.

여기까지 봐주셔서 감사합니다 ㅎㅎ

문제 설명

제한사항

코드

public static int[] solution(int num, int total) {
        int[] answer = new int[num];
        int start = 0;
        
        while(true) {
        	int sum = 0;
        	for(int i = start; i < start + num; i++) {
        		sum+=i;
        	}
        	if(sum == total) {
        		for(int i = 0; i < num; i++)
        		{
        			answer[i] = start;
        			start++;
        		}
        		break;
        	}
        	else if(sum < total) {start++;}
        	else {start--;}
        }
        
        return answer;
}​

풀이

num만큼 연속된 수로 total의 합이 된다는 것은

즉 num = 3 일때

{1, 2, 3} 이나 {4, 5, 6} 처럼 연속되는 3개의 수의 합이

total 이 되어야 하는 것이다.

그래서 num = 3, total = 12 이면

3 + 4 + 5 = 12 이기에 

이 {3, 4, 5} 를 찾아야 하는 것이다.

그러면 어떻게 할까 생각했는데

처음에 0(start) 부터 num까지의 합을 now total이라고 합시다.

이때 start가 1 더해지면 now totoal이 num 만큼 늘어나고

1 빼지면 now total이 num 만큼 줄어드는 것을 볼 수 있었다.

그래서 now total을 total 값과 비교해서

적으면 start + 1 을,

크면 start - 1을 해준다.

이렇게 차근차근 찾아가다보면 원하는 결과를 얻을 수 있습니다.

이를 이용해서 약간 수식처럼 만들어볼 수도 있는데요.

public static int[] solution(int num, int total) {
        int[] answer = new int[num];
        int start = 0;
        int sum = 0;
        for(int i = start; i < start + num; i++) {
    		sum+=i;
    	}
        start += (total-sum)/num;
        for(int i = 0; i < num; i++) {
    		answer[i]=start;
    		start++;
    	}
        return answer;
    }

풀이

 start = 0 으로 해서 

now total, 현재의 총합이 now total 이라고 할때

now total 은 결국 num 씩 커진다고 위에서 말했죠?

그러면 결국

(toal - now toal) / num 이 반복 되는 횟수가 되고

그것을 start에 더해주면

시작하는 숫자를 알게됩니다!!!!

앞에서 말한 방법과 결국에는 같은 맥락입니다.

좋은 방법을 선택해세요 ㅎㅎ

문제

정수 배열 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

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

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

 
 

문제

문제 설명

제한사항

제한사항

• 2 < numbers의 길이 < 100
• 0 < k < 1,000
• numbers의 첫 번째와 마지막 번호는 실제로 바로 옆에 있습니다.
• numbers는 1부터 시작하며 번호는 순서대로 올라갑니다.

입출력 예

입출력 예

입출력 예 설명

입출력 예 #1

• 1번은 첫 번째로 3번에게 공을 던집니다.
• 3번은 두 번째로 1번에게 공을 던집니다.

입출력 예 #2

• 1번은 첫 번째로 3번에게 공을 던집니다.
• 3번은 두 번째로 5번에게 공을 던집니다.
• 5번은 세 번째로 1번에게 공을 던집니다.
• 1번은 네 번째로 3번에게 공을 던집니다.
• 3번은 다섯 번째로 5번에게 공을 던집니다.

입출력 예 #3

• 1번은 첫 번째로 3번에게 공을 던집니다.
• 3번은 두 번째로 2번에게 공을 던집니다.
• 2번은 세 번째로 1번에게 공을 던집니다.

코드

class Solution {
    public int solution(int[] numbers, int k) {
        return numbers[((k-1)*2)%numbers.length];
    }
}

풀이

예 #2

1. 1번은 첫 번째로 3번에게 공을 던집니다.

2. 3번은 두 번째로 5번에게 공을 던집니다.

3. 5번은 세 번째로 1번에게 공을 던집니다.

4. 1번은 네 번째로 3번에게 공을 던집니다.

 5. 3번은 다섯 번째로 5번에게 공을 던집니다.

자! 그러면 차근차근 풀어봅시다.

1. 공은 한명을 넘겨서 던져집니다.

그러면 던진 길이는 k의 2배 이겠죠?

2. 근데 우리는 던진 친구를 찾아야 합니다.

던진 친구의 위치 = ( k * 2) - 2

                              = ( k - 1) * 2  

( k - 1 ) * 2에 위치하는 친구를 찾으면 됩니다.

3. 근데 ( k - 1 ) * 2가 배열(numbers)의 길이를 넘을 수도 있기때문에

( k + 1 ) * 2 을 배열(numbers)의 길이(numbers.length)로 나눈 나머지 값을 구합니다.

					((k-1)*2)%number.length

이렇게 하면 k 번째 공을 던진 친구를 찾을 수 있게 됩니다!!!

문제

등차수열 혹은 등비수열 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])