그로블

문제 설명

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

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

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

예시

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

ANIMAL_INS

ANIMAL_OUTS

ANIMAL_OUTS 테이블에서

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

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

ANIMAL_IDNAME

본 문제는 Kaggle의 "Austin Animal Center Shelter Intakes and Outcomes"에서 제공하는 데이터를 사용하였으며 ODbL의 적용을 받습니다.

풀이

[MySQL]

SELECT ANIMAL_ID, NAME 
FROM ANIMAL_OUTS
WHERE NOT EXISTS 
(SELECT NULL 
FROM ANIMAL_INS 
WHERE ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID)

NOT EXISTS구문은 먼저 ANIMAL_OUTS 테이블에 접근해서 하나의 레코드를 가져온 뒤 해당 레코드에 대해서 NOT EXISTS 이하의 서브 쿼리를 실행하고 서브 쿼리가 존재하지 않는지를 확인한다. 이 구문을 이용하여 존재하지 않느느 ANIMAL_ID를 찾아주면 된다.

[Oracle]

SELECT ANIMAL_ID, NAME 
FROM ANIMAL_OUTS 
WHERE NOT EXISTS 
(SELECT NULL 
FROM ANIMAL_INS 
WHERE ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID) 
ORDER BY ANIMAL_ID

이유는 잘 모르겠지만 Oracle에서 NOT EXISTS를 쓰면 틀렸다고 나와서 ANIMAL_ID를 기준으로 정렬을 해줬더니 정답 처리가 되었다.

LEFT OUTER JOIN을 이용한 방법으로도 풀어보자.

SELECT ANIMAL_OUTS.ANIMAL_ID, ANIMAL_OUTS.NAME 
FROM ANIMAL_OUTS 
LEFT OUTER JOIN ANIMAL_INS
ON ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID
WHERE ANIMAL_INS.ANIMAL_ID is NULL
ORDER BY ANIMAL_OUTS.ANIMAL_ID

LEFT OUTER JOIN은 왼쪽 테이블을 기준으로 오른쪽 테이블의 레코드를 비교하여 조건이 일치하면 가져와서 JOIN하고 다르면 NULL이 표시된다. ANIMAL_OUTS 테이블을 기준으로 JOIN을 하게 되면 ANIMAL_OUTS에 있지만 ANIMAL_INS에 없는 값들은 NULL로 들어오기 때문에 없어진 기록을 찾을 수 있다.

SELECT ANIMAL_OUTS.ANIMAL_ID, ANIMAL_OUTS.NAME 
FROM ANIMAL_OUTS, ANIMAL_INS
WHERE ANIMAL_OUTS.ANIMAL_ID = ANIMAL_INS.ANIMAL_ID(+)
AND ANIMAL_INS.ANIMAL_ID IS NULL
ORDER BY ANIMAL_OUTS.ANIMAL_ID

Oracle에서 (+)를 이용해서 위와 같이 작성할 수도 있다.

문제 설명

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

입출력 예

입출력 예에 대한 설명

입출력 예 #1

문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #2

문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #3

문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.

입출력 예 #4

문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

풀이

def solution(s):
    answer = len(s)
   
   #모든 경우의 수 중 가장 짧은 길이
    for i in range(1, len(s)//2+1):	
        answer = min(compress(s, i), answer)
        
    return answer

def compress(s, num):
    comstr = ''
    count = 1
    
    for i in range(0, len(s), num):
    	#같은 문자열 반복하는 경우
        if s[i:i+num] == s[i+num:i+2*num]:
            count += 1
        #다른 문자열이 나오는 경우
        else:
            if count == 1:
                comstr += s[i:i+num]
            else:
                comstr += str(count) + s[i:i+num]
                count = 1
            
    return len(comstr)

테스트 1 〉	통과 (0.04ms, 10.2MB)
테스트 2 〉	통과 (0.46ms, 10.3MB)
테스트 3 〉	통과 (0.35ms, 10.3MB)
테스트 4 〉	통과 (0.05ms, 10.3MB)
테스트 5 〉	통과 (0.00ms, 10.2MB)
테스트 6 〉	통과 (0.05ms, 10.3MB)
테스트 7 〉	통과 (0.78ms, 10.2MB)
테스트 8 〉	통과 (0.61ms, 10.2MB)
테스트 9 〉	통과 (0.88ms, 10.2MB)
테스트 10 〉	통과 (2.88ms, 10.2MB)
테스트 11 〉	통과 (0.11ms, 10.2MB)
테스트 12 〉	통과 (0.11ms, 10.2MB)
테스트 13 〉	통과 (0.20ms, 10.2MB)
테스트 14 〉	통과 (0.97ms, 10.2MB)
테스트 15 〉	통과 (0.22ms, 10.3MB)
테스트 16 〉	통과 (0.02ms, 10.2MB)
테스트 17 〉	통과 (1.40ms, 10.2MB)
테스트 18 〉	통과 (1.35ms, 10.3MB)
테스트 19 〉	통과 (1.35ms, 10.2MB)
테스트 20 〉	통과 (3.76ms, 10.3MB)
테스트 21 〉	통과 (3.23ms, 10.2MB)
테스트 22 〉	통과 (3.24ms, 10.2MB)
테스트 23 〉	통과 (3.10ms, 10.2MB)
테스트 24 〉	통과 (2.94ms, 10.2MB)
테스트 25 〉	통과 (3.21ms, 10.2MB)
테스트 26 〉	통과 (3.20ms, 10.3MB)
테스트 27 〉	통과 (3.17ms, 10.2MB)
테스트 28 〉	통과 (0.02ms, 10.2MB)

문자열을 1개 단위로 자르는 경우부터 1씩 증가시켜서 반으로 자르는 경우까지 모든 경우 중 가장 작게 압축되는 케이스를 찾는 과정을 solution 함수에서 수행했다.

문자열을 압축하는 과정은 compress라는 함수에서 하는데, 문자열과 함께 문자열을 자르는 단위(num)를 인자로 넘겨주었다. 문자열의 처음부터 끝까지 돌면서 num만큼의 간격으로 앞부분과 뒷부분이 같은지 비교하고 같으면 count를 1만큼 증가시키고 같지 않으면 압축된 문자열을 가리키는 comstr에 반복된 숫자와 문자열을 추가해준다. 이 때, count가 1이라면 숫자를 생략한다. 반복문을 다 돌면 해당 문자열의 길이를 다시 solution에 return해준다.

문제

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

입출력 예

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

입출력 예 #3
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

풀이

C++

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> nums)
{
    int answer = 0;
    int bring = nums.size()/2; //가지고 갈 수 있는 폰켓몬
    
    sort(nums.begin(), nums.end()); //정렬
    nums.erase(unique(nums.begin(), nums.end()), nums.end()); //중복 제거
    
    return bring > nums.size() ? nums.size() : bring; //작은 것 리턴
}

