SELECT HOUR(DATETIME) AS 'HOUR', COUNT(*) AS 'COUNT'
FROM ANIMAL_OUTS
GROUP BY HOUR(DATETIME)
HAVING HOUR >= 9 AND HOUR <= 19
ORDER BY HOUR(DATETIME) ASC
SET @hour := -1;
SELECT (@hour := @hour + 1) as HOUR,
(SELECT COUNT(*) FROM ANIMAL_OUTS WHERE HOUR(DATETIME) = @hour) as COUNT
FROM ANIMAL_OUTS
WHERE @hour < 23
SELECT b.ANIMAL_ID, b.NAME
FROM ANIMAL_INS a RIGHT JOIN ANIMAL_OUTS b on a.ANIMAL_ID = b.ANIMAL_ID
WHERE a.ANIMAL_ID IS NOT NULL AND a.DATETIME > b.DATETIME
ORDER BY a.DATETIME
SELECT ANIMAL_INS.NAME, ANIMAL_INS.DATETIME
FROM ANIMAL_INS
LEFT OUTER JOIN ANIMAL_OUTS
ON ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID
WHERE ANIMAL_OUTS.ANIMAL_ID IS NULL
ORDER BY ANIMAL_INS.DATETIME ASC
LIMIT 3
SELECT ANIMAL_INS.ANIMAL_ID, ANIMAL_INS.ANIMAL_TYPE, ANIMAL_INS.NAME
FROM ANIMAL_INS
LEFT OUTER JOIN ANIMAL_OUTS
ON ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID
WHERE ANIMAL_INS.SEX_UPON_INTAKE != ANIMAL_OUTS.SEX_UPON_OUTCOME
SELECT ANIMAL_ID, NAME, SEX_UPON_INTAKE
FROM ANIMAL_INS
WHERE NAME = 'Lucy' OR NAME = 'Ella' OR NAME = 'Pickle' OR NAME = 'Rogan' OR NAME = 'Sabrina' OR NAME = 'Mitty'
SELECT ANIMAL_ID, NAME, SEX_UPON_INTAKE
FROM ANIMAL_INS
WHERE NAME IN ('Lucy', 'Ella', 'Pickle', 'Rogan', 'Sabrina', 'Mitty')
SELECT ANIMAL_ID, NAME,
IF(SEX_UPON_INTAKE LIKE "%Neutered%" OR SEX_UPON_INTAKE LIKE "%Spayed%", 'O', 'X') AS '중성화'
FROM ANIMAL_INS
ORDER BY ANIMAL_ID ASC
SELECT ANIMAL_INS.ANIMAL_ID, ANIMAL_INS.NAME
FROM ANIMAL_INS, ANIMAL_OUTS
WHERE ANIMAL_INS.ANIMAL_ID = ANIMAL_OUTS.ANIMAL_ID
ORDER BY ANIMAL_OUTS.DATETIME - ANIMAL_INS.DATETIME DESC
LIMIT 2
기존에 후보키였던 것을 포함한다면, 지금 검사하는 칼럼의 인덱스는 최소성을 만족하지 못하므로 return
기존에 후보키였던 것을 포함하지 않는다면,
vector<vector<string>> relation의 모든 레코드에 대해 칼럼의 인덱스의 값들을 추출해서, 한 vector<string>으로 잡는다. 잡은 vector<string>을 vector<vector<string>>에 넣는다.
모두 넣고, 일일히 대조해서 처음부터 끝까지 일치하는지 확인한다.
일치하는게 있다면, 후보키가 되지 못하므로 return
일치하는게 없다면, 후보키가 될 수 있다.
조금 말이 어려운데, 코드를 보면서 이해해보자.
아래 코드는 후보키의 가짓수를 토대로 dfs를 돌리는 함수다.
vector<vector<string>> rel;
// answer는 후보키의 vector를 저장한다.
vector<vector<int>> answer;
int col, row, arr[21];
int solution(vector<vector<string>> relation) {
row = relation.size();
col = relation[0].size();
rel = relation;
// i는 후보키의 가짓수
for(int i = 1; i <= col; i++){
// arr은 칼럼의 인덱스를 저장할 예정.
memset(arr, 0, sizeof(arr));
dfs(i, 0, -1);
}
return answer.size();
}
아래 코드는 조합을 시행하는 dfs다.
// 벡터 a와 벡터 b가 모두 같은 원소를 가지고 있는지 판단하는 함수다.
bool vector_is_equal(vector<string> a, vector<string> b){
int vec_size = a.size();
for(int i = 0; i < vec_size; i++){
if(a[i] != b[i]) return false;
}
return true;
}
// goal : 나는 인덱스를 goal개 만큼 집기로 했다.
// cnt : 나는 인덱스를 cnt개 만큼 집었다.
// idx : 나는 인덱스를 idx까지 골랐었다.
void dfs(int goal, int cnt, int idx){
// 조합을 통해 모두 집었다면,
if(goal == cnt){
// 기존에 찾아놓은 후보키를 포함하고 있는 지 검사
for(auto i : answer){
int ans_idx = 0;
for(int j = 0; j < goal; j++){
if(i[ans_idx] == arr[j]) ans_idx++;
if(ans_idx >= i.size()) break;
}
if(ans_idx >= i.size()) return;
}
// 후보키가 될 수 있는지 검사할 예정
// vector<vector<string>> relation에서 골라놓은 인덱스를 저장해놓은 arr에 존재하는 인덱스대로 하나의 tmp 벡터를 만들고, 이를 cmp 벡터에 넣어준다.
vector<vector<string>> cmp;
for(int i = 0; i < row; i++){
vector<string> tmp;
for(int j = 0; j < goal; j++)
tmp.push_back(rel[i][arr[j]]);
cmp.push_back(tmp);
}
// 비교하는 과정
for(int i = 0; i < row; i++){
for(int j = i + 1; j < row; j++){
// 벡터가 하나라도 같은 게 있으면 후보키가 되지 못함
if(vector_is_equal(cmp[i], cmp[j])) return;
}
}
// 벡터가 모두 다르므로 후보키가 될 수 있다.
vector<int> answer_temp;
for(int i = 0; i < goal; i++)
answer_temp.push_back(arr[i]);
answer.push_back(answer_temp);
}
// 다음 조합 진행
else {
for(int i = idx + 1; i < col; i++){
arr[cnt] = i;
dfs(goal, cnt + 1, i);
}
}
}
코드
#include <bits/stdc++.h>
using namespace std;
vector<vector<string>> rel;
vector<vector<int>> answer;
int col, row, arr[21];
bool vector_is_equal(vector<string> a, vector<string> b){
int vec_size = a.size();
for(int i = 0; i < vec_size; i++){
if(a[i] != b[i]) return false;
}
return true;
}
void dfs(int goal, int cnt, int idx){
if(goal == cnt){
for(auto i : answer){
int ans_idx = 0;
for(int j = 0; j < goal; j++){
if(i[ans_idx] == arr[j]) ans_idx++;
if(ans_idx >= i.size()) break;
}
if(ans_idx >= i.size()) return;
}
vector<vector<string>> cmp;
for(int i = 0; i < row; i++){
vector<string> tmp;
for(int j = 0; j < goal; j++)
tmp.push_back(rel[i][arr[j]]);
cmp.push_back(tmp);
}
for(int i = 0; i < row; i++){
for(int j = i + 1; j < row; j++){
if(vector_is_equal(cmp[i], cmp[j])) return;
}
}
vector<int> answer_temp;
for(int i = 0; i < goal; i++)
answer_temp.push_back(arr[i]);
answer.push_back(answer_temp);
}
else {
for(int i = idx + 1; i < col; i++){
arr[cnt] = i;
dfs(goal, cnt + 1, i);
}
}
}
int solution(vector<vector<string>> relation) {
row = relation.size();
col = relation[0].size();
rel = relation;
for(int i = 1; i <= col; i++){
memset(arr, 0, sizeof(arr));
dfs(i, 0, -1);
}
return answer.size();
}
나는 이런 문제에 약한 것 같다. 날짜와 데이터가 섞여서 최적의 결과를 나타내는 문제들. 연습을 좀 해야겠다.
본론
dates와 supplies를 묶어서 관리하기 위해 새로운 구조체 Data를 하나 선언한다.
struct Data{
int date;
int supply;
Data(int a, int b): date(a), supply(b) {}
};
밀가루를 공급받기 위해 판단의 기준이 되는 우선순위 큐 pq 하나와, 밀가루를 공급받기 위한 날짜의 후보를 넣어두는 큐 q 하나를 선언한다.
우선순위 큐
priority_queue<Data, vector<Data>, cmp> pq;
큐
queue<Data> q;
for(int i = 0; i < dates.size(); i++)
q.push(Data(dates[i], supplies[i]));
후보들은 q에서 대기하고 있다가, pq에 넣어질 수 있는 조건이 충족되면 그때서야 pq에 넣어진다.
조건
내가 가지고 있는 밀가루 양보다 q.front().date가 작아야 한다.
why : 공장의 운영이 끊기면 안된다. 밀가루 양 current가 current일까지 공장이 운영될 수 있는 날이고, 밀가루는 미리 받아놓거나 (current > q.front().date인 경우) 밀가루가 떨어진 바로 다음날 새벽 (current = q.front().date인 경우) 에 받을 수 있기 때문에, 다음과 같은 식이 성립될 때 pq에 넣을 수 있다.
current >= q.front().date
pq에 넣어진 것들은 supply가 가장 큰 순서대로 나열된다. 이는 밀가루를 greedy하게 골라 다른 날짜에서 밀가루를 또 받는 일을 방지한다.
struct cmp{
bool operator()(Data a, Data b){
return a.supply < b.supply;
}
};
pq의 top에 있는 것이 공장이 받을 밀가루가 되므로, current += pq.top().supply;
코드
#include <bits/stdc++.h>
using namespace std;
struct Data{
int date;
int supply;
Data(int a, int b): date(a), supply(b) {}
};
struct cmp{
bool operator()(Data a, Data b){
return a.supply < b.supply;
}
};
int solution(int stock, vector<int> dates, vector<int> supplies, int k) {
int answer = 0;
int current = stock;
priority_queue<Data, vector<Data>, cmp> pq;
queue<Data> q;
for(int i = 0; i < dates.size(); i++)
q.push(Data(dates[i], supplies[i]));
while(current < k){
while(!q.empty() && current >= q.front().date){
pq.push(q.front());
q.pop();
}
current += pq.top().supply;
pq.pop();
answer++;
}
return answer;
}
