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

 

코딩테스트 연습 - 베스트앨범

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가

programmers.co.kr

 

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

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

 

코딩테스트 연습 - 네트워크

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있��

programmers.co.kr

 

깊이 우선 탐색(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

 

코딩테스트 연습 - 폰켓몬

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. �

programmers.co.kr

 

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

 

코딩테스트 연습 - 두 개 뽑아서 더하기

 

programmers.co.kr

 

중복을 확인하기 귀찮아서 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

 

코딩테스트 연습 - [1차] 다트 게임

 

programmers.co.kr

 

 

 

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/

 

카카오 신입 공채 1차 코딩 테스트 문제 해설

‘블라인드’ 전형으로 실시되어 시작부터 엄청난 화제를 몰고 온 카카오 개발 신입 공채. 그 첫 번째 관문인 1차 코딩 테스트가 지난 9월 16일(토) 오후 2시부터 7시까지 장장 5시간 동안 온라인��

tech.kakao.com

 

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

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

 

코딩테스트 연습 - 오픈채팅방

오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오

programmers.co.kr

 

 

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

그래서 먼저 키값의 중복이 안되는 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;
}

 

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

 

코딩테스트 연습 - 가사 검색

 

programmers.co.kr

 

 

 

해당 코드로는 정확성은 전부 맞지만 효율성 테스트에서 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/

 

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

올해에도 2020이라는 멋진 숫자와 함께, 카카오의 신입 개발자 채용을 시작했습니다! 그 여정 중 첫 단계로 1차 코딩 테스트가 지난 9월 7일 토요일 오후 2시부터 오후 7시까지 5시간 동안 진행됐는

tech.kakao.com

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

 

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

 

 

 

 

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

 

코딩테스트 연습 - JadenCase 문자열 만들기

JadenCase란 모든 단어의 첫 문자가 대문자이고, 그 외의 알파벳은 소문자인 문자열입니다. 문자열 s가 주어졌을 때, s를 JadenCase로 바꾼 문자열을 리턴하는 함수, solution을 완성해주세요. 제한 조건

programmers.co.kr

 

처음에는 그냥 공백 구분해서 제일 앞글자만 대문자로 바꿔주면 되는 줄 알았더니 다른 조건들이 있었다.

1. 문자열 중간에 있는 대문자를 소문자로 바꾸기

2. 공백이 길게 있는 경우 그 공백도 answer에 그대로 추가해야 함

 

그러니까 hello    woRld 같은 경우에 Hello WoRld로 출력하면 안되고 Hello    World로 출력해야 한다.

ssstream으로 풀고 테스트 실행했는데 눈이 침침했는지 분명 똑같은 결과인데 뭐가 다르다는 거야; 하면서 한참 고민했다.

웃기네 

 

 

string solution(string s) {
	string answer = "";

	int index = 0;
	bool prev_blank = true;
	while (index < s.size())
	{
		if (prev_blank && s[index] != ' ')
		{
			s[index] = toupper(s[index]);
			prev_blank = false; 
		}
		else if (s[index] == ' ')
		{
			prev_blank = true;
		}
		else if(isupper(s[index]))
		{
			s[index] = tolower(s[index]);
		}

		answer += s[index];
		index += 1;
	}

	return answer;
}

+ Recent posts