오늘의 공부

programmers.co.kr/learn/courses/30/lessons/42579

너무 복잡하게 풀어서 일단 풀기는 했지만 뭔가 찝찝하다.

IDE없이 풀려니까 어디가 문제인지도 안나오고 프로그래머스에서 풀 때 sort 오름차순, 내림차순 정렬 greater, less 추가하면 자꾸 오류나서 직접 비교 함수까지 추가했다.

map을 이용해서 장르 별로 총 몇 번 재생했는지 저장하고 (m)

그 m에 있는 정보를 정렬하기 위해서 또 re_m에다가 m의 키값과 value를 순서를 바꿔 저장했다.

이 때 map정렬을 따로 추가하는 게 귀찮아서 어차피 재생 횟수는 마이너스가 안되니까 -1을 곱해서 내림차순으로 저장했다.

그리고 나서 가장 많이 재생된 장르 순대로 하나씩 꺼내서 장르별로 횟수와 고유번호를 넣고 (v에) 정렬을 해줬다. 

iter를 2개까지만 끊어야 해서 idx변수를 추가로 써서 idx가 2면 break하게 하는 방식으로 answer에 넣어줬다. 

bool cmp(const pair<int, int> &a, const pair<int, int> &b)
{
    return a.first > b.first;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int song_cnt = genres.size();

    map<string, int> m;
    map<int, string> re_m;
    for(int i=0;i<song_cnt;++i)
    {
        m[genres[i]] += plays[i];
    }
    for(auto iter = m.begin(); iter != m.end(); ++iter)
    {
        re_m.insert(make_pair((iter->second)*-1, iter->first));
    }
    
    for(auto iter = re_m.begin(); iter != re_m.end();++iter)
    {
        vector<pair<int, int>> v;
        for(int i=0;i<song_cnt;++i)
        {
            if(genres[i] == iter->second)
            {
                v.push_back(make_pair(plays[i], i));
            }
        }
        sort(v.begin(), v.end(), cmp);
        
        int idx = 0;
        for(auto v_iter = v.begin(); v_iter != v.end() ; ++v_iter)
        {
            ++idx;
            answer.push_back(v_iter->second);
            
            if(idx >= 2)
            {
                break;
            }
        }
    }
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/43162

깊이 우선 탐색(DFS)의 방식으로 풀었다.

stack을 이용해서 갈 수 있는 점으로 진행하다가 갈 수가 없으면 stack을 pop해서 이전의 점으로 돌아간다.

bool (check)를 이용해 방문한 컴퓨터는 true로 바꿔 주었으며 

다시 이전으로 돌아가야 하는 조건을 설정하는 부분에서 (if (!Find) 부분) 스택이 비어있다면 하나의 네트워크 연결을 구한 것이므로 새로운 비어있는 컴퓨터를 찾아주어야 한다. 

int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    bool check[201]= {};
    stack<int> s;
    s.push(0);
    check[0] = true;
    
    while(!s.empty())
    {
        int y = s.top();
        bool Find = false;
        for(int i=0;i<n;++i)
        {
            if(computers[y][i] == 1)
            {
                if(check[i] == false)
                {
                    check[i] = true;
                    s.push(i);
                    Find = true;
                    break;
                }
            }
        }
        
        if(!Find)
        {
            // 다시 이전으로 돌아가야함
            s.pop();
            if(s.empty())
            {
                answer+=1;
                // 다음 찾아야됨
                for(int i=0;i<n;++i)
                {
                    if(check[i] == false)
                    {
                        check[i] = true;
                        s.push(i);
                        break;
                    }
                }
            }
        }
    }
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/1845

3분만에 푼 문제이다.

중복된 포켓몬들 사이에서 뽑을 수 있는 가장 최대한 여러 종류의 포켓몬을 뽑는 문제였다.

그래서 map에 포켓몬의 종류를 저장하고 (중복이 불가능하므로) 최대 뽑을 수 있는 nums/2 의 값보다 종류가 더 많으면 nums/2만큼, 작으면 종류의 개수(max_choice_collect)만큼 뽑도록 했다.

int solution(vector<int> nums)
{
    int answer = 0;
    map<int, int> choice;
    int nums_size = nums.size();
    for(int i=0;i<nums_size;++i)
    {
        choice[nums[i]]+=1;
    }
    
    int max_choice_collect = choice.size();
    
    if(nums_size/2 <= max_choice_collect)
    {
        answer = nums_size/2;
    }
    else
    {
        answer = max_choice_collect;
    }
    return answer;
}

걱정되는게 모든 문제에 map을 이용하는 경우가 많아서 다른 방법으로 풀 수 있는데도 map으로만 풀려고 해서 시야가 좁아지는 건 아닐까 걱정된다. 

programmers.co.kr/learn/courses/30/lessons/68644?language=cpp

중복을 확인하기 귀찮아서 key의 중복이 안되며 자동으로 정렬해주는 map을 이용했다.

map의 key값에 더한값들을 다 저장해주고 (중복 없이) map의 key값들을 answer에 넣어주었다. 

vector<int> solution(vector<int> numbers) {
    vector<int> answer;
    map<int, int> value;

    int num_size = numbers.size();
    for(int i=0;i< num_size-1;++i)
    {
        for(int j=i+1;j<num_size;++j)
        {
            value[numbers[i]+numbers[j]]+=1;
        }
    }
    
    auto iter =  value.begin();
    auto iterend = value.end();
    
    for(;iter != iterend; ++iter)
    {
        answer.push_back(iter->first);
    }

    return answer;
}

programmers.co.kr/learn/courses/30/lessons/17682

int solution(string dartResult) {
    int answer = 0;
    int result_size = dartResult.size();
    
    vector<int> cal_num;
    string temp_s = "";
    for(int i=0;i<result_size;++i)
    {
        if(dartResult[i] != 'S' && dartResult[i] != 'D' && dartResult[i] != 'T'
          && dartResult[i] != '*' && dartResult[i] != '#')
        {
            temp_s += dartResult[i];
        }
        else
        {
           switch(dartResult[i])
           {
               case 'S':{
                   int num = stoi(temp_s);
                   temp_s = "";
                   int cal = num;
                   cal_num.push_back(cal);
               }
                   break;
               case 'D':{
                   int num = stoi(temp_s);
                   temp_s = "";
                   int cal = num * num;
                   cal_num.push_back(cal);
               }
                   break;
               case 'T':{
                   int num = stoi(temp_s);
                   temp_s = "";
                   int cal = num * num * num;
                   cal_num.push_back(cal);
               }
                   break;
               case '*':{
                   int idx = cal_num.size();
                   if(idx > 0)
                   {
                       cal_num[idx-1] *=2;
                       cal_num[idx-2] *=2;
                   }
                   else
                   {
                       cal_num[0] *= 2;
                   }}
                   break;
               case '#':
                   {
                   int idx = cal_num.size();
                   if(idx > 0)
                   {
                       cal_num[idx-1] *= -1;
                   }
                   else
                   {
                       cal_num[0] *= -1;
                   }
                   }
                   break;
           }
        }
     
    }
  
    for(int i=0;i<cal_num.size();++i)
    {
        answer += cal_num[i];
    }
    return answer;
}

tech.kakao.com/2017/09/27/kakao-blind-recruitment-round-1/

초반에 감을 잘못 잡아서 헤매긴 했지만 정답률이 73%나 되는 쉬운 문제였다. 

programmers.co.kr/learn/courses/30/lessons/42888

누군가가 아이디를 바꾸면 마지막 출력에 바꾼 아이디들로 로그를 출력해야 한다.

그래서 먼저 키값의 중복이 안되는 map을 이용해서 Enter나 Change 상황에서 모든 user_id의 닉네임 값을 저장해 두었다. 

그 후에 Enter, Leave의 로그를 answer에 넣어줬다. 이때 map에서 user_id의 닉네임을 찾아 넣어주는 방식으로 풀었다.

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

using namespace std;

vector<string> solution(vector<string> record) {
    vector<string> answer;
    map<string, string> id;
    vector<vector<string>> id_record;
    int record_size = record.size();
    
    for(int i=0;i<record_size;++i)
    {   
        vector<string> temp_record;
        stringstream ss(record[i]);
        string k;
        while(ss >> k){
            temp_record.push_back(k);
        }
        
        if(temp_record[0] == "Enter" ||temp_record[0] == "Change" )
        {
            id[temp_record[1]] = temp_record[2];
        }
        
        id_record.push_back(temp_record);
    }
    
    
    for(int i=0;i<record_size;++i)
    {   
        string temp_answer = "";
        temp_answer += id[id_record[i][1]];
       if(id_record[i][0] == "Enter")
       {
           temp_answer += "님이 들어왔습니다.";
       }
        else if(id_record[i][0] == "Leave")
        {
           temp_answer += "님이 나갔습니다.";
        }
        else 
        {
            continue;
        }
        answer.push_back(temp_answer);
    }

    return answer;
}

트라이(Trie)

트리구조의 트라이

트라이(trie)는 탐색 트리의 일종으로 동적 집합이나 연관 배열을 저장하는데 사용하는 자료구조이다. 알고리즘 문제 등에서는 주로 문자열 저장 문제의 해결 방법으로 종종 등장한다.

문자열 검색을 빠르게 해주는 이진 탐색 트리의 구조로 한 레벨당 문자가 하나씩 저장되므로 문자열 검색 시 시간 복잡도는 O(NlogN)이다. 

위의 사진은 "A", "to", "tea", "ted", "ten", "i", "in", "inn"를 키로 둔 트라이.

◎ 알고리즘

트라이는 탐색과 삽입을 지원하는 노드로 구성된 트리이다. 

주어진 문자열을 이루고 있는 문자를 앞에서 부터 하나씩 노드를 생성해가며 만들어진다. 

탐색의 순서는 다음과 같다.

1. 탐색하려고 하는 문자열을 가져와 첫 번째 문자가 저장되어 있는지 체크한다. 

2. 현재 문자로 이루어진 노드가 존재하면 그 노드로 그 다음 문자열을 탐색하고 노드가 없으면 그 노드를 새로 할당받은 후, 해당 노드를 통해 다음 문자열을 탐색한다.

3. 문자열의 마지막이 될 때까지 위의 과정을 반복한다. 

참고 자료;

URL

ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)

