흰색기린

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://school.programmers.co.kr/learn/courses/30/lessons/12914

https://school.programmers.co.kr/learn/courses/30/lessons/138476

Think🤔

1. 멀리뛰기 경우의 수 다 따져봄

1,1,1,1,1

1,1,1,2
2,1,1,1
1,2,1,1
1,1,2,1

2,2,1
1,2,2
2,1,2

------------------
1,1,1,1,1,1 -> 1개
1,1,1,1,2 -> 5개

1,1,2,2 -> 6개
1,2,1,2
1,2,2,1
2,1,1,2
2,2,1,1
2,1,2,1

2,2,2 -> 1개

해보니 피보나치 수열 dp [ 동적 프로그래밍 ] 이용해서 풀어야 함

2. 귤 고르기

HashMap으로 받음
k = 9라 하면
제일 많이 받은 숫자부터 k에서 빼주고 0이 되면 종류 cnt해서 return

Solution✍

class Solution {
    public long solution(int n) {
        long dp[] = new long[n+2];
        dp[1] = 1;
        dp[2] = 2;
        
        for(int i=3; i<=n; i++){
            dp[i] = (dp[i-1] + dp[i-2]) % 1234567;
        }
        
        return dp[n];
    }
}

import java.util.HashMap;
import java.util.List;
import java.util.Collections;
import java.util.ArrayList;

class Solution {
    public int solution(int k, int[] tangerine) {
        int answer = 0; // 종류
        
        HashMap<Integer, Integer> hm = new HashMap();
        
        for(int i : tangerine){
            hm.put(i, hm.getOrDefault(i, 0) + 1);
        }
        
        List<Integer> val = new ArrayList<>(hm.values());
        Collections.sort(val, Collections.reverseOrder());
        
        for(int i : val){
            if(k < 1){return answer;}
            k = k - i;
            answer++;
        }
        
        return answer;
    }
}

// HashMap으로 받음
// k = 9라 하면
// 제일 많이 받은 숫자부터 k에서 빼주고 0이 되면 종류 cnt해서 return

Review🤩

dp는 다른 사람 정답 참조 후 작성

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://school.programmers.co.kr/learn/courses/30/lessons/12953?language=java

Think🤔

1. 최대공약수 구하는 방법 
2. 유클리드 호제법 이용
3. 최대공약수를 구한 후 최소공배수 = ( a * b ) / 최대공약수

- 유클리드 호제법

유클리드 호제법(Euclidean algorithm)은 두 개의 자연수의 최대공약수를 구하는 방법 중 하나입니다. 이름은 그리스의 수학자 유클리드에게 영감을 받아 지어졌습니다. 이 방법은 두 수를 나누고 나머지를 이용하여 계속해서 나누어가면서 두 수의 최대공약수를 찾아내는 간단하고 효율적인 알고리즘입니다. 여기에는 두 가지 과정이 있습니다:

두 수 중 큰 수를 작은 수로 나눕니다.
나머지가 0이 아니라면, 작은 수를 큰 수로, 나머지를 작은 수로 대체합니다.
나머지가 0이 되면, 그 때의 큰 수가 최대공약수가 됩니다.
이 방법은 반복적으로 나누기 연산을 통해 최대공약수를 찾기 때문에 효율적이며, 재귀적으로 구현할 수도 있습니다. 최대공약수를 구하는데 유클리드 호제법은 매우 효율적이며 널리 사용되는 방법 중 하나입니다.

Solution✍

최소공배수를 구하긴 위해서 최대공약수를 이용한다

먼저 최대공약수는 보통 gcd , 최소공배수는 lcm으로 표현

import java.lang.Math;

// 최대공약수 gcd
// 최소공배수 lcm

class Solution {
    public int solution(int[] arr) {
        int answer = arr[0];
        
        for(int i=1; i<arr.length; i++){
            answer = lcm(answer,arr[i]);
        }
        
        return answer;
    }
    
    public int gcd(int a,int b){
        
        int big = Math.max(a,b);
        int small = Math.min(a,b);
        
        // 작은 값으로 큰 값을 나눴을 때 0이되면 작은 값이 최대공약수가 됨
        if(big % small == 0){ 
            return small;
        }
        
        // 아닐경우 작은 값을 앞 , 나머지를 뒤
        return gcd(small,big % small);
    }
    
