Posted 2021-07-15Updated 2021-07-15algorithm2 minutes read (About 319 words)

프로그래머스 2레벨 12953 N개의 최소공배수 JAVA

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/12953

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

풀이

문제 그대로 최소공배수를 구하는 문제

gcd는 유클리드 호제법이라는 방법을 사용했고

두 수의 최소공배수는 두 수의 곱을 두 수의 최대공약수로 나누면 된다.

만약 모른다고 하여도 금방 찾아보면 쉽게 이해할 수 있을 것임! ✍

코드

class Solution {


    static int gcd(int numA,int numB)
    {
        int result = 0;
        if(numA % numB == 0)
        {
            return numB;
        }
        else
        {
            result = gcd(numB,numA % numB);
        }
        return result;
    }
    static int lcd(int numA, int numB) {
        int result = 0;
        int gcd = 0;
        gcd = gcd(numA,numB);
        
        return (numA * numB)/gcd;
    }
    
    public int solution(int[] arr) {
        
        int answer = 0;
        int numA = arr[0];
        for(int i = 1;i<arr.length;i++)
        {
            numA = lcd(numA,arr[i]);   
        }
        answer = numA;
        return answer;
    }

}

메모

스스로 풀었는가 : ✅

Posted 2021-07-15Updated 2021-07-14algorithm2 minutes read (About 295 words)

프로그래머스 2레벨 12905 가장 큰 정사각형 찾기

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/12905

1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

풀이

배열의 각 요소를 왼쪽,위,왼쪽 위의 값 중 최솟값 +1로 갱신하여 최대 크기를 구할 수 있다.
최솟값인 이유는 정사각형이기 때문이다.
현 위치에서 가능한 최대 정사각형의 크기를 저장한다는 점에서 메모라이제이션 느낌을 받았다.

코드

class Solution {
    public static int solution(int [][]board)
    {
        int answer = board[0][0];
        int r = board.length;
        int c = board[0].length;
        for(int i=1;i<r;i++)
        {
            for(int j=1;j<c;j++)
            {
                if(board[i][j] == 1)
                {
                    board[i][j] = Math.min(board[i-1][j],board[i-1][j-1]);
                    board[i][j] = Math.min(board[i][j-1],board[i][j]) + 1;
                    answer = Math.max(answer,board[i][j]);
                }

            }
        }   
        return (int)Math.pow(answer,2);
    }

}

메모

문제는 간단한데 막상 풀려니 풀이가 떠오르지 않은 문제🙃
스스로 풀었는가 : ❎

Posted 2021-07-15Updated 2021-07-14algorithma minute read (About 196 words)

프로그래머스 2레벨 12951 JadenCase

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/12951

JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요.

풀이

언어에서 지원하는 메소드를 쓰거나 아스키코드로 처리하면 쉽게 풀 수 있는 문제

문제에서 나온 JadenCase를 그대로 만들어주면 됨

코드

class Solution {
    public String solution(String s) 
    {
        char[] charArr = s.toCharArray();
        boolean prevBlank = true;
        StringBuilder answer = new StringBuilder();
        for(int i=0;i<charArr.length;i++)
        {
            if(charArr[i] == ' ')
            {
                answer.append(' ');
                prevBlank = true;
            }
            else
            {
                if(prevBlank)
                {
                    prevBlank = false;
                    charArr[i] = Character.toUpperCase(charArr[i]);
                }
                else
                {
                    charArr[i] = Character.toLowerCase(charArr[i]);
                }
                answer.append(charArr[i]);
            }
        }

        return answer.toString();
    }

}

메모

StringBuffer -> 기본적으로 주어진 크기가 적음

StringBuilder -> 기본적으로 주어진 크기가 큼

문자열 크기가 상관없다면 StringBuilder 사용할 것

Posted 2021-07-15Updated 2021-07-14algorithm2 minutes read (About 290 words)

프로그래머스 2레벨 12945 피보나치수(메모라이제이션)

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/12945

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5

와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

풀이

오랜만에 다시 푼 피보나치 문제

n이 100000이하일 수 있는데 일반적인 피보나치로는 끝이나지 않아 통과하지 못할 것

따라서 메모라이제이션 기법을 써서 풀어야함

n이 크면 계산된 수가 커질 수 있는데 문제에서 나누라고한 값으로 나눈 나머지를 저장해주면 됨

코드

import java.util.Arrays;

class Solution {
    int MAX = 100000+1;
    int dp[] = new int[MAX];
    int divNum = 1234567;
    int fibo(int n)
    {
        if(n == 0)
        {
            return 0;
        }
        if(n == 1)
        {
            return 1;
        }
        
        if(dp[n-1]== -1)
        {
            dp[n-1] = fibo(n-1) % divNum;
        }
        
        if(dp[n-2] == -1)
        {
            dp[n-2] = fibo(n-2) % divNum;
        }
        
        return (dp[n-2] + dp[n-1]) % divNum;
    }
    
    public int solution(int n) {
        int answer = 0;
        Arrays.fill(dp, -1);
        answer = fibo(n);
        
        return answer;
    }
}

메모

어렵지 않은 문제였음

프로그래머스 2레벨 12953 N개의 최소공배수 JAVA

문제

풀이

코드

메모

프로그래머스 2레벨 12905 가장 큰 정사각형 찾기

문제

풀이

코드

메모

프로그래머스 2레벨 12951 JadenCase

문제

풀이

코드

메모

프로그래머스 2레벨 12945 피보나치수(메모라이제이션)

문제

풀이

코드

메모

Categories

Recents

Archives

Tags

Subscribe for updates