뚝딱뚝딱

첫 sql문 문제 풀이이다.

데이터베이스설계를 들으면서 sql문은 어느 정도 익숙해져 있고, 정처기를 준비하면서도 복잡한 sql문을 공부해 왔어서 어렵지 않게 문제를 풀 수 있었으나...! 역시 디테일한 부분은 좀 더 공부할 필요가 있음을 느낀 첫 문제였다.

DATE 형식의 컬럼의 출력 형태 변환하는 방법!

이 문제에서 내가 걸렸던 부분은 주의사항에 있는 DATE 형식을 주어진 예제의 출력결과처럼 변경하여 출력할 수 있도록 하는 것이었다.

문제에서 PUBLISHED_DATE의 형식을 'YYYY-MM-DD' 형태로 출력하도록 요구하고 있다.

처음에는 이 부분을 확인하지 못하고 그냥 출력해 보았는데, 뒤에 상세한 시간까지 출력되는 것을 확인하였다.

이렇게 시간까지 표시되는 것을, 날짜만 표시되도록 변경해주어야 한다.

이때 사용할 수 있는 것이 DATE_FORMAT() 함수이다!!

mysql : DATE를 원하는 형식으로 변경하기

각 sql마다 다른데, 내가 사용하는 mysql을 기준으로는 다음과 같은 방식을 사용할 수 있다.

1. 날짜→문자열로 변환

DATE FORMAT(날짜, 출력 형식)

문제 예시 ) DATE_FORMAT(A.PUBLISHED_DATE, '%Y-%m-%d')

위의 형태의 날짜를 '2020-01-02'의 형태로 리턴해준다.

2. 문자열→날짜로 변환
 
STR_TO_DATE(문자, 출력 형식)
 
예시) 
STR_TO_DATE('20080101', '%Y-%m-%d')

20080101이라는 문자를 2008-01-01의 형태의 날짜로 리턴해준다.

---

여기에서 주의할 점은 '%Y-%m-%d' 이 부분인데, 여기에서 Y이면 '2020'과 같은 형태를, m이면 '03'과 같은 형태를, d이면 '23'과 같은 형태로, 보통 'yyyy-mm-dd'형식의 출력을 얻을 수 있다.
이 부분이 왜 헷갈리냐면, 저 문자를 대문자로 쓰느냐, 소문자로 쓰느냐에 따라 다른 출력이 되기 때문이다.
나도 처음에는 모두 대문자로 써서, 월은 'march', 일은 'secondary_three' 이런식으로 나왔다.
따라서 형식에 따라 잘 구분지어 주어야 한다. 
자세한 내용은 아래의 표를 참고하자.

**FORMAT설명

위의 방법을 사용하고 출력한 결과이다.

원하는 출력 형태를 얻을 수 있었다!

전체 코드는 아래와 같다.

SELECT A.BOOK_ID, B.AUTHOR_NAME, DATE_FORMAT(A.PUBLISHED_DATE, '%Y-%m-%d') AS PUBLISHED_DATE
FROM BOOK A JOIN AUTHOR B ON A.AUTHOR_ID=B.AUTHOR_ID 
WHERE A.CATEGORY='경제' 
ORDER BY A.PUBLISHED_DATE;

join할 때 조인할 테이블을 A, B이런식으로 지정해주는 건 정처기 때 버릇.. 아주 좋은 버릇인거 같다.

가끔 안해도 돌아갈 때가 있는데, 정확하게 쓰는 거는 위가 맞기 때문에, 최대한 쓰려고 한다.

select ~ from~join~on~where~order by~ 순으로 알아보기 쉽게 줄바꿈 해 두었다.

* DATE_FORMAT(A.PUBLISHED_DATE, '%Y-%m-%d') AS PUBLISHED_DATE 

이런 부분의 경우, 예시 출력 형태를 보고 컬럼 이름을 잘 지정해주는 것이 중요한 포인트이다.

아깝게 틀릴 수 있는 사소한 문제이기 때문이다!

이상 백준허브 연동 겸 가볍게 풀어본 sql문제였다.

그리디 알고리즘의 대표적인 예시 중 하나인 동전 문제를 풀어보자.

다음과 같은 절차로 해결할 수 있다.

1. 선택 절차 : 거스름돈 문제에서 가장 가치가 큰 동전부터 선택 한다.
2. 적절성 검사 : 만약 선택된 동전의 가치가 거스름돈보다 크다면 다음으로 작은 동전을 선택한다.
3. 해답 검사 : 합이 일치하면 거스름돈 문제가 해결된 것이다.

+여기에 부가적인 절차는 주석으로 작성하였다.

#include<iostream>

using namespace std;

