[Algo-Challenge]

SELOG·2024년 2월 1일

ALGO-CHALLENGE

목록 보기

4/17

[SQL : level 3] 없어진 기록 찾기 - 59042

문제 설명

ANIMAL_INS 테이블은 동물 보호소에 들어온 동물의 정보를 담은 테이블입니다. ANIMAL_INS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, INTAKE_CONDITION, NAME, SEX_UPON_INTAKE는 각각 동물의 아이디, 생물 종, 보호 시작일, 보호 시작 시 상태, 이름, 성별 및 중성화 여부를 나타냅니다.

NAME	TYPE	NULLABLE
ANIMAL_ID	VARCHAR(N)	FALSE
ANIMAL_TYPE	VARCHAR(N)	FALSE
DATETIME	DATETIME	FALSE
INTAKE_CONDITION	VARCHAR(N)	FALSE
NAME	VARCHAR(N)	TRUE
SEX_UPON_INTAKE	VARCHAR(N)	FALSE

ANIMAL_OUTS 테이블은 동물 보호소에서 입양 보낸 동물의 정보를 담은 테이블입니다. ANIMAL_OUTS 테이블 구조는 다음과 같으며, ANIMAL_ID, ANIMAL_TYPE, DATETIME, NAME, SEX_UPON_OUTCOME는 각각 동물의 아이디, 생물 종, 입양일, 이름, 성별 및 중성화 여부를 나타냅니다. ANIMAL_OUTS 테이블의 ANIMAL_ID는 ANIMAL_INS의 ANIMAL_ID의 외래 키입니다.

NAME	TYPE	NULLABLE
ANIMAL_ID	VARCHAR(N)	FALSE
ANIMAL_TYPE	VARCHAR(N)	FALSE
DATETIME	DATETIME	FALSE
NAME	VARCHAR(N)	TRUE
SEX_UPON_OUTCOME	VARCHAR(N)	FALSE

천재지변으로 인해 일부 데이터가 유실되었습니다. 입양을 간 기록은 있는데, 보호소에 들어온 기록이 없는 동물의 ID와 이름을 ID 순으로 조회하는 SQL문을 작성해주세요.

예시

예를 들어, ANIMAL_INS 테이블과 ANIMAL_OUTS 테이블이 다음과 같다면

ANIMAL_INS

ANIMAL_ID	ANIMAL_TYPE	DATETIME	INTAKE_CONDITION	NAME	SEX_UPON_INTAKE
A352713	Cat	2017-04-13 16:29:00	Normal	Gia	Spayed Female
A350375	Cat	2017-03-06 15:01:00	Normal	Meo	Neutered Male

ANIMAL_OUTS

ANIMAL_ID	ANIMAL_TYPE	DATETIME	NAME	SEX_UPON_OUTCOME
A349733	Dog	2017-09-27 19:09:00	Allie	Spayed Female
A352713	Cat	2017-04-25 12:25:00	Gia	Spayed Female
A349990	Cat	2018-02-02 14:18:00	Spice	Spayed Female

ANIMAL_OUTS 테이블에서

Allie의 ID는 ANIMAL_INS에 없으므로, Allie의 데이터는 유실되었습니다.
Gia의 ID는 ANIMAL_INS에 있으므로, Gia의 데이터는 유실되지 않았습니다.
Spice의 ID는 ANIMAL_INS에 없으므로, Spice의 데이터는 유실되었습니다.

따라서 SQL문을 실행하면 다음과 같이 나와야 합니다.

ANIMAL_ID	NAME
A349733	Allie
A349990	Spice

My Code

-- 입양 간 기록은 있는데, 보호소에 들어온 기록이 없는 동물
-- 동물의 ID와 이름을, ID ASC 조회

SELECT ANIMAL_ID, NAME
FROM ANIMAL_OUTS
WHERE ANIMAL_ID NOT IN (
    SELECT ANIMAL_ID
    FROM ANIMAL_INS
)
ORDER BY ANIMAL_ID ASC
;

[JAVA : level 2] 숫자 변환하기 - 154538

문제 링크

문제 설명

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

x에 n을 더합니다
x에 2를 곱합니다.
x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항

1 ≤ x ≤ y ≤ 1,000,000
1 ≤ n < y

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

입출력 예 설명

