오늘의 공부

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/12951

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

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;
}

순열, 조합 구현

C++로 순열과 조합을 구현해보았다.

순열은 STL의 next_permutation과 prev_permutation을 쓰면 쉽게 구현할 수 있긴 하다. 하지만 하다보면 해당 원리를 이용해 조금 변형할 일이 생기기 마련...... 

순열과 조합은 보통 재귀를 이용해 구현한다. 

◎ 조합

조합은 순열과 다르게 순서가 없는 나열이다. 그러니까 원소들을 중복 없이 뽑는다.

조합을 먼저 쓴 이유는 조합을 먼저 구해야 순열을 구할 수 있다. 

우선 조합은 nCr로 n개 중에 r개를 뽑는 것이다.

만약 배열 {1,2,3,4,5}의 원소 중 3개씩 뽑는 조합을 만든다 했을 때 나올 수 있는 경우의 수는

(1,2,3) (1,2,4) (1,2,5) (1,3,4) (1,3,5) (1,4,5)

(2,3,4) (2,3,5) (2,4,5)

(3,4,5)
로 총 10개가 된다.

조합의 공식이 nPr / r! 임을 생각해보면 10개가 맞다. 

#include <iostream>
using namespace std;


void Combination(int arr[], int n, int r,  int index,int target, int comb_arr[])
{
	if (r == 0)
	{
		// r개를 뽑기로 했는데 r개를 다 뽑은 경우
		for (int i = 0; i < index; ++i)
		{
			cout << comb_arr[i];
		}
		cout << endl;
	}
	else if (target == n)
	{
		// target이 index를 초과=>종료 
		return;
	}
	else
	{
		//target 인덱스의 원소를 저장
		comb_arr[index] = arr[target];
		Combination(arr, n, r - 1, index + 1, target + 1, comb_arr); // 해당 원소를 선택
		Combination(arr, n, r, index, target + 1, comb_arr); // 해당 원소를 선택하지 않음
	}
}

int main()
{
	int arr[5] = { 1,2,3,4,5 };
	int n = 5;
	int r = 3;

	int* comb_arr = new int[5];
	
	Combination(arr, 5, 3, 0,0 , comb_arr);
}

조합을 하기 위해서 배열을 돌면서 뽑는 경우와 안 뽑는 경우를 조사한다. 

comb_arr는 빈 배열로 Combination 함수를 돌면서 뽑은 원소를 저장하는 배열이다.

Combination(arr, n, r - 1, index + 1, target + 1, comb_arr); // 해당 원소를 선택
Combination(arr, n, r, index, target + 1, comb_arr); // 해당 원소를 선택하지 않음

왜 두번 호출을 하냐면..

이 부분을 보면 위의 줄은 target에 위치한 원소를 원소를 뽑는 부분, 밑의 줄은 원소를 선택하지 않는 부분이다.

또한 target은 함수 호출 시 항상 1을 증가시켜서 넘겨야 순회하는 역할을 할 수 있다.

선택할 때는 r을 1 감소시키고 index를 1 증가시키며 선택하지 않을 때는 r을 그대로, index도 그대로 넣고 호출한다.

index를 증가시키는 이유는 현재 target이 가리키는 원소를 선택하고 다음 index를 선택하기 위함이며

증가시키지 않는 것은 현재 target이 가리키는 원소를 선택하지 않고 현재 index에 다른 원소를 선택하기 위함이다. 

이렇게 순회를 하는 도중, 다 뽑은 경우인 r=0과 r개를 다 뽑았지만 arr의 모든 원소를 다 검사했을 때인 target = n일 때이다. 후자의 경우 실패이므로 아무것도 하지 않고 return하게 된다. 

◎ 순열

순열은 순서가 있는 나열이다. 

우선 n개 중에 n개를 뽑는 순열을 보면 

void Swap(int arr[], int num1, int num2)
{
	int temp = arr[num1];
	arr[num1] = arr[num2];
	arr[num2] = temp;
}
void Permutation(int arr[], int index, int arr_size)
{
	// 탈출!
	if (arr_size - 1 == index)
	{
		for (int i = 0; i < arr_size; ++i)
		{
			cout << arr[i];
		}
		cout << endl;
		return;
	}

	for (int i = index; i < arr_size; ++i)
	{
		Swap(arr, index, i);
		Permutation(arr,index + 1, arr_size);
		Swap(arr, index, i);
	}
}


