요약: 어떤 스트링 하나와 코드들이 주어졌을 때 스트링을 코드에 맞게 디코드 하는 문제입니다.
설명: codes를 파싱해서, 키가 string이고 밸류가 char인 map에다 넣습니다. Map 자료구조를 사용한 이유는: 탐색속도가 빠르기 때문입니다.(logN)
스트링 encoded를 처음부터 sweeping하는데, 빈 스트링(empty)에서, 한 글자씩 붙여가면서 현재 스트링이map에존재하면, 그 스트링과 연결된 밸류(즉, 알파벳 하나 또는 '\n')를 result 스트링에 추가하고, 다음 문자로 넘어가는식으로 반복합니다.
#include <bits/stdc++.h> // 모든 표준 라이브러리 헤더들을 가져오는 전처리문
using namespace std; // std라는 namespace에서 사용하려고 한다. 그냥 암기하면 됨
/*
각 element가 string으로 이루어진 벡터 codes와 스트링 encoded를 매개변수로 받아서,
스트링 encoded를 디코드한 결과값을 리턴하라.
1. codes를 파싱해서, 키가 string이고 밸류가 char인 huffman_map을 만든다. (구글에 'c++ map 사용법'으로 검색)
2. 스트링 encoded를 처음부터 sweeping하는데,
빈 스트링(empty)에서, 한 글자씩 붙여가면서 현재 스트링이 huffman_map에 키값(!!)으로 존재하는 스트링인지 아닌지를 판별한다.
만약 huffman_map에 현재 스트링이 키 값으로 존재하면,
그 스트링과 연결된 밸류(즉, 알파벳 하나 또는 '\n')를 result 스트링에 추가하고, i에다가 j+1을 대입하고 for j문을 탈출(break)한다. (한번에 6칸씩 넘어가는 부분)
현재 스트링이 map에 없으면 한 글자를 더 붙여본다. (for문에서 j++하는 부분)
*/
string decode(vector<string> codes, string encoded) {
int n = codes.size(); // 총 몇 줄인지를 의미. 예제 데이터에서 n = 7
/*
map 하나(map은 자료구조임)를 선언하는데, 키값의 타입은 string이고, 밸류의 타입은 char이다. (변수명이 huffman_map)
ex) "111000"을 키로 넣으면 거기에 해당하는 밸류 "a"를 빠른 속도로 가져온다. (insert find delete 모든 연산 시간복잡도 log n으로, 매우 빠름)
구글에 c++ map 사용법 검색하면 잘 나옴.
*/
map<string, char> huffman_map;
for (int i=0; i<n; i++) { //i를 0부터 n-1까지 증가시키면서
/*
codes[0]: "a 100100"
codes[1]: "b 100101"
....
codes[6]: "q 000001"
*/
/*
스트링 codes[i]에서, '\t'가 몇 번째 인덱스에 위치하는 지를 찾는다.
ex) codes[i]가 "a\t100100"인 경우
tab_pos = 1이다.
ex) codes[i]가 "[newline]\t111111"인 경우
tab_pos = 9이다.
c++ string에는 find라는 함수가 있다. find('\t')를 호출하면 \t의 위치를 리턴해줌
(자세한건 구글링해서 c++ string find 사용법으로 검색)
*/
int tab_pos = codes[i].find('\t');
/*
스트링 codes[i]에서, tab 위치 바로 다음 인덱스부터 문자열 끝까지를 추출해서, encoded_value에 저장한다.
ex) codes[i]가 "a\t100100"인 경우
encoded_value = "100100"이다.
ex) codes[i]가 "[newline]\t111111"인 경우
encoded_value = "111111"이다.
c++ string에는 substr라는 함수가 있다. substr(k)를 호출하면 k번째 위치부터 마지막 위치까지의 문자열을 추출해서 리턴한다.
(자세한건 구글링해서 c++ string substr 사용법으로 검색)
*/
string encoded_value = codes[i].substr(tab_pos + 1);
if (tab_pos != 1) { // tab_pos가 1이 아니라면 (즉, codes[i]의 맨 앞 부분이 [newline]인 경우)
/*
huffman_map 에다가 키-밸류를 저장하는데,
키는 encoded_value이고 (encoded_value는 "111111")
밸류는 '\n'이다.
*/
huffman_map[encoded_value] = '\n';
}
else { // tab_pos가 1이면 (즉, codes[i]의 맨 앞 글자가 알파벳인 경우)
/*
huffman_map 에다가 키-밸류를 저장하는데,
키는 encoded_value이고 (encoded_value는 "100100" "000001" 이런 애들)
밸류는 알파벳 아무거나 하나(p, q, a, b, c, d 이런 애들)이다.
*/
huffman_map[encoded_value] = codes[i][0]; //codes[i][0]은 스트링 codes[i]의 맨 앞 문자를 의미한다. 문자 하나니깐 얘는 char형태이다.
}
}
string result = ""; //최종 결과값을 저장할 문자열. 처음에는 빈 문자열 ""이다.
int encoded_str_len = encoded.size(); // 디코드할 문자열 encoded의 길이 저장. (예제 데이터에서는 encoded_str_len = 42)
for (int i=0; i<encoded_str_len; ) { //스트링 encoded를 처음부터 sweeping한다. 단, i++ 부분이 없다. 왜냐면 한번에 뛸 거기 땜에
// 빈 스트링(empty)에서, 한 글자씩 붙여가면서 현재 스트링이 huffman_map에 키값(!!)으로 존재하는 스트링인지 아닌지를 확인할 것이다.
string cur_str = ""; //현재 스트링. 여기다가 계속 한글자씩 붙일 예정. huffman_map에 이 스트링이 존재할 때까지.
for (int j=i; j<encoded_str_len; j++) { //j는 i에서 시작해서, 일단 끝까지 계속 한칸씩 올려본다. (j++해서)
cur_str += encoded[j]; //현재 스트링에다가 j번째 문자 하나를 붙여본다.
/*
c++ map에는 find라는 함수가 있다. 이 함수는 전체 map에서 특정 키의 위치를 알려준다.
만약, 전체 map에 검색하고자하는 키가 존재하지 않는 경우, end()를 리턴한다.
그렇지 않으면(전체 map에 검색하고자하는 키가 존재하는 경우), end()가 아닌 어떤 위치를 알려준다.
즉, huffman_map이라는 맵에서 스트링 cur_str를 키로 넣어서 검색했을 때
키가 맵에 존재하지 않는다면 huffman_map.find(cur_str) == huffman_map.end()이고
키가 맵에 존재한다면 huffman_map.find(cur_str) != huffman_map.end()이다. (c++ map 문법이니 구글링해보자)
*/
if (huffman_map.find(cur_str) != huffman_map.end()) { // huffman_map에 현재 스트링 cur_str이 키값으로 존재한다면!!
// 그 스트링과 연결된 밸류(즉, 알파벳 하나 또는 '\n')를 result 스트링에 추가한다.
// c++ map에서, (MAP[키] == 밸류) 라고 생각하면 된다.(즉, 배열과 비슷한 느낌으로 쓸 수 있다. 인덱스에다가 숫자가 아니라 스트링 키를 넣으면, 밸류를 바로 꺼낼 수 있다.)
result += huffman_map[cur_str]; // huffman_map 전체에서 cur_str이라는 키를 넣어서, 밸류를 꺼내려면 huffman_map[cur_str] 로 쓰면 된다.
i = j+1; // i에다가 j+1을 대입한다. (한번에 6~7칸씩 넘어가던 부분)
break; // for j문만 탈출. for i문으로 이동한다.
}
}
}
return result; //결과값을 리턴한다.
}
int main()
{
int n = 7; // huffman codes 갯수
vector<string> codes ={
"a\t100100",
"b\t100101",
"c\t110001",
"d\t100000",
"[newline]\t111111",
"p\t111110",
"q\t000001"
};
string encoded = "111110000001100100111111100101110001111110"; //디코드할 문자열
// decode 함수 호출 후 결과 스트링 저장
string answer = decode(codes, encoded);
// 결과값 출력
cout << answer;
return 0; //정상 종료됨을 의미하는 return 0
}
주석 제거용
#include <bits/stdc++.h>
using namespace std;
string decode(vector<string> codes, string encoded) {
int n = codes.size();
map<string, char> huffman_map;
for (int i=0; i<n; i++) {
int tab_pos = codes[i].find('\t');
string encoded_value = codes[i].substr(tab_pos + 1);
if (tab_pos != 1) {
huffman_map[encoded_value] = '\n';
}
else {
huffman_map[encoded_value] = codes[i][0];
}
}
string result = "";
int encoded_str_len = encoded.size();
for (int i=0; i<encoded_str_len; ) {
string cur_str = "";
for (int j=i; j<encoded_str_len; j++) {
cur_str += encoded[j];
if (huffman_map.find(cur_str) != huffman_map.end()) {
result += huffman_map[cur_str];
i = j+1;
break;
}
}
}
return result;
}
int main()
{
int n = 7;
vector<string> codes ={
"a\t100100",
"b\t100101",
"c\t110001",
"d\t100000",
"[newline]\t111111",
"p\t111110",
"q\t000001"
};
string encoded = "111110000001100100111111100101110001111110";
string answer = decode(codes, encoded);
cout << answer;
return 0;
}
요약: 시작시간과 끝나는 시간이 주어지는 N개의 회의가 있을 때 하나의 회의실에 최대로 많이 넣을 수 있는 회의의 개수를 구하는 문제입니다.
설명: 일찍 끝나는 회의 순으로 정렬한 후, 순서대로 회의실이 비어있으면 회의를 집어넣으면 됩니다. 끝나는 시간을 기준으로 했던 이유를 보여주는 예시) 1~10시 까지 회의, 2~4시 까지의 회의, 4~5시 까지의 회의 가 있으면 1~10시까지의 회의 보다 나머지 두 개의 회의를 넣는게 더 이득이다.
#include <bits/stdc++.h> // 모든 표준 라이브러리 헤더들을 가져오는 전처리문
using namespace std; // std라는 namespace에서 사용하려고 한다. 그냥 암기하면 됨
// 구조체 Time 선언
struct Time {
int start_time;
int end_time;
};
/*
정렬의 기준을 정의한다. (사용자 정의로 customizing해서 쓸 수 있음)
임의의 두 Time 구조체끼리 비교할 때,
swap을 해서 위치를 바꿀 건지(false, 즉 현재 조건을 만족하지 않음), 그대로 둘건지(true, 현재 조건을 만족함)를 리턴한다.
*/
bool compare(Time t1, Time t2) {
if (t1.end_time == t2.end_time) { // t1의 종료 시간(end_time)과 t2의 종료 시간(end_time)이 같다면.
return t1.start_time < t2.start_time; // t1의 시작 시간(start_time) < t2의 시작 시간(start_time) 조건의 결과값(true 또는 false)을 리턴한다. (즉, 오름차순으로 정렬하게 된다.)
}
// 그렇지 않은 경우(즉, t1과 t2의 종료 시간이 다른 경우)
return t1.end_time < t2.end_time; // t1의 종료시간 < t2의 종료시간 조건을 리턴한다. (즉, 오름차순으로 정렬하게 됨)
}
/*
문제:
n개의 회의가 주어지고, 각 회의는 시작 시간과 지속 시간이 있다. (당연히 종료시간=시작시간+지속시간이다.)
회의실이 1개일 때, 최대한 많은 회의를 커버하고 싶다. 이 때 최대 회의 수는?
솔루션:
일찍 끝나는 회의 순으로 정렬한 후, 순서대로 sweeping하면서 선택한다.
(구글에 "회의실 문제" 또는 "회의실 배정 문제"로 검색하면, 자세한 설명들이 있다.)
(참고로, 이 문제는 욕심쟁이 기법(greedy) 알고리즘의 가장 대표적인 문제이다.)
*/
int maxEvents(vector<int> arrival, vector<int> duration) {
int n = arrival.size(); // 회의 갯수를 n에 저장
/*
각 element의 타입이 구조체 Time인 벡터 times를 선언. 크기는 n
구조체 Time을 선언해서 새로운 벡터를 만드는 이유:
원래 문제에서는 시작 시간 arrival, 지속 시간 duration가 매개변수로 주어지는데,
구조체로 묶어서 (시작 시간, 종료 시간) 형태로 바꿔서 저장하면, sort할 때 편하다.
*/
vector<Time> times(n);
for (int i=0; i<n; i++) { // n개를 훑으면서
times[i].start_time = arrival[i]; // 시작 시간은 그대로..
times[i].end_time = arrival[i] + duration[i]; // 당연히 종료 시간 = 시작 시간 + 지속 시간이다.
}
/*
times 벡터를 정렬한다. 정렬 기준은 compare 함수이다.
종료 시간(end_time) 순으로 정렬하되, 종료 시간(end_time)이 같은 경우엔 시작 시간(start_time)이 빠른 놈으로 한다.
근데 사실 시작 시간 순으로 sort안해도 된다. 시작 시간은 아무렇게나해도 됨. 잘 생각해보면됨
*/
sort(times.begin(), times.end(), compare);
int last_finished_time = 0; // 마지막 회의 종료 시간 (시작 전에는 time = 0. 모든 start_time은 1 이상이니까 처음엔 0으로 두면 됨)
int result = 0; // 선택한 회의 갯수. (시작 전에는 당연히 0개)
for (int i=0; i<n; i++) { // 정렬된 회의들을 순서대로 sweeping하면서(훑으면서)
// 마지막 회의 종료 시간이 i번째 회의의 시작시간(start_time) 이하인 경우 (즉, 회의실이 비어서 현재 회의가 들어갈 수 있는 경우)
if (last_finished_time <= times[i].start_time) {
last_finished_time = times[i].end_time; // last_finished_time을 i번째 회의의 종료시간(end_time)으로 갱신해버린다. (즉, 회의를 추가해서 시작하고 끝났음)
++result; // i번째 회의를 선택했으므로 result에 +1
}
}
return result; // 결과값 result를 리턴
}
int main()
{
// 입력하는 부분 생략하고, 바로 변수에 저장
int n = 3; // arrival[] size n = 3
vector<int> arrival = { 1, 3, 5 }; // arrival = [1, 3, 5]
vector<int> duration = { 2, 2, 2 }; // duration = [2, 2, 2]
// maxEvents 함수 호출하고 결과값 저장
int answer = maxEvents(arrival, duration);
// 결과값 출력
cout << answer;
return 0; //정상 종료됨을 의미하는 return 0
}
주석 제거용
#include <bits/stdc++.h>
using namespace std;
struct Time {
int start_time;
int end_time;
};
bool compare(Time t1, Time t2) {
if (t1.end_time == t2.end_time) {
return t1.start_time < t2.start_time;
}
return t1.end_time < t2.end_time;
} //끝나는 시간을 기준으로 정렬하기 위해 compare 함수를 만들었습니다.
int maxEvents(vector<int> arrival, vector<int> duration) {
int n = arrival.size();
vector<Time> times(n);
for (int i=0; i<n; i++) {
times[i].start_time = arrival[i];
times[i].end_time = arrival[i] + duration[i];
}
sort(times.begin(), times.end(), compare);
int last_finished_time = 0;
int result = 0;
for (int i=0; i<n; i++) {
if (last_finished_time <= times[i].start_time) {
last_finished_time = times[i].end_time;
++result;
}
}
return result;
}
int main()
{
int n = 3;
vector<int> arrival = { 1, 3, 5 };
vector<int> duration = { 2, 2, 2 };
int answer = maxEvents(arrival, duration);
cout << answer;
return 0;
}
