아찌방 하우스

문제

등차수열 혹은 등비수열 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이면 그 참가자가 미완주자이다.

결과

문제 설명

코드

import java.util.Arrays;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length]; //commands의 row 값만큼 배정
        
        for(int i = 0; i < commands.length; i++) //commands의 row 값만큼 반복
        {
            int how = (commands[i][1] - commands[i][0]) + 1; // n1~n2까지의 길이를 배정
            int[] temp = new int[how]; // n1~n2까지를 임시로 저장해줄 배열
            int count =0;
            for(int j = commands[i][0]-1; j <= commands[i][1]-1; j++) //n1~n2까지 
            {
                temp[count] = array[j]; //임시저장
                count++; //temp의 좌표 이동
            }
            Arrays.sort(temp); //정렬
            answer[i] = temp[commands[i][2]-1]; //저장
        }
        return answer;
    }
}

의도

결과

다른 사람의 코드

import java.util.Arrays;
class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int[] answer = new int[commands.length];

        for(int i=0; i<commands.length; i++){
            int[] temp = Arrays.copyOfRange(array, commands[i][0]-1, commands[i][1]);
            Arrays.sort(temp);
            answer[i] = temp[commands[i][2]-1];
        }

        return answer;
    }
}

copyOfRange 써서 코드를 단축시켰다. 근데 실행시간은 그렇게 달라지지 않는다.

class Solution {
    public int[] solution(int[] array, int[][] commands) {
        int n = 0;
        int[] ret = new int[commands.length];

        while(n < commands.length){
            int m = commands[n][1] - commands[n][0] + 1;

            if(m == 1){
                ret[n] = array[commands[n++][0]-1];
                continue;
            }

            int[] a = new int[m];
            int j = 0;
            for(int i = commands[n][0]-1; i < commands[n][1]; i++)
                a[j++] = array[i];

            sort(a, 0, m-1);

            ret[n] = a[commands[n++][2]-1];
        }

        return ret;
    }

    void sort(int[] a, int left, int right){
        int pl = left;
        int pr = right;
        int x = a[(pl+pr)/2];

        do{
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr){
                int temp = a[pl];
                a[pl] = a[pr];
                a[pr] = temp;
                pl++;
                pr--;
            }
        }while(pl <= pr);

        if(left < pr) sort(a, left, pr);
        if(right > pl) sort(a, pl, right);
    }
}

이 분은 sort 부분을 함수로 직접 구현하셨고 copyOfRange도 직접 구현하셨다.

부족한 금액 계산하기

​

문제 설명

코드

class Solution {
           public long solution(int price, int money, int count) {
                      long answer = -1;
                      int temp = 0; // count번 탔을때 필요한 총 금액을 임시로 저장할 변수.
                      for(int i = 1; i<=count; i++)
                      {
                                 temp += price * i; //count번 탈 때 필요한 금액을 temp에 저장.
                      }
                      answer = temp - money; //총 필요한 금액에서 내가 가진 money를 뺀 값을 answer에 저장.
                      return answer;
           }
}

코딩 의도 : 가장 단순하게 생각했다. 내가 필요한 돈은 한 번 탈 수록 증가한다(price * count의 방식으로). 이 값을 계속해서 더 해줘서 총 필요한 금액을 구한 후 내가 가진 돈(money)을 빼면 내가 얼마가 모자른지 나온다(answer).

​

1. 내가 돈이 얼마나 필요한지 구한다.

2. 총 필요한 돈에서 내가 가지고 있는 돈을 뺀다.

​

결과

​

오랜만에 아무 생각 없이 문제를 풀었더니 100점은 안 나왔다. 데이터 타입이나 알고리즘을 신경쓰지 않았으니 당연한 결과라고 생각한다.

​

또 다른 방법

price * 1 + price * 2 + ººººº + price * count = price(1+2+ººººº+count) 인 등차수열이기에

총 필요한 금액 = price*(count*(count+1)/2) 이다.

​

코드

class Solution {
           public long solution(int price, int money, int count) {
                      return price * (count*(count+1)/2) - money;
           }
}

결과

으로 코딩의 수가 확 줄었지만 점수는 같았다.

하지만 int 형을 long 형으로 바꿔보니 결과가 달랐다. 이 점은 나중에 다시 한 번 다루겠다.

​

코드} }

class Solution {
           public long solution(long price, long money, long count) {
                      return price * (count*(count+1)/2) - money;
           }
}

결과

한 문제가 실패했는데 원인을 모르겠어서 다른 사람들의 풀이를 찾아봤다.

​

다른 사람의 코드​

class Solution {
           public long solution(long price, long money, long count) {
                      return Math.max(price * (count*(count+1)/2) - money, 0);
           }
}

 } }

결과

​

Math.max 를 활용하는 사람이 많았다.

생각해보니 price = 1, count = 1, money > 1 일 경우 내가 더 필요한 돈은 0이다.

내가 기존에 했던 코딩의 경우

price * (count*(count+1)/2) - money => 1 * (1*(1+1)/2) - 2 = -1 이 나오므로 틀린 답이 되는 것이다.

음수가 나오면 내가 필요한 금액은 0원이여야 하기에

Math.max 를 이용하여 0을 반환해주는 것이다.

Math.max 와 Math.min 은 나중에 간단히 다뤄보겠다.

​

#프로그래머스 #위클리챌린지 #1주차 #프로그래밍 #자바 #JAVA