int main()
{
	int arr[5] = { 1,2,3,4,5 };
	Permutation(arr, 0, sizeof(arr) / sizeof(int));
}

(1,2,3,4,5) 의 배열에서 5개 중 5개를 뽑는 순열을 구하면 순열 공식에 의해 총 120개가 나오게 된다. 

arr배열 자체를 위에서 구한 조합을 이용해 정렬하는 것이다. 

먼저 swap을 이용해서 index번째의 자리 수가 1,2,3,4,일 때를 조사한다. index번째 자리를 선택한 후에 재귀를 통해 그 다음 자리를 선택하다가 arr의 마지막을 가리키면 끝이 난다.

재귀 후 다시 swap으로 바꿔준 값을 원상복구를 하면 다시 각 자리 수가 1일 때, 2일 때, 3일 때, 4일 때를 모두 조사할 수 있다. 

n개에서 n개를 뽑는 경우를 구했으니 이제 n개 중 r개를 뽑는 경우를 구하면 되는데 

이건 위에서 구한 조합을 이용하면 된다. 먼저 nCr을 이용해 n개 중에 r개를 뽑은 후에 r개의 수로 이루어진 숫자들을 permutation을 이용해서 정렬해주면 된다. 

void Swap(int arr[], int num1, int num2)
{
	int temp = arr[num1];
	arr[num1] = arr[num2];
	arr[num2] = temp;
}
void Permutation(int arr[], int index, int arr_size)
{
	// 탈출!
	if (arr_size - 1 == index)
	{
		for (int i = 0; i < arr_size; ++i)
		{
			cout << arr[i];
		}
		cout << endl;
		return;
	}

	for (int i = index; i < arr_size; ++i)
	{
		Swap(arr, index, i);
		Permutation(arr,index + 1, arr_size);
		Swap(arr, index, i);
	}
}
void Combination(int arr[], int n, int r, int index, int target, int comb_arr[])
{
	if (r == 0)
	{
		Permutation(comb_arr, 0, 3);
		cout << endl;
	}
	else if (target == n)
	{
		return;
	}
	else
	{
		comb_arr[index] = arr[target];
		Combination(arr, n, r - 1, index + 1, target + 1, comb_arr); 
		Combination(arr, n, r, index, target + 1, comb_arr); 
	}
}

int main()
{
	int arr[5] = { 1,2,3,4,5 };

	int* comb_arr = new int[5];

	Combination(arr, 5, 3, 0,0 , comb_arr);
}

혹시 이 포스팅을 보시는 분께..

참고 자료;

it-earth.tistory.com/53

onsil-thegreenhouse.github.io/programming/algorithm/2018/04/05/permutation_combination/

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

다른분들은 막 수식으로 한 두줄로 정리해서 푸시던데 나는 그냥 풀었다.. 

우선 brown+yellow를 해서 총 격자의 갯수를 구해서 (all_rect) 그 총 격자의 약수를 구해줬다. 

가로가 세로보다 더 길거나 같다고 했으니 약수는 절반 이상부터 가로의 값으로 비교해보면 된다.

총 12칸의 4x3 의 예시가 있을 때 o 표시가 쳐진 부분이 테두리이다.

즉 brown의 개수는 (w*2) + (h*2-4) 로 구할 수 있다.

가로의 길이는 첫 번째 줄과 마지막 줄. 그리고 세로는 첫 번째 열과 마지막 열에서 이미 가로의 길이에 더한 값인 네 꼭짓점 부분을 빼주는 것이다.

그럼 총 격자의 수에서 brown을 빼면 마찬가지로 yellow도 나온다. 

5분만에 풀었다. 요새 푼 문제 중에 제일 빨리 풀어서 기분이 (아주)좋다. 

