C++ TIL day 12

1. 알고리즘 (코테 준비)

오전에 알고리즘 관련수업을 듣고, 코딩테스트 문제를 풀었다.

이때 substr 함수에 대해 잘 몰랐던 것 같아서 substr 에 대해 좀 더 공부해 보았다.

https://gbleem.tistory.com/19

substr

또한 코딩테스트를 풀면서, 예전에 풀었던 문제들이 생각나서 관련 유형을 다시 한번 풀어보고 정리해 보았다.

https://gbleem.tistory.com/18

1차원 BFS, DP

 

2. 코테 좀 더 풀기

프로그래머스 문제를 둘러보다가 level2에서 우연히 해당 문제를 들어오게 되었는데, 마침 오늘 정리한 substr을 써서 풀 수 있을 것 같아서 풀게 되었다.

https://school.programmers.co.kr/learn/courses/30/lessons/17677

프로그래머스

 

문제를 정리해보면

• 문자열 처리
  • 2개씩 묶어서 vector에 넣은 후
  • 각 문자열 마다 필요없는 내용은 없애고, (Check 함수를 통해서 문자열인지 확인)
  • 모두 대문자로 바꿔주었다. (makeArr 함수를 통해 바꿈)
• 갯수 세기
  • set을 통해 모든 중복되지 않은 가짓수를 저장했고
  • unordered_map 두개를 이용해서 중복된 수를 셀때 사용했다.
• 정리
  • 어려운 문제는 아니었지만, 문자열 처리를 해야하고 갯수를 세는 과정에 있어서 unordered_map이랑 set을 써서 코드가 길어지고, 복잡해졌다.
  • 가장 신경써서 구현한 부분이 중복된 숫자를 세는 부분인데,
    • 예를 들어, {1,1,2,3,4} 와 {1,1,1,2,3} 이런 집합이 있으면
    • total은 {1,1,1,2,3,4} 이고 중복집합은 {1,1,2,3} 이어야 한다.
    • 그래서 unordered_map 두개를 만들어서 각각의 갯수를 센 후
      • um1[1] = 2, um1[2] = 1, um1[3] = 1, um1[4] = 1
      • um2[1] = 3, um2[2] = 2, um2[3] = 1
    • set을 통해 순환하면서 개수를 측정했다 ( set = { 1,2,3,4} )
      • 만약 um1[1] 과 um2[1] 이 모두 0이 아니라면, 둘 중의 더 많은 갯수를  total에 넣어주고
      • 중복집합에는 둘 중에 작은 갯수를 넣어주면 된다.
• 정답 코드
  • 이 문제도 풀고나서 다른 사람들의 풀이를 봤는데, 다들 코드가 길었다. 
  • 다른 사람들이 사용한 함수 몇 가지를 찾을 수 있었는데, tolower과 isalpha, transform 함수였다.
  • 이 함수들도 다음에 정리해 보아야 할 것 같다.

#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <set>
#include <unordered_map>
using namespace std;

bool Check(string str)
{
    int cnt = 0;
    if(('a' <= str[0] && str[0] <= 'z') ||('A' <= str[0] && str[0] <= 'Z'))
    {
        cnt++;
    }
    if(('a' <= str[1] && str[1] <= 'z') ||('A' <= str[1] && str[1] <= 'Z'))
    {
        cnt++;
    }
    if(cnt == 2)
        return true;
    return false;
}

vector<string> makeArr(const string& str1)
{
    vector<string> vec;
    vector<string> res;
    
    for(int i = 0; i < str1.size() - 1; ++i)
    {
        vec.push_back(str1.substr(i, 2));
    }
    
    for(int i = 0; i < vec.size(); ++i)
    {
        if(Check(vec[i]))
        {
            string temp;
            if('a' <= vec[i][0] && vec[i][0] <= 'z')
            {
                vec[i][0] -= 32;
            }
            temp += vec[i][0];
            if('a' <= vec[i][1] && vec[i][1] <= 'z')
            {
                vec[i][1] -= 32;
            }
            temp += vec[i][1];
            
            res.push_back(temp);
        }
    }
    
    return res;
}

int solution(string str1, string str2) 
{
    float answer = 0;    
    
    vector<string> vec1;
    vector<string> vec2;
    unordered_map<string, int> um1;
    unordered_map<string, int> um2;
    set<string> s;
    
    vec1 = makeArr(str1);
    vec2 = makeArr(str2);
    
    int size1 = vec1.size();
    int size2 = vec2.size();
    
    float total = 0;
    float same = 0;
    
    //둘 다 공집합
    if(size1 == 0 && size2 == 0)
        answer = 1;
    else
    {
        for(const auto& v : vec1)
        {
            s.insert(v);
            um1[v]++;
        }

        for(const auto& v : vec2)
        {
            s.insert(v);
            um2[v]++;
        }

        for(auto it = s.begin(); it != s.end(); ++it)
        {
            int a = um1[*it];
            int b = um2[*it];
            
            if(a != 0 && b == 0)
                total += a;
            else if(a == 0 && b != 0)
                total += b;
            else if(a != 0 && b != 0)
            {
                if(a == b)
                {
                    total += a;
                    same += a;
                }
                else
                {
                    if(a > b)
                    {
                        total += a;
                        same += b;
                    }
                    else
                    {
                        total += b;
                        same += a;
                    }                    
                }
            }
        }
        answer = same/total;
    }    
                
    answer *= 65536;
    answer = floor(answer);
        
    return answer;
}