DO MY BEST

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

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

문제요약: 어떤 2차원 grid가 주어지고 각 셀은 벽 또는 빈 공간이고, 각 셀을 동서남북으로 이동할 수 있고 한칸을 이동하는데 걸리는 시간은 1입니다. 시작점 left-top에서 도착점 right-bottom까지 이동하는 시간이 문제에서 주어지는 maxTime 이하이면 Yes를 리턴하고 아니면 No를 리턴하는 문제입니다.

요약: 출발지점부터 도착지점까지 너비우선탐색(BFS)를 돌려서 도착지점까지의 최단거리를 구합니다. 그리고 도착지점까지의 최단거리가 문제에서 주어진 maxTime초과이거나 혹은 벽에 막혀서 도착지점까지 도착하지 못하는경우 No를 리턴하고 아닌 경우 다 Yes로 리턴합니다.

*BFS: 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이고 큐를 사용한다.

3번 문제

#include <bits/stdc++.h> // 모든 표준 라이브러리 헤더들을 가져오는 전처리문
using namespace std; // std라는 namespace에서 사용하려고 한다. 그냥 암기하면 됨

/*
   문제:
      어떤 grid(2차원 맵이겠죠)가 주어지고, 각 cell은 '#' 또는 '.'이다. ('#'이면 벽이고, '.'이면 빈 공간이라고 생각하면 됨)
      각 cell을 동서남북으로 이동할 수 있고, 한 칸을 이동하는 데 걸리는 시간은 1이다.
      이 때, 시작점(left top)에서 도착점(right bottom)까지 이동하는 시간이 (문제에서 주어지는 maxTime) 이하이면 Yes를 리턴하고 아니면 No를 리턴하라.
         (주의: 모든 cell을 탐색했는데도, 벽('#')에 막혀서 도착점에 도달하지 못할 수도 있음)
*/
string reachTheEnd(vector<string> grid, int maxTime) {
   // 높이 height와 너비 width를 저장한다. 
   // height는 vector의 크기이고, width는 vector의 첫번째 원소(스트링)의 길이를 의미
   int height = grid.size(), width = grid[0].size(); 
   
   // 탐색 시, 동서남북으로 이동하기 위해 미리 세팅해둔 배열
   int dirx[4] = {0, 0, 1, -1}; 
   int diry[4] = {1, -1, 0, 0}; 

   // dist[i][j] 정의: 시작점 (0,0)에서 현재 좌표 (i,j)까지의 최단 거리를 저장
   // dist 벡터는 2차원 벡터로서, 원본 맵 grid와 같은 크기(height * width)를 갖는다. (예제 데이터대로면 3*4)
   // 높이는 height이고, 너비는 width인데, 모든 원소의 값을 -1로 초기화한다.
   // -1의 의미: 아직까지 도달하지 못했음을 의미. 만약 -1이 아니라면 이미 도착했다는 것이다.
   vector<vector<int> > dist(height, vector<int>(width, -1)); 
   dist[0][0] = 0; //시작점 (0,0)은 거리가 당연히 0이다. 시작점에서 시작점까지니까

   /*
      BFS(너비우선탐색)을 위해 큐를 선언하는데, 큐에 들어가는 각 원소는 pair 타입이다. (왜냐면 좌표를 저장해야하므로)
      pair는 STL에 내장된 구조체이다.
   */
   queue<pair<int, int> > q;
   q.push({0, 0}); //큐에다가 좌표(0, 0)을 넣는다. (BFS 탐색의 시작 위치가 (0,0)이라는 의미)
   while (!q.empty()) { // 큐가 비어있지않는 동안
      pair<int, int> cur = q.front(); // q에서 맨 앞에 있는 놈(좌표)를 꺼내서 cur라는 pair 타입 변수에 대입
      q.pop(); // cur에 저장했으니 q에서 맨 앞에 있는 놈을 삭제한다.
      for (int i=0; i<4; i++) { // 동서남북 4가지
         /*
            현재 좌표 (cur.first, cur.second)에다가 (+dirx[i], +diry[i])를 해서 next 좌표를 구한다.
            (+0, +1)하면 동쪽
            (+0, -1)하면 서쪽
            (+1, +0)하면 남쪽
            (-1, +0)하면 북쪽
         */
         pair<int, int> next = { cur.first + dirx[i], cur.second + diry[i] }; 

         // next 좌표(동서남북 중 하나)가 grid 밖으로 벗어나는 경우는 continue해서 스킵한다.
         if (next.first < 0 || next.first >= height || next.second < 0 || next.second >= width) continue;

         // next 좌표(동서남북 중 하나)가 원본 맵(grid)에서 벽인 경우('#'으로 표시된 경우) continue해서 스킵한다. (벽이니까 이동할 수 없음)
         if (grid[next.first][next.second] == '#') continue;

         // dist[next.first][next.second]가 -1이면(즉, 이때까지 한번도 next 좌표에 도달하지 못한 경우에만)
         if (dist[next.first][next.second] == -1) {

            // next 좌표의 distance 값을 갱신한다. (cur 좌표에서 1칸 움직인 것이므로, dist[cur.first][cur.second] + 1 값을 대입한다.)
            dist[next.first][next.second] = dist[cur.first][cur.second] + 1;

            // 큐에 next 좌표를 푸시한다.
            q.push(next);
         }
      }
   }

   /*
      도착점의 좌표는 (height-1, width-1)이다. (왜냐하면, 시작점이 (0,0)이기 때문에 도착점은 (height,width)가 아니라 -1씩 해줘야한다. 예를 들어 길이가 4인 배열은 인덱스가 0,1,2,3임)
      만약, 도착점의 distance가 -1이면 "No"를 리턴한다. (즉, 모든 cell을 탐색했는데도, 벽('#')에 막혀서 도착점에 도달하지 못한 경우) 
      또는 distance가 -1은 아니지만 maxTime보다 크다면 "No"를 리턴한다. (즉, 문제에서 주어진 시간 안에 도착하지 못한 경우)
      그 외의 경우는 모두 "Yes"
   */
   if (dist[height-1][width-1] == -1 || dist[height-1][width-1] > maxTime) return "No";
   return "Yes";
}