int main() {
	int N, K;
	cin >> N >> K;

	int *a = new int[N];

	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}

	int cnt = 0; //동전의 개수를 저장할 것이다

	for (int i = N - 1; i >= 0; i--) {//문제에서 동전의 가치를 오름차순으로 저장했으므로,뒤에서부터 비교한다
		if (a[i] <= K) {//입력받은 가치보다 작은 것중 가장 큰 걸 선택
			cnt += (K / a[i]);//큰 가치로 몇번 나누어질 수 있는지를 구하고 더한다
			K = K % a[i];//그 나머지를 K로 갱신한다
		}
	}

	cout << cnt;//최종 cnt를 출력한다
}

문제에서 예시로 주어진 접근 순서를 보고, 가장 멀리 있는 집부터 접근해야 한다는 건 다 캐치했을 것이다.

그런데 cap만큼 감소시키는 것을 불규칙한 vector 값에 바로 접근해서 푸는 건 복잡할 것 같았다.

집의 번수 = 물류창고로부터의 거리이고, 거리에 대한 정보도, 각 거리에 있는 집에 두어야 할/ 수거해야 할 택배 개수에 대한 정보도 동시에 가질 수 있는 방법이 무엇이 있을까 생각하다 보니.. 스택이 생각났다.

내가 접근한 방법은 delieveries와 pickups에서 0이 아닌 값을 갖는 인덱스+1(거리는 1부터니까)를 각 택배 개수만큼 스택에 차례로 넣는것이다. 그럼 스택은 뒤에서부터 빼니까, 우리가 원하는 대로 가장 멀리있는 집의 택배를 이용할 수 있게 된다.

두 스택에서 cap만큼씩 삭제하고, 이때 각각의 스택에서 맨 처음 삭제한 값이 가장 멀리까지 가는 거리가 되므로, top1과 top2에 저장해 둔다. 이때 주의할 점은 스택이 비어있지 않은 경우에만 삭제 해야 한다는 점이다.

한번 순회하고 갔다올 때 top1과 top2 중 더 큰 값에 따라서 갔다와야 한번에 해결할 수 있기 때문에 더 큰 값의 2배 만큼을 answer에 더해주면 된다!

c++ 코드는 아래와 같다.

#include <string>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
	long long answer = 0;
	
	stack<int> st1, st2;

	for (int i = 0; i < n; i++) {//스택에 다 넣어준다
		for (int j = 0; j < deliveries[i]; j++) {
			st1.push(i + 1);
		}
		for (int k = 0; k < pickups[i]; k++) {
			st2.push(i + 1);
		}
	}

	int top1, top2;

	while (!st1.empty() || !st2.empty()) {//둘다 스택이 비워지면 그만
		top1 = top2 = 0;
        for (int i = 0; i < cap; i++) {
			if (!st1.empty()) {
				if (i == 0) {
					top1 = st1.top();
				}
				st1.pop();
			}

			if (!st2.empty()) {
				if (i == 0) {
					top2 = st2.top();
				}
				st2.pop();
			}
		}
		answer += max(top1, top2) * 2;
		
	}
	
	return answer;
}

요격 시스템

요격 시스템 문제는 먼저 sorting을 해주어야 한다.

이 때 어느 값을 기준으로 정렬할 것인지가 관건이 되는데..

주어진 예제에서 어떤 폭격 미사일 하나의 구간만을 고려한다고 해보자.

 예를 들면 4-5 구간의 미사일만을 고려해 보자.

4를 요격 범위의 start로 S, 5를 요격 범위의 end로 E라고 표현하고, 현재의 요격 범위로 두자.

end가 4(현재의 S)보다 작은 미사일의 경우, 현재의 요격 범위에 포함될 수 없다.

따라서 start가 5(현재의 E)보다 큰 미사일의 경우에도 현재의 요격 범위에 포함될 수 없다.

그러므로 요격 범위에 들어올 자격이 되는지는, 각 미사일 구간의 end 포인트 지점에 달려있다.

따라서 end를 기준으로 오름차순 정렬해준다.

end를 기준으로 오름차순 정렬해주면

[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4] → [1,4], [4,5], [3,7], [4,8], [5,12], [11,13], [10,14]
이 된다.

미사일을 어차피 한번이상 쏘게 되어 있으니까, count는 1로 시작한다.

처음 요격 구간을 [1,4]로 설정하고 그 다음 구간부터 차례로 순회한다.

첫 S=1, E=4가 된다.

다음 미사일의 범위가 [4,5]이고, 이것의 시작 지점인 4가 현재 요격 구간의 E보다 작아야 한번에 쏠 수 있다.
(엔드 포인트인 4에서는 쏘지 못한다. 조건에 명시되어 있다.)

그런데 E보다 작지 않기 때문에 이 구간에는 첫번째 미사일 구간 빼고는 더이상 요격할 미사일이 없는 것이다.

따라서 count를 1올려주고, 다음 미사일 구간의 시작점을 s로, 끝점을 e로 하여 새로운 요격 범위를 갱신하고 위 과정을 반복하도록 한다.