    public int lcm(int a,int b){
        return (a * b) / gcd(a,b);
    }
}

Review🤩

    public int gcd(int a, int b) {
        if(b == 0) {
            return a;
        }
        
        return gcd(b, a % b);
    }

최대공약수를 구할때 이렇게도 가능한데, 작은값이 왜 b인지 a == 0 return b는 왜 안되는지 이해가 안됨.

2 , 4일 경우

gcd(4, 0)이 들어가고 뒤에는 자동적으로 작은 값이 들어감

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://school.programmers.co.kr/learn/courses/30/lessons/17677?language=java

Think🤔

import java.util.ArrayList;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();

        double jaka = 0;
        
        ArrayList<String> arr1 = new ArrayList();
        ArrayList<String> arr2 = new ArrayList();
        
        for(int i=0; i<str1.length() - 1; i++){
            char c1 = str1.charAt(i);
            char c2 = str1.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr1.add(""+c1+c2);
            }
        }
        
        for(int i=0; i<str2.length() - 1; i++){
            char c1 = str2.charAt(i);
            char c2 = str2.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr2.add(""+c1+c2);
            }
        }
        
        ArrayList<String> intersection = new ArrayList<>(arr1);
        intersection.retainAll(arr2); // arr1과 arr2의 교집합을 intersection에 저장
        
        int kyo = intersection.size();
        int hab = arr1.size() + arr2.size() - kyo;
        
        if(intersection.size() == 0){
            answer = 65536;
        } else {
            answer = (int)((double) kyo / hab * 65536);
        }
        
        System.out.println(arr1);
        System.out.println(arr2);
        System.out.println("kyo : " + kyo);
        System.out.println("hab : " + hab);
        
        return answer;
    }
}
// ab+면 요소를 하나로 삼음
// ab+ -> ab
// abc -> ab bc 

// 유사도 체크 후 정수 버리고 곱함 0.42 * 65536

// 반복문으로 자르고 특수문자면 앞에만 하고 넘김 , 한 만큼 cnt 세고 뺴면 교집합
// [ FR ] , RA , AN , [ NC ] , CE
// [ FR ] , RE , EN , [ NC ] , CH
// 2 / 8
// 교집합 = 같은지 확인
// 합집합 = 전체 - 교집합

이렇게 했을 경우 4,5,7,9,10,11,13 실패 

반례를 차장보기로 한다.

합집합 구하는 방식의 문제

import java.util.ArrayList;

class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();

        double jaka = 0;
        
        ArrayList<String> arr1 = new ArrayList();
        ArrayList<String> arr2 = new ArrayList();
        
        for(int i=0; i<str1.length() - 1; i++){
            char c1 = str1.charAt(i);
            char c2 = str1.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr1.add(""+c1+c2);
            }
        }
        
        for(int i=0; i<str2.length() - 1; i++){
            char c1 = str2.charAt(i);
            char c2 = str2.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr2.add(""+c1+c2);
            }
        }
        ArrayList<String> union = new ArrayList<>();        // 합집합
        ArrayList<String> intersection = new ArrayList<>(); // 교집합
        
        
        for(String s : arr1){
            if(arr2.remove(s)){
                intersection.add(s);
            }
            union.add(s); // 교집합 빼고 넣기
        }
        for(String s : arr2){ // 나머지 arr2값 넣기
            union.add(s);
        }
        
        int kyo = intersection.size();
        int hab = union.size();
        
        if(intersection.size() == 0){
            answer = 65536;
        } else {
            answer = (int)((double) kyo / (double)hab * 65536);
        }
        
        System.out.println(arr1);
        System.out.println(arr2);
        System.out.println("kyo : " + kyo);
        System.out.println("hab : " + hab);
        
        return answer;
    }
}

Solution✍

import java.util.ArrayList;


class Solution {
    public int solution(String str1, String str2) {
        int answer = 0;
        
        str1 = str1.toUpperCase();
        str2 = str2.toUpperCase();

        double jaka = 0;
        
        ArrayList<String> arr1 = new ArrayList();
        ArrayList<String> arr2 = new ArrayList();
        
        for(int i=0; i<str1.length() - 1; i++){
            char c1 = str1.charAt(i);
            char c2 = str1.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr1.add(""+c1+c2);
            }
        }
        