int main()
{
   // 입력하는 부분 생략하고, 바로 변수에 저장
   int n = 3; // size of grid[] rows
   vector<string> grid = { "..##", "#.##", "#..." }; //각 element의 타입이 string인 1차원 벡터 grid를 선언한다. 크기는 n이다. (n은 row 갯수=높이를 의미)
   int maxTime = 5; // maxTime
   
   // reachTheEnd 함수 호출 후 결과값 저장
   string answer = reachTheEnd(grid, maxTime);
   
   // 결과값 출력
   cout << answer;

   return 0; //정상 종료됨을 의미하는 return 0
}

주석 제거용

#include <bits/stdc++.h> 
using namespace std; 

string reachTheEnd(vector<string> grid, int maxTime) {
   int height = grid.size(), width = grid[0].size(); 

   int dirx[4] = {0, 0, 1, -1}; 
   int diry[4] = {1, -1, 0, 0}; 

   vector<vector<int> > dist(height, vector<int>(width, -1)); 
   dist[0][0] = 0; 

   queue<pair<int, int> > q;
   q.push({0, 0}); 
   while (!q.empty()) { 
      pair<int, int> cur = q.front();
      q.pop(); 
      for (int i=0; i<4; i++) { 
         pair<int, int> next = { cur.first + dirx[i], cur.second + diry[i] }; 
         if (next.first < 0 || next.first >= height || next.second < 0 || next.second >= width) continue;
         if (grid[next.first][next.second] == '#') continue;
         if (dist[next.first][next.second] == -1) {
            dist[next.first][next.second] = dist[cur.first][cur.second] + 1;

            q.push(next);
         }
      }
   }

   if (dist[height-1][width-1] == -1 || dist[height-1][width-1] > maxTime) return "No";
   return "Yes";
}

int main()
{

   int n = 3; 
   vector<string> grid = { "..##", "#.##", "#..." }; 
   int maxTime = 5; 
   
   string answer = reachTheEnd(grid, maxTime);
   
   cout << answer;

   return 0;
}

요약: 어떤 string 하나가 주어졌을 때, 이 스트링의 모든 substring들이 distinct하도록(중복이 없도록) 만들기 위해, 원본 스트링에서 삭제해야하는 문자의 최소 갯수를 구하는 문제입니다. 원본 스트링에서 중복되는 알파벳이 하나라도 있는 경우 substring들이 중복되는 것은 자명합니다. 따라서 알파벳 26개의 frequency를 저장해서, 특정 알파벳의 frequency가 1개 초과인 경우에는 1개를 제외한 나머지를 삭제하는 방식으로 풀었습니다.

#include <bits/stdc++.h> // 모든 표준 라이브러리 헤더들을 가져오는 전처리문
using namespace std; // std라는 namespace에서 사용하려고 한다. 그냥 암기하면 됨

