프로그래머스 - 탐욕법 : 체육복, 조이스틱

체육복

 

음 이 문제를 모든 경우를 생각한다 해보면, 앞뒤로 학생이 빌려주는지 확인한다. 그러면 30명이니까 2^30이 된다 .....그러니까 아님 그래서 탐욕법을 사용하나 보다.

 

그냥 쉽게 생각해보면 빌려주려는 애가 앞뒤로 옷이 없으면 누굴 줘야 되는 지가 문제다, 자기 뒤에 친구가 옷이 있는지 보고 없으면 그 뒤에 친구가 여분이 있는지 확인하면 될듯?뒤에 친구가 여분이 있으면 앞에 친구 옷 빌려주면 되고, 뒤에 애들도 옷이 없으면 앞에 친구 빌려주면 되지 않을까??

 

아니 그냥 앞에사람 빌려주면 되는듯 앞에 사람이 있으면 뒤에사람

 

맞았다.

#include <string>
#include <vector>

using namespace std;

int student[31] = { 1 };

int solution(int n, vector<int> lost, vector<int> reserve) {
	int answer = 0;
	for (int i = 1; i <= n; i++)
		student[i] = 1;

	for (int i = 0; i <lost.size(); i++) {
		student[lost[i]]--;
	}
	for (int i = 0; i < reserve.size(); i++) {
		student[reserve[i]]++;
	}

	for (int i = 0; i < reserve.size(); i++) {
		int cur = reserve[i];
		if (student[cur] >= 2) {
			if (cur - 1 >= 1 && student[cur - 1] == 0) {
				student[cur - 1] += 1;
				student[cur] -= 1;
			}
			else if (cur + 1 <= n && student[cur + 1] == 0) {
				student[cur + 1] += 1;
				student[cur] -= 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		if (student[i] >= 1) {
			answer++;
		}
	}

	return answer;
}

int main() {

	vector<int>tmp1;
	vector<int>tmp2;

	tmp1.push_back(2);
	tmp1.push_back(4);

	tmp2.push_back(1);
	tmp2.push_back(3);
	tmp2.push_back(5);

	solution(5, tmp1, tmp2);
}

 

근데 이렇게 하니까 초기화가 안되더라

int student[31] = { 1 };

int solution(int n, vector<int> lost, vector<int> reserve) {
	int answer = 0;
	for (int i = 1; i <= n; i++)
		student[i] = 1;

 

전역 공간에서 student[31] ={1}; 하니까 안됨..; for로 해줌 그래서 왜안되냐 ㅠ

 

 

조이스틱

현재 커서의 위치에서 알파벳 변환의 횟수는 위 또는 아래중 적은 쪽을 고르면 된다.

그럼 커서 이동을 왼쪽으로 할지 오른쪽으로 할지가 문제다.

 

JAZ -> 이건 그냥 좌우 비교만 하면되.

JAZA -> 전체를 봐야 움직일 필요가 없다.

JAAZA -> 좌우를 보면 안되고 전체를 봐야되...

 

근데 커서는 왼쪽으로만 쭉 움직이거나 오른쪽으로만 움직이는거 아닌가.  양쪽으로 각각 계산하고 최솟값 고르면 될듯?

 

JAAZAAAAAAAAAAZ 이면 근데 한쪽이 아니라 오른쪽 갔다 왼쪽가는거야.....

 

그냥 매 순간 어느쪽인지 골라야되. 해당 커서 기준 양쪽에 가장 가까운 알파벳으로 가자.

 

아 구현했는데 잘 안된다. 예제2만 맞고 1은 틀리네.....

#include <string>
#include <vector>

using namespace std;

void swap(char* a, char * b) {
	char tmp = *a;
	*a = *b;
	*b = tmp;
}

int getDif(char ans, char base,string & str,int index) {
	int minv=100000;
	int dif;

	//A Z
	if (ans < base)
		swap(&ans, &base);

	//Z A
	minv = ans - base;
	dif = 'Z'-'A' - (minv);
	if (minv > dif) {
		minv = dif;
	}

	str[index] = ans;

	return minv;
}

int getNextIndex(string ans, string cur,int index,int* diff) {
	int dif;
	
	int dir[2] = { 1,-1 };
	int st;
	int minv = 100000;
	int nextIndex;

	for (int i = 0; i < 2; i++) {
		st = index;
		dif = 0;
		st += dir[i];
		dif++;
		if (st == ans.size()) {
			st = 0;
		}
		if (st == -1) {
			st = ans.size() - 1;
		}


		while (ans[st] == cur[st] && st != index) {
			st += dir[i];
			dif++;

			if (st == ans.size()) {
				st = 0;
			}
			if (st == -1) {
				st = ans.size() - 1;
			}
		}

		if (minv > dif) {
			minv = dif;
			*diff = dif;
			nextIndex = st;
		}
	}
	
	return nextIndex;
}


int solution(string name) {
	int answer = 0;

	string str="";
	for (int i = 0; i < name.size(); i++) {
		str.push_back('A');
	}

	int nextInd=0;
	int dif;
	while (str != name) {

		answer += getDif(name[nextInd], str[nextInd], str, nextInd);
		if(str!= name)
			nextInd = getNextIndex(name, str, nextInd,&dif);
		answer += dif;
	}

	return answer;
}

int main() {
	solution("JEROEN");
}

 

음 A 에서 Z를 누를때 처럼 아래로 가는 횟수 잘 못 계산했었다. 그거랑 맨 마지막에 getNextIndex에서 1 더해지는거 같아서 빼줬는데 틀렸다. 74점으로.....

 

#include <string>
#include <vector>

using namespace std;

void swap(char* a, char * b) {
	char tmp = *a;
	*a = *b;
	*b = tmp;
}

int getDif(char ans, char base,string & str,int index) {
	int minv=100000;
	int dif;

	//A Z
	if (ans < base)
		swap(&ans, &base);

	//Z A
	minv = ans - base;
	dif = 'Z'-'A' + 1 - (minv);
	if (minv > dif) {
		minv = dif;
	}

	str[index] = ans;

	return minv;
}

int getNextIndex(string ans, string cur,int index,int* diff) {
	int dif;
	
	int dir[2] = { 1,-1 };
	int st;
	int minv = 100000;
	int nextIndex;

	for (int i = 0; i < 2; i++) {
		st = index;
		dif = 0;
		st += dir[i];
		dif++;
		if (st == ans.size()) {
			st = 0;
		}
		if (st == -1) {
			st = ans.size() - 1;
		}


		while (ans[st] == cur[st] && st != index) {
			st += dir[i];
			dif++;

			if (st == ans.size()) {
				st = 0;
			}
			if (st == -1) {
				st = ans.size() - 1;
			}
		}

		if (minv > dif) {
			minv = dif;
			*diff = dif;
			nextIndex = st;
		}
	}
	
	return nextIndex;
}


int solution(string name) {
	int answer = 0;

	string str="";
	for (int i = 0; i < name.size(); i++) {
		str.push_back('A');
	}

	int nextInd=0;
	int dif;
	while (str != name) {

		answer += getDif(name[nextInd], str[nextInd], str, nextInd);
		if(str!= name)
			nextInd = getNextIndex(name, str, nextInd,&dif);
		answer += dif;
	}
	answer--;

	return answer;
}

int main() {
	solution("JEROEN");
}

 

 

원인을 알았다. while문 안에 if 안에 answer+=dif를 넣어 주니까 맞음 . answer--를 빼고 ㅋㅋ

	while (str != name) {

		answer += getDif(name[nextInd], str[nextInd], str, nextInd);
		if (str != name) {
			nextInd = getNextIndex(name, str, nextInd, &dif);
			answer += dif;
		}
	}

 

 

다른 분 풀이인데 map을 쓴건 이해 되는데 커서 이동횟수 계산을 어떻게 한거지???

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

using namespace std;

int solution(string name) {
    int answer = 0;
    map<char,int> m;
    m['A']=0;
    m['B']=1;
    m['C']=2;
    m['D']=3;
    m['E']=4;
    m['F']=5;
    m['G']=6;
    m['H']=7;
    m['I']=8;
    m['J']=9;
    m['K']=10;
    m['L']=11;
    m['M']=12;
    m['N']=13;
    m['O']=12;
    m['P']=11;
    m['Q']=10;
    m['R']=9;
    m['S']=8;
    m['T']=7;
    m['U']=6;
    m['V']=5;
    m['W']=4;
    m['X']=3;
    m['Y']=2;
    m['Z']=1;
    int a_count=0;
    for(int i=1;i<name.length();i++){
        if(name[i]!='A')
            break;
        a_count++;
    }
    for(int i=0;i<name.length();i++){
        answer+=m[name[i]];
    }
    answer+=name.length()-1-a_count;
    return answer;
}