입출력 예 #1
x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2
x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3
x를 y로 변환할 수 없기 때문에 -1을 return합니다.

Wrong Code (50%)

class Solution {
    public static int temp_cnt;
    
    public int solution(int x, int y, int n) {
        temp_cnt = 123456789;
        int cnt = 0;
        int value = x;
        func(value, x, y, n, cnt);
        
        if(temp_cnt == 123456789) return -1;
        else return temp_cnt;
    }
    
    public static void func(int value, int x, int y, int n, int cnt){
        if(value == y){
            if(temp_cnt > cnt){
                temp_cnt = cnt;
            }
            return;
        } else if (value > y) return;
        
        // func_1
        func(value + n, x, y, n, cnt + 1);
        
        // func_2
        func(value * 2, x, y, n, cnt + 1);
        
        // func_3
        func(value * 3, x, y, n, cnt + 1);
    }
}

import java.util.*;
class Solution {
    public static int temp_cnt;
    public static LinkedList<Integer> list ;
    
    public int solution(int x, int y, int n) {
        list = new LinkedList<>();
        int cnt = 0;
        int value = x;
        func(value, x, y, n, cnt);
        
        if(list.size() == 0 ) return -1;
        else return Collections.min(list);
    }
    
    public static void func(int value, int x, int y, int n, int cnt){
        if(value == y){
            list.add(cnt);
            return;
        } else if (value > y) return;
        
        // func_1
        func(value + n, x, y, n, cnt + 1);
        
        // func_2
        func(value * 2, x, y, n, cnt + 1);
        
        // func_3
        func(value * 3, x, y, n, cnt + 1);
    }
}

Answer Code (Dp)

class Solution {
    public int solution(int x, int y, int n) {
        int[] dp = new int[y+1];
        
        for(int index = x ; index <= y ; index++){
            // 처음 x만 0으로 시작, 이후에 0이면 Max값 넣어서 제외해버려~
            if(index != x && dp[index] == 0){
                dp[index] = Integer.MAX_VALUE;
                continue; // 돌아가~
            }
            
            if(index + n <= y){
                dp[index+n] = dp[index+n] == 0 ? dp[index] + 1 : Math.min(dp[index] + 1, dp[index+n]);
            }
            if(index * 2 <= y){
                dp[index*2] = dp[index*2] == 0 ? dp[index] + 1 : Math.min(dp[index] + 1, dp[index*2]);
            }
            if(index * 3 <= y){
                dp[index*3] = dp[index*3] == 0 ? dp[index] + 1 : Math.min(dp[index] + 1, dp[index*3]);
            }
            
        }
        
        if(dp[y] == Integer.MAX_VALUE) return -1;
        return dp[y];
    
    }
}

Other Code (BFS)

import java.util.Queue;
import java.util.LinkedList;

class Solution {
    public int solution(int x, int y, int n) {
        boolean[] visited = new boolean[y + 1]; // 방문 여부를 체크하는 배열
        Queue<Integer> valuesQueue = new LinkedList<>(); // 숫자를 저장하는 큐
        Queue<Integer> countsQueue = new LinkedList<>(); // 연산 횟수를 저장하는 큐

        // 초기 값과 연산 횟수를 큐에 추가
        valuesQueue.add(x);
        countsQueue.add(0);
        visited[x] = true;

        while (!valuesQueue.isEmpty()) {
            int currentValue = valuesQueue.poll();
            int currentCount = countsQueue.poll();

            if (currentValue == y) {
                return currentCount; // 목표에 도달한 경우
            }

            // 다음에 방문할 숫자들을 큐에 추가
            if (currentValue + n <= y && !visited[currentValue + n]) {
                valuesQueue.add(currentValue + n);
                countsQueue.add(currentCount + 1);
                visited[currentValue + n] = true;
            }
            if (currentValue * 2 <= y && !visited[currentValue * 2]) {
                valuesQueue.add(currentValue * 2);
                countsQueue.add(currentCount + 1);
                visited[currentValue * 2] = true;
            }
            if (currentValue * 3 <= y && !visited[currentValue * 3]) {
                valuesQueue.add(currentValue * 3);
                countsQueue.add(currentCount + 1);
                visited[currentValue * 3] = true;
            }
        }

        return -1; // y에 도달할 수 없는 경우
    }
}