/*
   어떤 string 하나가 주어졌을 때, 이 스트링의 모든 substring들이 distinct하도록(중복이 없도록) 만들기 위해, 
   원본 스트링에서 삭제해야하는 문자의 최소 갯수를 구하라

   0. 아이디어
      원본 스트링에서 중복되는 알파벳이 하나라도 있는 경우, substring들이 중복됨은 자명하다. 
      ex) 원본 스트링이 "aba"인 경우, substrings = { "a", "b", "a", "ab", "ba", "aba" }인데 여기서 substring "a"와 "a"가 중복된다.
      따라서, 입력으로 주어지는 string에서, 모든 알파벳 a~z가 1개 이하여야 한다.
   
   1. 알파벳 26개가 각각 몇 번씩 나왔는 지(frequency)를 카운팅하는 벡터 alphabet_cnt을 선언한다. 벡터의 크기는 26이고 초기값은 0
   2. 입력으로 주어지는 string을 문자 하나씩 sweeping하면서(순서대로 읽으면서),
      해당 문자가 'a'이면 alphabet_cnt[0]을 증가시켜주고,
      해당 문자가 'b'이면 alphabet_cnt[1]을 증가시켜주고,
      ...
      해당 문자가 'z'이면 alphabet_cnt[25]를 증가시켜준다.
   3. alphabet_cnt[0]부터 alphabet_cnt[25]까지 읽으면서 (즉, 'a'의 갯수, 'b'의 갯수, ..., 'z'의 갯수를 보면서)
      만약 특정 알파벳이 1개 초과(2개 이상)이면, 삭제해야하는 문자이므로
      결과값 result에다가 alphabet_cnt[i] - 1을 추가한다. (왜 -1이냐면 1개는 남겨놔도 되므로)      
*/

int getMinDeletions(string s) {
   int n = s.size(); // 스트링 s의 크기를 저장. ex) 스트링이 "abab"이면 n은 4
   vector<int> alphabet_cnt(26, 0); // 알파벳 26개의 frequency를 저장하는 벡터 alphabet_cnt를 선언하고, 초기값을 모두 0으로 지정
   for (int i=0; i<n; i++) { //i는 0부터 시작해서, n 미만일동안 i를 하나씩 증가시킨다. (즉, 입력으로 주어지는 string을 문자 하나씩 sweeping하는 것)
      /*
         ex) s가 "abac"이면
         s[0] = 'a'
         s[1] = 'b'
         s[2] = 'a'
         s[3] = 'c'이다.

         s[i]-'a'는 무엇을 의미하는가?
            'a'는 아스키코드 값으로 변환하면 97이고, 'z'는 아스키코드로 123이다.
            따라서 s[i]에서 'a'를 빼면, 알파벳 'a'~'z'를 0~25 사이의 숫자로 바꿀 수 있다.
            참고로 s[i]-'a' 대신 s[i]-97로 대체 가능하다.

         i=0인 경우, s[0]-'a'는 0  ->  alphabet_cnt[0]을 +1시킨다.  (alphabet_cnt[0]은 1이 됨)
         i=1인 경우, s[0]-'a'는 1  ->  alphabet_cnt[1]을 +1시킨다.  (alphabet_cnt[1]은 1이 됨)
         i=2인 경우, s[0]-'a'는 0  ->  alphabet_cnt[0]을 +1시킨다.  (alphabet_cnt[0]은 2가 됨)
         i=3인 경우, s[0]-'a'는 2  ->  alphabet_cnt[2]을 +1시킨다.  (alphabet_cnt[2]은 1이 됨)
      */
      ++alphabet_cnt[s[i]-'a'];
   }
   int result = 0; //결과값을 저장할 변수 (원본 스트링에서 삭제해야하는 문자의 갯수)
   for (int i=0; i<26; i++) { //alphabet_cnt[0]부터 alphabet_cnt[25]까지 읽으면서 (즉, 'a'의 갯수, 'b'의 갯수, ..., 'z'의 갯수를 보면서)
      if (alphabet_cnt[i] > 1) { // 현재 알파벳의 frequency가 1보다 크면, 삭제해야하는 문자이므로
         result += (alphabet_cnt[i] - 1); // 결과값 result에다가 alphabet_cnt[i] - 1을 추가한다
      }
   }
   return result; //결과값을 리턴
}

int main()
{
   string s; //스트링 s 선언
   cin >> s; //스트링 입력
   
   int answer = getMinDeletions(s); // getMinDelettion 함수 호출해서 결과값을 answer 변수에 저장
   cout << answer; // 출력해서 확인

   return 0; //정상 종료됨을 의미하는 return 0
}

주석 제거용

#include <bits/stdc++.h> 
using namespace std; 