        for(int i=0; i<str2.length() - 1; i++){
            char c1 = str2.charAt(i);
            char c2 = str2.charAt(i+1);
            if(Character.isLetter(c1) && Character.isLetter(c2)){
                arr2.add(""+c1+c2);
            }
        }
        ArrayList<String> union = new ArrayList<>();        // 합집합
        ArrayList<String> intersection = new ArrayList<>(); // 교집합
        
        for(String s : arr1){
            if(arr2.remove(s)){
                intersection.add(s);
            }
            union.add(s); // 교집합 빼고 넣기
        }
        for(String s : arr2){ // 나머지 arr2값 넣기
            union.add(s);
        }
        
        int kyo = intersection.size();
        int hab = union.size();
        
        // kyo가 0일때 안되는 이유
        // a,b가 있고 c가 있으면 
        // 교에 0들어가는 경우 , 합에 3인 경우
        // 그럼 답이 0이 나와야하는데 65536이 나와서 오류 그래서 hab == 0 을 걸어줘야 함
        // 테스트 케이스 5번이 그런경우 같은데 answer = 0;으로 보내서 검증 [ 통과 맞음 ]
        if(hab == 0){
            answer = 65536;
        } else {
            answer = (int)((double) kyo / (double)hab * 65536);
        }
        
        return answer;
    }
}

Review🤩

정렬은 필요없다.

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://school.programmers.co.kr/learn/courses/30/lessons/42888

Think🤔

Enter 채팅방 입장

Leave 채팅방 퇴장

Change 채팅방 변경

각각 함수 따로 생성

아이디는 중복 X , 닉네임은 중복 가능

import java.util.HashMap;

class Solution {
    public String[] solution(String[] record) {
        
        HashMap<String, String> id = new HashMap();
        int count = 0; // 출력 카운트 몇인지
        
        for(String str : record){
            String[] info = str.split(" ");
            String behavior = info[0];
            if(behavior.equals("Enter")){
                count++;
            }else if(behavior.equals("Leave")){
                count++;
                continue;
            }
            id.put(info[1],info[2]); // uid1234 , Muzi
        }
        
        String[] answer = new String [count];
        int answerCnt = 0;
        
        for(int i=0; i<answer.length; i++){
            String[] str = record[i].split(" ");
        
            String behavior = str[0];
            String nickName = str[1];
            
            if(behavior.equals("Enter")){
                answer[answerCnt] = id.get(nickName) + "님이 들어왔습니다.";
            }else if(behavior.equals("Leave")){
                answer[answerCnt] = id.get(nickName) + "님이 나갔습니다.";
            }
            answerCnt++;
        }
        
        return answer;
    }
}

// 반복문 record 돔
// hashmap 아이디랑 닉네임
// change면 hashMap value 변경 
// 다 돌고 다시 for문 돌려서
// 아이디에 맞는 value값 글자 보여주면서 들어왔습니다 , 나갔습니다 보여줌
// 변경은 안보임

샘플 테스트만 통과하고 다틀림...

왜 틀렸는지 궁금했는데 똑같은 코드도 있는데 통과하지 못함

Solution✍

import java.util.HashMap;

class Solution {
    public String[] solution(String[] record) {
        
        HashMap<String, String> id = new HashMap();
        int count = 0; // 출력 카운트 몇인지
        
        for(String str : record){
            String[] info = str.split(" ");
            String behavior = info[0];
            
            if(behavior.equals("Enter")){
                count++;
            }else if(behavior.equals("Leave")){
                count++;
                continue;
            }
            id.put(info[1],info[2]); // uid1234 , Muzi
        }
        
        String[] answer = new String [count];
        
        int answerCnt = 0;
        for(int i=0; i<record.length; i++){ ///////////// 이곳 answer이 아님
            String[] info = record[i].split(" ");
        
            String behavior = info[0];
            String nickName = id.get(info[1]);
            
            if(behavior.equals("Enter")){
                answer[answerCnt++] = nickName + "님이 들어왔습니다.";
            }else if(behavior.equals("Leave")){
                answer[answerCnt++] = nickName + "님이 나갔습니다.";
            }
        }
        
        return answer;
    }
}

answer이 아닌 부분 record를 바꿔줬는데 반례를 생각해 보면

들어왔고 , 변경했고 , 나갔으면 

들어옴 1

변경 0

나감 1

이여서 총 2의 길이를 가짐

근데 마지막 나감도 찍어줘야 되기 때문에 모든 record를 검사해야 됨...