vector<int> solution(int brown, int yellow) {
	vector<int> answer;

	int all_rect = brown + yellow;
	vector<int> factor; // 약수

	for (int i = 1; i <= all_rect; ++i)
	{
		if (all_rect % i == 0)
		{
			factor.push_back(i);
		}
	}
	int CD_cnt = factor.size();
	

	for (int w_idx = CD_cnt / 2; w_idx < CD_cnt; ++w_idx)
	{
		int h = all_rect / factor[w_idx];

		int temp = ((h * 2) - 4) + (factor[w_idx] *2);
		if (temp == brown)
		{
			answer.push_back(factor[w_idx]);
			answer.push_back(h);
			break;
		}
	}
	return answer;
}

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

※ 절대적인 해답은 당연히 아니고 제 마음대로 풀었으니 참고용으로 봐주세요

어떻게 풀까 고민을 하다 location값을 언제 찾아줘야 하는지가 애매해서 queue에 index값을 넣어주기로 했다.

1. q를 만들고 거기에 priorities(vector<int>) 우선순위들이 들어있는 벡터의 사이즈만큼 값을 채워준다. 

	for (int i = 0; i < p_size; ++i)
	{
		q.push(i);
	}

2. while문을 돌면서 queue의 값을 체크

2-1. q의 제일 앞에 있는 index값을 빼온다 

(여기의 index값이란 priorities 벡터의 index를 가리키는 값임)

2-2. for문을 돌면서 현재의 index값(temp)과 i의 값을 비교해 나보다 더 큰 우선순위가 존재한다면 해당 인덱스 값이 맨 뒤로 가게 큐에서 빼서 다시 넣어준다. 

2-3. 만약에 인덱스 값의 변화가 일어나지 않았다면(=내가 제일 우선순위가 크다면) for문 안에서 IsChange가 true가 되지 않았을 것이므로 false이면 큐에서 인덱스를 빼주고 해당 인덱스값이 가리키는 우선순위 벡터의 값을 0으로 만들어준다. 

왜 0인지? 우선순위는 1~9로 0이면 어떠한 우선순위보다 작게 되므로 for문 안에서 체크 시 제외된다.

2-4. 만약 IsChange가 false일 때 temp값(현재 검사하고 있는 index값)이 location과 같다면 while문을 나와서 결과값을 리턴한다. 

int solution(vector<int> priorities, int location) {
	int answer = 0;
	int p_size = priorities.size();
	queue<int> q;

	for (int i = 0; i < p_size; ++i)
	{
		q.push(i);
	}

	while (1)
	{
		int temp = q.front();

		int IsChange = false;
		for (int i = 0; i < p_size; ++i)
		{
			if (i == temp)
			{
				continue;
			}
			if (priorities[temp] < priorities[i])
			{
				q.pop();
				q.push(temp);
				IsChange = true;
				break;
			}
		}

		if (!IsChange)
		{
			
			q.pop();
			priorities[temp] = 0;
			answer += 1;
			if (temp == location)
			{
				break;
			}

		}
	}

	return answer;
}

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

int solution(string s) {
	int answer = 1001;// s의 길이가 최대 1000이므로
	int s_size = s.length();

	string temp = "";
	int same = 1;

	if (s_size == 1)
	{
		return 1;
	}

	for (int i = 1; i<= s_size / 2; ++i)
	{
		string save = "";
		for (int j = 0; j < s_size; j+=i) {

			temp = s.substr(j, i);

			if (temp.length() % i != 0)
			{
				if (same != 1) {
					save += to_string(same);
				}
				save += temp;
				break;
			}
			string value = s.substr(i + j, i);
			if (temp == value)
			{
				// 같으면
				same += 1;
			}
			else
			{
				// 다르면
				if (same != 1) {
					save += to_string(same);
				}
				save += temp;
				same = 1;
			}
		}

		int temp_length = save.length();

		if (temp_length < answer)
		{
			answer = temp_length;
		}
		
	}

	return answer;
}

이.. 이게 생각보다 어려웠다. 이거 레벨2 맞나?

왜.. 왜이렇게 어렵지... 너무 어렵게 생각했나? 계속 고치고 고치다가 맞았는데 앞에 풀었던건 왜 틀렸는지 모르겠음