굳건하게

문제 : 카카오 2020 BLINE RECRUITMENT '문자열압축'

구현

 예시 5번을 잘 이해하면 쉽게 구현할 수 있는 문제입니다. 문자열의 모든 지점에서 압축크기만큼 압축을 진행할 수 있는게 아니라, 시작지점부터 압축크기만큼 잘라야 합니다.

 1 ~ (문자열의길이 / 2) 까지 각각 다 압축을 진행해보고 가장 작은 길이 값을 return 해주면 됩니다.

 p1 : 문자열의 현재 시작 지점을 가리키고 있는 포인터

 p1 에서부터 i (현재압축크기) 만큼 같은 쌍이 몇개 나오는지 count를 합니다. 이때, count 값이 1이면 자기 자신이랑만 같다는 뜻으로 압축을 할 필요가 없습니다. 따라서, p1 을 p1 + i 로 보내준 후 다시 같은 과정을 반복하면 되고, count 값이 1보다 크다면 압축을 진행할 수 있으므로 압축을 진행하고 p1 을 p1 + count * i 로 보내주면 됩니다. 

#include <string>
#include <vector>
#include<algorithm>

using namespace std;

int get_length(int n) {
	int ret = 0;
    while(n){
    	ret++;
        n /= 10;
    }
    return ret;
}

int solution(string s) {
	int answer = s.length();
	int start = 1, end = s.length() / 2;
	for (int i = start; i <= end; i++) {
		int  p1 = 0, tempAns = s.length();
		while (p1 <= s.length() - 2 * i) {
			// p1 에서부터 i개 씩 같은지 다른지 체크해보자.
			int cnt = 0, jump = 0;
			while (1) {
				bool check1 = false;
				for (int j = 0; j < i; j++) {
					if (s[p1 + j] != s[p1 + jump + j]){
						check1 = true;
						break;
					}
				}
				if (!check1) // p1에서부터 i개씩 다 같음 -> p1 + i 로 jump를 이동.
					jump += i;
				else
					break;
				cnt++;
			}
			if (cnt == 1){ // p1에서부터 i개씩 다 같은게 자기 자신 밖에 없음.
				p1 += i; // 그러면 p1 시작 위치를 그냥 이동( 압축된게없음 )
			}
			else{ // p1에서부터 i개씩 다 같은게 있음!
				p1 += cnt * i; // 일단 p1을 저 앞으로 이동
				tempAns -= i * cnt; // 답 갱신
				tempAns += get_length(cnt) + i;
			}
		}
		answer = min(answer, tempAns);
	}
	return answer;
}

문제 : 2018 KAKAO BLIND RECRUITMENT [3차] n진수 게임

문자열 수학 구현 

 Input의 크기가 작아 단순 구현으로 해결할 수 있는 문제입니다. 

 숫자 0부터 1씩 키워가며 N진법으로 표현한 후, N진법으로 표현된 수를 다시 한 자리씩 순회하며 m명의 친구들에게 하나씩 배당해준다. 이때, 튜브의 차례라면 answer에 concat 해준다.

#include <string>
#include <vector>

using namespace std; 

string solution(int n, int t, int m, int p) {
	char list[16] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B','C', 'D', 'E' , 'F' };
	string answer = "";
	p--;
	int curN = 0, curP = 0;
	while (answer.length() < t) {
		string temp = "";
		int tempN = curN;
		do { // curN을 N진법으로 표현하자.
			temp += list[tempN % n];
			tempN /= n;
		} while (tempN);

		for (int i = temp.length() - 1; i >= 0; i--) {
			if (curP % m == p && answer.length() < t)
				answer += temp[i];
			curP = (curP + 1) % m;
		}
		curN++;
	}
	return answer;
}

[ 알고리즘풀이 ]

time[i] : i번 째 기능이 완성되는데 걸리는 시간.

--> time[i] = ((100 - progresses[i]) / speeds[i] ) + 1; // (100 - progresses[i]) % speeds[i] 가 0이 아니라면.
     time[i] = (100 - progresses[i]) / speeds[i];  // (100 - progresses[i]) % speeds[i] 가 0이라면.

 각각 기능별로 필요한 시간을 구하고, 앞에서부터 순회하며 한 번에 처리할 수 있는 최대 작업량을 count 한다. 현재 기준이 되는 time[i] 보다 작거나 같은 값들은 한 번에 처리할 수 있으므로 while 문을 통해 count 해주고, answer에 push 해준다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> progresses, vector<int> speeds) {
    int time[100]={};
    for(int i = 0; i < progresses.size(); i++){
        if((100 - progresses[i]) % speeds[i])
            time[i] = ((100 - progresses[i]) / speeds[i] ) + 1;
        else
            time[i] = (100 - progresses[i]) / speeds[i];
    }
    vector<int> answer;
    int i = 0, count = 0, s = time[0];
    while(i < progresses.size()){
        while(i < progresses.size() && s >= time[i]){
            count++;
            i++;
        }
        answer.push_back(count);
        if(i < progresses.size()){
            count = 0;
            s = time[i];
        }
    }   
    return answer;
}

[ 알고리즘풀이 ]

 DP 문제로 DP[N] : 2 x N 타일링하는 경우의 수라고 한다면, 2 x N 타일링은 2 x (N - 1) 타일링 방법에 세로 한 줄을 추가하는 경우의 수와 2 X (N - 2) 타일링 방법에 가로 두 줄을 추가하는 경우의 수의 합으로 다음과 같은 점화식이 성립합니다.

■ DP[N] = DP[N - 1] + DP[N - 2]

 이때, 여러개의 테스트 케이스에 대해서 2 x N 타일링하는 경우의 수를 출력하는 게 아니라 단 한 번만 출력하면 되므로 굳이 배열을 선언해 메모리를 낭비하지 않고 2 x N 타일링하는 경우의 수를 앞에서부터 차곡차곡 쌓아가면 됩니다.

#include <string>
#include <vector>
#define M 1000000007
using namespace std;

int solution(int n) {
    int answer = 0, left = 0, right =1, temp;
    for(int i = 2; i <= n; i++){
        temp = (left + right) % M;
        left = right;
        right = temp;
    }
    answer = (left + right) % M;
    return answer;
}