int getMinDeletions(string s) {
   int n = s.size();
   vector<int> alphabet_cnt(26, 0); 
   for (int i=0; i<n; i++) { 
      ++alphabet_cnt[s[i]-'a'];
   }
   int result = 0; 
   for (int i=0; i<26; i++) {
      if (alphabet_cnt[i] > 1) {
         result += (alphabet_cnt[i] - 1); 
      }
   }
   return result; 
}

int main()
{
   string s;
   cin >> s; 
   
   int answer = getMinDeletions(s);
   cout << answer;

   return 0; 
}

요약:  문제에서 주어진 tickets배열을 먼저 sort한 후 배열을 순서대로 읽으면서 바로 이전 원소와 비교해서 차가 0 또는 1 이면 같은 그룹으로 판단 하면서, 현재 그룹의 길이를 카운팅 해줍니다. 그리고 같은 그룹이 아닌 경우 그룹의 길이를 1로 초기화 시키고 모든 그룹의 길이중 가장 큰 값을 저장하여 리턴합니다. 

#include <bits/stdc++.h> // 모든 표준 라이브러리 헤더들을 가져오는 전처리문
using namespace std; // std라는 namespace에서 사용하려고 한다. 그냥 암기하면 됨

/*
   각 element의 타입이 int인 벡터(=배열) tickets를 매개변수로 받아서, 결과값(int타입)을 리턴하는 함수

   1. 벡터를 sort한다.
   2. 벡터의 각 원소를 차례대로 sweeping하면서(순서대로 읽으면서),
      바로 이전 원소와 비교해서 diff가 0 또는 1이면 같은 시퀀스(그룹)로 판단한다.
*/

int maxTickets(vector<int> tickets) {
   int n = tickets.size(); // int형 변수 n에다가 벡터 tickets의 길이를 대입
   sort(tickets.begin(), tickets.end()); // 벡터 tickets의 시작부터 끝을 정렬. (3번째 파라메터에 아무 것도 넣지 않으면 기본적으로 오름차순 정렬)

   int result = 0; // 결과값을 저장하는 변수 (모든 그룹의 길이들 중 최대값)
   int current_s_len = 0; // 현재 그룹 s의 길이.
   for (int i=0; i<n; i++) { //i를 0부터 시작해서, n 미만일 동안 i를 증가시킨다.
      if (i == 0 || tickets[i] - tickets[i-1] <= 1) { //i가 0이거나(처음 들어온 원소이거나), 현재 원소와 이전 원소의 차가 1 이하면
         ++current_s_len; //current_s_len을 증가시킨다. (즉, 그룹의 cnt를 늘린다.)
      }
      else { //아니라면. 즉 i번째 티켓과 i-1번째 티켓이 다른 그룹임을 의미
         if (result < current_s_len) { // result보다 i-1번째 티켓이 속하는 그룹의 길이가 크면
            result = current_s_len; // 갱신한다. (result는 모든 그룹의 길이들 중 최대값, 처음에는 0으로 세팅) 다시 말해, result는 여태까지 지나온 값을 말함
         }
         current_s_len = 1; // i번째 티켓부터 새로운 그룹이니까 current_s_len을 1로 바꾼다.
      }
   }
   if (result < current_s_len) { // 마지막 그룹의 크기가 가장 큰 경우, 갱신이 필요하다.
      result = current_s_len; //
   }
   return result; // result를 리턴
}

int main()
{
   int n; // 길이 n 선언
   cin >> n; // 길이 입력

   vector<int> tickets(n); // 크기가 n인 벡터 tickets 선언
   for (int i=0; i<n; i++) { // n개의 티켓 크기 입력
      cin >> tickets[i]; 
   }

   int answer = maxTickets(tickets); // maxTickets 함수를 호출해서 answer 변수에 저장
   cout << "\n" << "정답: "<< answer; // 출력해서 확인

   return 0; //정상 종료됨을 의미하는 return 0
}

주석 제거용

#include <bits/stdc++.h> 
using namespace std; 

int maxTickets(vector<int> tickets) {
   int n = tickets.size(); 
   sort(tickets.begin(), tickets.end());

   int result = 0; 
   int current_s_len = 0; 
   for (int i=0; i<n; i++) { 
      if (i == 0 || tickets[i] - tickets[i-1] <= 1) { 
         ++current_s_len;
      }
      else { 
         if (result < current_s_len) { 
            result = current_s_len; 
         }
         current_s_len = 1; 
      }
   }
   if (result < current_s_len) {
      result = current_s_len; 
   }
   return result; 
}

int main()
{
   int n; 
   cin >> n; 

   vector<int> tickets(n); 
   for (int i=0; i<n; i++) { 
      cin >> tickets[i]; 
   }

   int answer = maxTickets(tickets); 
   cout << "\n" << "정답: "<< answer; 

   return 0; 
}