programmers.co.kr/learn/courses/30/lessons/60060

해당 코드로는 정확성은 전부 맞지만 효율성 테스트에서 1,2,3을 통과하지 못했다.

무슨 문제인지 검색해보니 선형 탐색의 방식으로는 1,2,3을 통과할 수 없다고 한다.

Tries 구조를 공부해야 풀 수 있는 문제 였다. 

아래는 내가 풀어서 효율성 테스트를 통과하지 못한 코드

int FindMatch(string& words, string& queries, int dir)
{
	int words_size = words.size();
	int queries_size = queries.size();

	if (words_size != queries_size)
		return 0;
        
	switch (dir)
	{
	case 0:
		// 뒤에서부터
		for (int i = words_size - 1; i >= 0; --i)
		{
			if (queries[i] != '?') {
				if (words[i] == queries[i])
					continue;
				else
					return 0;
			}
			else
				return 1;
		}
		break;
	case 1:
		// 앞에서부터
		for (int i = 0; i < words_size; ++i)
		{
			if (queries[i] != '?') {
				if (words[i] == queries[i])
					continue;
				else
					return 0;
			}
			else
				return 1;
		}
		break;
	}
}

vector<int> solution(vector<string> words, vector<string> queries) {
	vector<int> answer;
	int words_size = words.size();
	int queries_size = queries.size();
	int idx = 0;
	while (idx < queries_size)
	{
		int cnt = 0;
		for (int i = 0; i < words_size; ++i)
		{
			if (queries[idx][0] == '?')
				cnt += FindMatch(words[i], queries[idx], 0);
			else
				cnt += FindMatch(words[i], queries[idx], 1);
		}
		idx += 1;
		answer.push_back(cnt);
	}
	return answer;
}

이게 내가 해결한 방식이었다. 

tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

다음의 공식 해설을 보면 출제 의도에 문자열을 다룰 수 있는지 파악과 함께 트라이 자료구조 또는 이분 탐색 등 보다 효율적인 방법을 이용해 코드를 작성할 수 있는지 파악하고자 했다고 써있다.

공식적인 해설은 다음과 같다. 정확성 풀이같은 경우는 하나하나 비교해가면서 개수를 세면 되지만 효율성 풀이 같은 경우는 좀 길다.