테스트 1 〉	통과 (0.01ms, 3.81MB)
테스트 2 〉	통과 (0.01ms, 3.99MB)
테스트 3 〉	통과 (0.01ms, 3.99MB)
테스트 4 〉	통과 (0.01ms, 4.34MB)
테스트 5 〉	통과 (0.01ms, 3.99MB)
테스트 6 〉	통과 (0.01ms, 3.81MB)
테스트 7 〉	통과 (0.01ms, 3.76MB)
테스트 8 〉	통과 (0.01ms, 4.35MB)
테스트 9 〉	통과 (0.02ms, 3.66MB)
테스트 10 〉	통과 (0.02ms, 3.69MB)
테스트 11 〉	통과 (0.02ms, 4.34MB)
테스트 12 〉	통과 (0.06ms, 3.97MB)
테스트 13 〉	통과 (0.06ms, 3.75MB)
테스트 14 〉	통과 (0.07ms, 3.99MB)
테스트 15 〉	통과 (0.06ms, 3.75MB)
테스트 16 〉	통과 (0.58ms, 3.99MB)
테스트 17 〉	통과 (0.63ms, 4.02MB)
테스트 18 〉	통과 (0.57ms, 4.02MB)
테스트 19 〉	통과 (0.56ms, 3.95MB)
테스트 20 〉	통과 (0.38ms, 4.08MB)

Python3

def solution(nums):
    return min(len(set(nums)), len(nums)/2);

테스트 1 〉	통과 (0.00ms, 10.1MB)
테스트 2 〉	통과 (0.01ms, 10.2MB)
테스트 3 〉	통과 (0.00ms, 10.2MB)
테스트 4 〉	통과 (0.01ms, 10.2MB)
테스트 5 〉	통과 (0.01ms, 10.1MB)
테스트 6 〉	통과 (0.01ms, 10.2MB)
테스트 7 〉	통과 (0.01ms, 10.2MB)
테스트 8 〉	통과 (0.01ms, 10.1MB)
테스트 9 〉	통과 (0.01ms, 10.2MB)
테스트 10 〉	통과 (0.01ms, 10.2MB)
테스트 11 〉	통과 (0.01ms, 10.3MB)
테스트 12 〉	통과 (0.07ms, 10.2MB)
테스트 13 〉	통과 (0.08ms, 10.3MB)
테스트 14 〉	통과 (0.08ms, 10.4MB)
테스트 15 〉	통과 (0.05ms, 10.3MB)
테스트 16 〉	통과 (0.80ms, 11.1MB)
테스트 17 〉	통과 (0.63ms, 10.6MB)
테스트 18 〉	통과 (0.54ms, 10.7MB)
테스트 19 〉	통과 (0.50ms, 10.3MB)
테스트 20 〉	통과 (0.38ms, 10.4MB)

간단하게 가지고 갈 수 있는 폰켓몬 수와 중복을 제거한 폰켓몬 수(폰켓몬의 종류)를 비교해서 더 작은 값을 return 해주면 된다.

가지고 갈 수 있는 폰켓몬 수가 폰켓몬의 종류보다 적다면 최대한 많은 폰켓몬을 가지고 가야 하기 때문에 각각 다른 폰켓몬을 가지고 갈 것이므로 N/2마리가 그대로 최댓값이 된다. 반대로 폰켓몬의 종류가 더 적다면 아무리 많이 가져간다고 해도 종류의 수를 넘을 수 없기 때문에 폰켓몬의 종류가 최댓값이 된다.

C++에서는 sort, erase, unique 함수를 이용해 중복을 제거한 뒤 삼항 연산자를 이용해서 작은 값을 return했고, Python에서는 중복을 허용하지 않는 set으로 자료형을 바꾼 뒤 길이를 비교하여 작은 값을 return하였다.