[2021 ICT 하반기] 5번 문제

요약: 어떤 스트링 하나와 코드들이 주어졌을 때 스트링을 코드에 맞게 디코드 하는 문제입니다.

 

설명: 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; 
}