그럼 최종 요격 발사 횟수를 COUNT를 반환함으로써 얻을 수 있다.

C++로 해결한 코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(vector<int> &v1, vector<int> &v2) {
	if (v1[1] == v2[1])
		return v1[0] < v2[0];
	else return v1[1] < v2[1];
}

int solution(vector<vector<int>> targets) {
	
	int answer = 0;

	sort(targets.begin(), targets.end(), cmp);

	int e = targets[0][1];

	answer++;

	for (int i = 1; i < targets.size(); i++) {
		if (targets[i][0] < e) {
			continue;
		}
		else {
			answer++;
			e = targets[i][1];
		}

	}

	return answer;
}

대충 만든 자판

이제는 익숙해진 문자열과 숫자 한번에 다루기!

문제를 몇번 풀어보니, 이 문제 역시 문자열과 숫자 개념이 더해진 것임을 바로 파악할 수 있었고, map을 사용하여 쉽게 해결할 수 있었다.

자판의 등장하는 문자를 char형태의 index로 보고, 어떤 위치의 버튼이든 최소한으로 눌렀을 때를 그 알파벳의 버튼 횟수로 저장하도록 하였다.

그러니까 keymap을 순회하면서, 등장하는 문자를 map의 인덱스로 넣고, 해당 위치를 저장하였다.

그리고 같은 문자가 또 한번 등장할 때마다 기존에 저장해 두었던 위치와 비교해보아서 더 작은 위치로 갱신되도록 하였다.

이렇게 하여 문자당 최소 터치 수를 map에 저장해 두면 80 프로는 다 한 것이다!!

이제 targets을 순회하면서 해당 문자의 최소 터치 수가 저장된 map에서 값을 가져와 count시키고, 

만약 해당 문자가 map에 존재하지 않는다면, 작성할 수 없는 문자열이므로, 문제에서 요구한 것처럼 count를 -1로 하고, 해당 문자열은 넘어가도록 코드를 구현했다.

그리고 한 문자열씩 돌때마다 answer벡터에 count값을 push해주면 끝!

코드는 아래와 같다.

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    
    map<char, int> m1;

	for (int i = 0; i < keymap.size(); i++) {
		for (int j = 0; j < keymap[i].size(); j++) {
			if (m1.find(keymap[i][j]) == m1.end()) {//map에 존재하지 않은 문자면 입력
				m1.insert(pair<char, int>(keymap[i][j], j+1));
			}
			else {
				if (m1[keymap[i][j]] > j + 1) {
					m1[keymap[i][j]] = j + 1;//더작은 값으로 바꾼다
				}
			}
		}
	}

	int cnt;

	for (int i = 0; i < targets.size(); i++) {
		cnt = 0;
		for (int j = 0; j < targets[i].size(); j++) {
			if (m1.find(targets[i][j]) == m1.end()) {
				cnt = -1;
				break;
			}
			auto temp = targets[i][j];
			cnt += m1[temp];
		}
		answer.push_back(cnt);
	}

    
    return answer;
}

n칸의 벽 중 덧칠해야 할 칸 번호가 적힌 벡터를 참고하여, 한번에 m칸 칠할 수 있는 페인트 롤러를 이용해 최소의 페인트칠 횟수 구하는 문제.

문제의 조건을 보면 section 벡터의 크기가 무조건 1이상이므로, 최소 한번은 칠해야 한다는 점을 기억하자.

section[0]에서 시작해서 한번 칠할 때 section[0]+m-1번 칸 까지는 칠해진다.

그리고 한번 칠했으므로, 칠한 횟수(answer)를 1 증가시켜준다.

temp에 section[0]+m에 대한 값을 저장해두고, for문을 통해 section[1]부터 section의 크기만큼 순회한다.

그래서, 다음 칠해야 할 칸이, 이전에 한번 칠했던 범위에 포함이 되는지를 살펴보고, 포함이 된다면 현재 회차는 넘어가도록 한다.이는 현재 section[i]의 값이 temp보다 작은지를 보면 된다.

만약 현재 section[i]의 값이 temp와 같거나 더 크다면 이전에 칠했을 때, 같이 칠해지지 못한 것이므로, temp를 다시 section[i]+m으로 갱신해주고, 이를 기준으로 한번 더 칠하는 것이므로 answer를 1 증가 시킨다.

위 과정을 모든 section벡터 값에 대해 순회해주면 최소 페인트 칠 횟수를 반환할 수 있다! 

코드는 아래와 같다.

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 0;
    
    int temp = section[0] + m;
	answer++;
	
	for (int i = 1; i < section.size(); i++) {
		if (section[i] < temp) {//한번 칠한것에 같이 포함이 되면
			continue;//넘어간다
		}
		else {
			temp = section[i] + m;
			answer++;
		}
	}
    
    return answer;
}