Review🤩

이상한 곳에서 헤맸다..

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

https://school.programmers.co.kr/learn/courses/30/lessons/42885?language=java

Think🤔

int[] people이 주어짐 , 무게들이 다 나열되어 있음

int limit 은 무게 제한을 나타냄

무게 제한이 안넘어가게 

그럼 peolple에 있는 값 다 더하고 limit으로 나눈 몫에 + 1 하면 되는거 아닌가? 

-> 100 100 90 10 이고 limit이면 100이면 300 / 100 + 1 4대 근데 3대로도 가능 그렇기 때문에 X

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people);
        int i = 0;
        int j = people.length - 1;
        while(i < j){
            int sum = people[i] + people[j];
            if(sum > limit){ // 큰 무게 때문에 sum이 limit을 넘으니 , 큰 무게를 줄여준다.
                j--;
            }else{
                i++;
                j--;
            }
            answer++;
        }
        
        if(i == j){answer++;} // 마지막에 사람 한명 남으면
        
        return answer;
    }
}

Solution✍

import java.util.Arrays;

class Solution {
    public int solution(int[] people, int limit) {
        int answer = 0;
        
        Arrays.sort(people);
        int i = 0;
        int j = people.length - 1;
        while(i < j){
            int sum = people[i] + people[j];
            if(sum > limit){ // 큰 무게 때문에 sum이 limit을 넘으니 , 큰 무게를 줄여준다.
                j--;
            }else{
                i++;
                j--;
            }
            answer++;
        }
        
        if(i == j){answer++;} // 마지막에 사람 한명 남으면
        
        return answer;
    }
}

20 20 20 20 20 / 100일 경우

1개의 구명보트로 보드 구할 수 있음

20 20 40 20 20 

근데 어차피 최대 2명씩이여서 이 반례는 필요하지 않음!

Review🤩

생각보다 어렵..

알고리즘 풀이 방법입니다.
문제(Problem) -> 생각(Think) -> 해결책(Solution) -> 리뷰(Review) 를 통해서 정리해서 작성합니다.

Problem📄

프로그래머스 82%대 문제 몇 가지 ...

Think🤔

풀이하면서 솔루션에 같이 기입

Solution✍

3월에 태어난 여성 회원 목록 출력하기

SELECT MEMBER_ID , MEMBER_NAME , GENDER , TO_CHAR(DATE_OF_BIRTH, 'YYYY-MM-DD') AS DATE_OF_BIRTH
FROM MEMBER_PROFILE 
WHERE TO_CHAR(DATE_OF_BIRTH , 'MM') = '03'
  AND TLNO IS NOT NULL
  AND GENDER = 'W'
ORDER BY MEMBER_ID ASC;

대여 기록이 존재하는 자동차 리스트 구하기

    SELECT DISTINCT A.CAR_ID
    FROM CAR_RENTAL_COMPANY_CAR A
    JOIN CAR_RENTAL_COMPANY_RENTAL_HISTORY B
      ON A.CAR_ID = B.CAR_ID
   WHERE A.CAR_TYPE = '세단'
     AND TO_CHAR(B.START_DATE,'MM') = '10'
ORDER BY A.CAR_ID DESC

    - ORDER BY를 사용할때는 SELECT에 있는 절로 해야됨. 

가격대 별 상품 개수 구하기

SELECT TRUNC(PRICE/10000) * 10000 AS PRICE_GROUP , COUNT(1) PRODUCTS
  FROM PRODUCT 
 GROUP BY TRUNC(PRICE/10000)
 ORDER BY PRICE_GROUP ASC;

식품분류별 가장 비싼 식품의 정보 조회하기

SELECT CATEGORY , PRICE AS MAX_PRICE , PRODUCT_NAME
  FROM FOOD_PRODUCT
 WHERE (CATEGORY,PRICE) IN (SELECT CATEGORY , MAX(PRICE)
                      FROM FOOD_PRODUCT
                     WHERE CATEGORY IN ('과자', '국', '김치', '식용유')
                  GROUP BY CATEGORY) 
 ORDER BY MAX_PRICE DESC;

WHERE절에서 IN 조건에 있는 컬럼하고 똑같으면 사용 가능 서브쿼리로도 가능

Review🤩

IN 조건 전에 컬럼 맞추는 건 이번에 처음 알았다.