2022 KAKAO BLIND RECRUITMENT 문제 리뷰

1. 신고 결과 받기 

 

문제 링크 : 코딩테스트 연습 - 신고 결과 받기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 신고 결과 받기

 

map 을 사용하여 해결하였다.

주의해야 했던건 한 유저가 같은 유저를 여러번 신고하는 경우를 처리해야 한다.

아래와 같이 map 을 이용하여 해결할 수 있다.

 

• map<string, int> report_cnt : 신고당한 유저의 횟수
• map<string, int> report_id : 해당 id의 유저가 신고한 유저들 중에 신고당한 횟수
• map<string, bool> report_check : 한 유저가 같은 유저를 여러번 신고하는 경우에 대한 처리 용도

 

※ 문제 접근 방법

① report 의 각 원소마다 report_check을 이용하여 한 유저가 같은 유저를 신고했는지 안했는지에 대한 확인을 한다.

신고하지 않을 경우 report_check[report[i]] 의 값을 true 로 변경해주고, report_cnt[신고당한 유저] 의 값을 1 증가 시킨다.

 

② report_check를 clear한 후에 다시 report 의 각 원소를 검사한다.

그리고 report_check을 이용하여 한 유저가 같은 유저를 신고했는지 안했는지에 대한 확인을 ① 방법과 동일하게 한다.

신고하지 않을 경우 report_check[report[i]] 의 값을 true 로 변경해주고, 신고당한 유저의 횟수 report_cnt[신고당한 유저] 값이 k 이상일 경우 report_id[신고한 유저] 의 값을 1 증가시킨다.

 

③ id_list 의 각 원소마다 report_id[id_list[i]] 의 값을 answer 벡터에 push 한다.

 

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

using namespace std;

vector<int> solution(vector<string> id_list, vector<string> report, int k) {
	vector<int> answer;
	map<string, int> report_cnt, report_id;
	map<string, bool> report_check;

	for (int i = 0; i < report.size(); i++) {
		string s = "";
		int t = 0;

		for (int j = 0; j < report[i].size(); j++) {
			if (report[i][j] == ' ') {
				t = j + 1;
				break;
			}
		}

		// s는 신고당한 유저의 이름
		for (int j = t; j < report[i].size(); j++)
			s += report[i][j];

		if (!report_check[report[i]]) {
			report_check[report[i]] = true;
			report_cnt[s]++;
		}
	}

	report_check.clear();
	for (int i = 0; i < report.size(); i++) {
		string s1 = "", s2 = "";
		int t = 0;

		// s1는 신고한 유저의 이름
		for (int j = 0; j < report[i].size(); j++) {
			if (report[i][j] == ' ') {
				t = j + 1;
				break;
			}
			s1 += report[i][j];
		}

		// s2는 신고당한 유저의 이름
		for (int j = t; j < report[i].size(); j++)
			s2 += report[i][j];

		if (!report_check[report[i]]) {
			report_check[report[i]] = true;
			if (report_cnt[s2] >= k)
				report_id[s1]++;
		}
	}

	for (int i = 0; i < id_list.size(); i++) {
		string S = id_list[i];
		answer.push_back(report_id[S]);
	}

	return answer;
}

 

---

2. k진수에서 소수 개수 구하기

 

문제 링크 : 코딩테스트 연습 - k진수에서 소수 개수 구하기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - k진수에서 소수 개수 구하기

 

양의 정수를 k진수로 변환 및 소수 판별 문제이다.

예를 들어서 12345 를 7진수로 변환하는 과정을 생각해보면 다음과 같다.

 

소수 판별은 아래와 같이 O(\(\sqrt{n}\)) 으로 판별 가능하도록 함수를 구현했다.

bool is_prime(ll n){
    if(n == 1) return false;
    ll tmp = sqrt(n);
    for(ll x = 2; x <= tmp; x++){
        if(n % x == 0) return false;
    }
    return true;
}

 

※ 문제 접근 방법

① 파라메터로 받은 n, k 값에 대하여 n 값을 k 진수로 변환하여 벡터 v에 저장한다.

k 진수로 변환하는 코드는 다음과 같이 작성하였다.

void get_10_to_k(vector<int> &v, int n, int k){
    while(n){
        v.push_back(n % k);
        n /= k;
    }
    reverse(v.begin(), v.end());
}

 

② 문제에 주어진 4 가지 조건을 고려해야 한다.

 

• 0P0 인 경우 : 양 옆에 0이 있는지 체크하고 P 값이 소수인지를 계속해서 체크해준다.
• P0 인 경우 : 맨 왼쪽에 0이 있는 경우 0P0 이 되므로 무시한다. 그렇지 않은 경우, P0 을 체크하고 P 값이 소수인지를 체크해주면 된다. 
• 0P 인 경우 : 맨 오른쪽에 0이 있는 경우 0P0 이 되므로 무시한다. 그렇지 않은 경우, 0P 를 체크하고 P 값이 소수인지를 체크해주면 된다.
• P 인 경우 : 모든 숫자가 0이 아닌 경우여야 하고 0이 하나라도 있을 경우 무시한다. 그렇지 않은 경우, P 를 체크하고 P 값이 소수인지를 체크해주면 된다.

 

#include <string>
#include <vector>
#include <algorithm>
#include <math.h>
#define ll long long

using namespace std;

void get_10_to_k(vector<int>& v, int n, int k) {
	while (n) {
		v.push_back(n % k);
		n /= k;
	}
	reverse(v.begin(), v.end());
}

bool is_prime(ll n) {
	if (n == 1) return false;
	ll tmp = sqrt(n);
	for (ll x = 2; x <= tmp; x++) {
		if (n % x == 0) return false;
	}
	return true;
}

// 0P0
int prime1(vector<int> v) {
	int x, y, ret = 0;
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == 0) {
			string S = "";
			x = i, y = -1;
			for (int j = i + 1; j < v.size(); j++) {
				if (v[j] == 0) {
					y = j;
					break;
				}
			}
			for (int j = x + 1; j < y; j++) {
				S += to_string(v[j]);
			}
			if (S.size() != 0 && is_prime(stol(S))) ret++;
		}
	}
	return ret;
}

// P0
int prime2(vector<int> v) {
	if (v[0] == 0) return 0;
	int x = -1;
	string S = "";
	for (int i = 1; i < v.size(); i++) {
		if (v[i] == 0) {
			x = i;
			break;
		}
	}
	if (x == -1) return 0;
	for (int i = 0; i < x; i++) {
		S += to_string(v[i]);
	}
	if (is_prime(stol(S))) return 1;
	return 0;
}

// 0P
int prime3(vector<int> v) {
	if (v[v.size() - 1] == 0) return 0;
	int x = -1;
	string S = "";
	for (int i = v.size() - 2; i >= 0; i--) {
		if (v[i] == 0) {
			x = i;
			break;
		}
	}
	if (x == -1) return 0;
	for (int i = x + 1; i < v.size(); i++) {
		S += to_string(v[i]);
	}
	if (is_prime(stol(S))) return 1;
	return 0;
}

// P
int prime4(vector<int> v) {
	for (int i = 0; i < v.size(); i++) {
		if (v[i] == 0) return 0;
	}
	string S = "";
	for (int i = 0; i < v.size(); i++) {
		S += to_string(v[i]);
	}
	if (is_prime(stol(S))) return 1;
	return 0;
}

int solution(int n, int k) {
	int answer = 0;

	vector<int> v;
	get_10_to_k(v, n, k);
	answer = prime1(v) + prime2(v) + prime3(v) + prime4(v);

	return answer;
}

 

---

3. 주차 요금 계산

 

문제 링크 : 코딩테스트 연습 - 주차 요금 계산 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 주차 요금 계산

 

구현 문제이다.

차가 들어오는 경우("IN") 무조건 나가야 한다("OUT").

예를 들어 차량 번호 1234가 2번 들어오고 3번 나가거나 4번 들어오고 2번 나가는 경우는 존재하지 않는다.

또 다른 예로 차량 번호 4321가 5번 들어오고 5번 나가거나 5번 들어오고 4번 나가는 경우는 존재한다.

 

5번 들어오고 4번 나가는 경우는 왜 존재하나요?

 

문제를 잘 읽어보면 ...

 

• 0000번 차량은 18:59에 입차된 이후, 출차된 내역이 없습니다. 따라서, 23:59에 출차된 것으로 간주합니다.

 

와 같은 문구를 볼 수 있다.

즉, 간접적으로 23:59 에 나갔다는 것을 캐치할 수 있는게 이 문제의 핵심이다.

 

※ 문제 접근 방법

① 차가 들어오는 시간과 나가는 시간을 담을 수 있는 벡터를 생성한다.

 

• vector<int> car[10000] : 차량 번호는 '0'~'9' 로 구성된 길이 4인 문자열이므로 최소 0 부터 최대 9999 까지 차량이 존재하기 때문이다.

 

② record 벡터에 담긴 시각, 차량번호를 파싱하여 car[차량번호] 에 넣어주도록 한다. 

이때 IN, OUT 은 고려하지 않고 넣어줘도 무방하다. 

 

③ 차량번호 0 부터 9999 까지 car[차량번호] 의 size가 0이 아닌 경우를 확인해준다.

0이 아닐 경우 size 가 만약 짝수일 경우와 홀수일 경우로 나뉠 것이다.

 

• size가 짝수일 경우 : IN, OUT이 동일하다는 것을 짐작할 수 있다.
• size가 홀수일 경우 : OUT 내역이 없는 것을 짐작할 수 있다. 이 경우 23:59 을 넣어줘서 size 값이 짝수가 되도록 변경해줘야 한다.

 

④ car[차량번호] 의 size 값이 이제 짝수이므로, \(time_{out}\) - \(time_{in}\) 의 값을 누적한 값을 time 이라고 하고 fees 벡터에 담긴 요금표 정보를 고려하여 주차 요금을 계산하여 answer 벡터에 값을 넣어주기만 하면 된다.

 

#include <string>
#include <vector>
#include <math.h>

using namespace std;

int get_Time(string S) {
	string hour, min;
	hour = S.substr(0, 2);
	min = S.substr(3, 5);
	return stoi(hour) * 60 + stoi(min);
}

int get_Number(string S) {
	string number;
	number = S.substr(6, 10);
	return stoi(number);
}

vector<int> car[10000];

vector<int> solution(vector<int> fees, vector<string> records) {
	vector<int> answer;
	for (int i = 0; i < records.size(); i++) {
		int time, number;
		time = get_Time(records[i]);
		number = get_Number(records[i]);
		car[number].push_back(time);
	}

	for (int number = 0; number < 10000; number++) {
		if (car[number].size() == 0) continue;
		if (car[number].size() % 2)
			car[number].push_back(1439);
		int time = 0;
		for (int i = 0; i < car[number].size(); i += 2) {
			time += (car[number][i + 1] - car[number][i]);
		}
		if (time > fees[0]) {
			int cul_time = time - fees[0];
			if (cul_time % fees[2]) cul_time = cul_time / fees[2] + 1;
			else cul_time = cul_time / fees[2];
			answer.push_back(fees[1] + cul_time * fees[3]);
		}
		else {
			answer.push_back(fees[1]);
		}
	}

	return answer;
}

 

---

4. 양궁대회

 

문제 링크 : 코딩테스트 연습 - 양궁대회 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 양궁대회

 

풀이법이 다양하겠지만 재귀를 적절히 사용하여 해결하였다.

이 문제에서 약간 골치 아팠던 조건이 하나 있었다.

 

• 라이언이 가장 큰 점수 차이로 우승할 수 있는 방법이 여러 가지 일 경우, 가장 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
  • 가장 낮은 점수를 맞힌 개수가 같을 경우 계속해서 그다음으로 낮은 점수를 더 많이 맞힌 경우를 return 해주세요.
  • 예를 들어, [2,3,1,0,0,0,0,1,3,0,0]과 [2,1,0,2,0,0,0,2,3,0,0]를 비교하면 [2,1,0,2,0,0,0,2,3,0,0]를 return 해야 합니다.
  • 다른 예로, [0,0,2,3,4,1,0,0,0,0,0]과 [9,0,0,0,0,0,0,0,1,0,0]를 비교하면[9,0,0,0,0,0,0,0,1,0,0]를 return 해야 합니다.

 

이 조건만 잘 고려해준다면 특별하게 큰 문제는 없었던 것 같다.

 

우선 전역 변수로 int lion[11], peach[11], gap 을 선언하였다.

 

• int lion[11] : lion의 점수를 보관하기 위한 용도이다.
• int peach[11] : peach의 점수를 보관하기 위한 용도이다.
• int gap : 라이언과 어피치의 점수 차이를 보관하기 위한 변수이다. (초기값은 0)

 

※ 문제 접근 방법 

① 재귀적으로 lion의 점수를 배정하려고 한다.

예를 들어 문제에 주어진 인풋으로 n = 5, info = [2, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] 으로 설명하자면 다음과 같다.

 

 

초기의 어피치와 라이언의 점수는 위와 같이 세팅한다.

 

 

재귀적으로 (어피치의 점수 + 1) 을 배정하거나 점수를 배정하지 않도록 한다.

위 경우로 어피치의 점수에 1을 더한 3을 배정하여 나머지 2점만 할당하면 되는 상태이며, 다른 경우로 점수를 배정하지 않아서 여전히 5점을 할당해야 하는 상태이다.

 

 

계속 해서 재귀적으로 (어피치의 점수 + 1) 을 배정하거나 배정하지 않도록 한다.

위 경우로 어피치의 점수에 1을 더한 2를 배정하여 모든 점수가 할당된 상태이며, 다른 경우로 점수를 배정하지 않아서 여전히 2점을 할당해야 하는 상태이다.

 

※ 주의할 점 : (어피치의 점수 + 1) 을 배정할 수 없는 경우를 고려해줘야 한다. (할당해야 할 점수보다 큰 경우)

      이 경우에 배정할 수 있는 점수만 할당해주도록 해줘야 한다.

 

② 모든 점수를 할당한 경우 어피치의 점수와 라이언의 점수를 비교하여 라이언의 점수가 더 큰 경우 gap 값을 업데이트 해준다.

이때, 두 가지 경우를 고려하여 answer 벡터를 채워야 한다.

 

• 라이언 점수 - 어피치 점수 > gap : gap 값을 업데이트 하고 answer 벡터를 초기화 하여 새로운 라이언의 점수를 넣어준다.
• 라이언 점수 - 어피치 점수 == gap : answer 벡터에 존재하는 기존에 있던 점수와 새로운 라이언의 점수를 비교하여 가장 낮은 점수를 더 많이 맞힌 경우 answer 벡터를 초기화 하여 새로운 라이언의 점수를 넣어주고, 그렇지 않은 경우 무시한다.

 

③ 위 과정을 전부 진행 후, 여전히 gap 값이 0인 경우 answer 벡터에 -1 을 넣어주면 된다.

 

#include <string>
#include <vector>

using namespace std;

int lion[11], peach[11];
int gap;

void shot_Lion(int shot, int idx, vector<int>& answer) {
	if (shot == 0) {
		int lion_point, peach_point;
		lion_point = peach_point = 0;
		for (int i = 0; i < 11; i++) {
			if (peach[i] && peach[i] == lion[i])
				peach_point += (10 - i);
			if (peach[i] > lion[i]) peach_point += (10 - i);
			else if (peach[i] < lion[i]) lion_point += (10 - i);
		}
		if (lion_point > peach_point) {
			if (lion_point - peach_point > gap) {
				gap = lion_point - peach_point;
				answer.clear();
				for (int i = 0; i < 11; i++) answer.push_back(lion[i]);
			}
			else if (lion_point - peach_point == gap) {
				for (int i = 10; i >= 0; i--) {
					if (lion[i] != answer[i]) {
						if (lion[i] > answer[i]) {
							answer.clear();
						}
						break;
					}
				}
				if (answer.size() == 0) {
					for (int i = 0; i < 11; i++) answer.push_back(lion[i]);
				}
			}
		}
		return;
	}
	if (idx == 11) return;

	if (shot - (peach[idx] + 1) < 0) {
		lion[idx] = shot;
		shot_Lion(0, idx + 1, answer);
	}
	else {
		lion[idx] = peach[idx] + 1;
		shot_Lion(shot - lion[idx], idx + 1, answer);
	}
	lion[idx] = 0;
	shot_Lion(shot, idx + 1, answer);
}

vector<int> solution(int n, vector<int> info) {
	vector<int> answer;
	for (int i = 0; i < 11; i++) peach[i] = info[i];
	shot_Lion(n, 0, answer);
	if (gap == 0) answer.push_back(-1);

	return answer;
}

 

---

5. 양과 늑대

 

문제 링크 : 코딩테스트 연습 - 양과 늑대 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 양과 늑대

 

트리 + 재귀 + 완전 탐색 문제이다.

info 의 사이즈가 작다는 점에서 완전 탐색 기법을 이용하였으며 시간 내에 모두 통과하는 것을 확인할 수 있었다.

먼저 이 문제를 해결한 흐름에 대해 설명해보려고 한다.

 

※ 문제에 대한 흐름

 

 

① 루트 노드부터 시작하므로, 루트 노드부터 이동할 수 있는 모든 경우를 다 따져본다. (루트 노드를 미리 방문 처리)

루트 노드부터 시작하여 이동 가능한 곳은 2번, 5번 이다.

 

• 7번, 8번 : 루트 노드에서 1번으로 이동할 경우 양 1마리, 늑대 1마리 이므로 모든 양이 잡아먹힌다. 따라서 이동할 수 없다.
• 10번 : 루트 노드에서 2번으로 이동할 경우 양 2마리, 늑대 0마리 이고, 2번에서 6번으로 이동할 경우 양 2마리, 늑대 1마리 이다. 그러나 6번에서 9번으로 이동할 경우 양 2마리, 늑대 2마리 이므로 모든 양이 잡아먹힌다. 따라서 이동할 수 없다.

 

 

② 현재 루트 노드에서 5번으로 이동한 상황이라고 하자. (이때 2, 5번 노드가 방문 처리됨)

그리고 다시 루트 노드부터 시작하여 이동할 수 있는 모든 경우를 따져본다.

루트 노드부터 시작하여 이동 가능한 곳은 7번, 8번, 10번 이다.

7번, 8번, 10번 으로 이동할 경우 양 4마리, 늑대 2마리가 되므로 모두 충족하게 된다.

이번엔 10번으로 이동한 경우를 고려해보도록 한다.

 

 

③ 현재 10번으로 이동한 상황이라고 하자. (이때 6, 9, 10번 노드가 방문 처리됨)

이번엔 루트 노드부터 시작하여 이동할 수 있는 경우가 존재하지 않는다.

 

• 7번, 8번 : 루트 노드에서 1번으로 이동할 경우 양 4마리 늑대 3마리 이고, 1번에서 3번 또는 4번으로 이동할 경우 양 4마리 늑대 4마리 이므로 모든 양이 잡아먹힌다. 따라서 이동할 수 없다.

 

 

④ 우선, ③에서 10번 까지 이동한 경로에 대한 방문 처리를 해제해야 한다.

방문 처리를 해제하는 방법은 10번 (해제) => 9번 (해제) => 6번 (해제) => 2번 (해제 x) 와 같이 진행된다.

즉, 양이 존재하는 10번에서 역으로 방문 처리를 해제하면서 늑대를 발견할 경우 방문 처리를 해제하고 양을 발견할 경우 종료하도록 한다.

그리고 ② 에서 7번 양으로 이동한 경우를 생각해보도록 하자. (이때 1번, 3번, 7번 노드가 방문 처리됨)

이번엔 루트 노드에서 8번 노드로 이동이 가능하며 10번 노드로는 이동이 불가능하다.

 

• 10번 : 루트 노드에서 6번으로 이동할 경우 양 4마리 늑대 3마리, 6번에서 9번으로 이동할 경우 양 4마리 늑대 4마리 이므로 모든 양이 잡아먹힌다. 따라서 이동할 수 없다.

 

 

⑤ 마지막으로 8번 노드로 이동한 경우이다. (이때 4번, 8번 노드가 방문 처리됨)

현재 양 5마리 늑대 3마리 이므로, 10번 노드로 이동할 수 없다.

따라서 모든 경우를 따져서 최대로 모을 수 있는 양은 5마리가 된다.

 

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

using namespace std;

int tree[20][2];
bool visited[20];

// 이동 경로에 대한 순서 정하기
void set_order(int cur, vector<int>& v) {
	if (tree[cur][0]) {
		v.push_back(tree[cur][0]);
		set_order(tree[cur][0], v);
		if (tree[cur][1]) {
			v.push_back(tree[cur][1]);
			set_order(tree[cur][1], v);
		}
	}
}

// fin 위치로 이동할 수 있는지를 판단하는 함수
// 이때, cur 의 초깃값은 root 노드, fin 위치에는 양이 존재
bool tree_traversal(int cur, int fin, int& sheep, int& wolf,
	vector<int> info, deque<int> Dq) {
	if (cur == fin) {
		deque<int> tmp = Dq;
		while (!Dq.empty()) {
			int x = Dq.front();
			Dq.pop_front();
			if (!visited[x]) {
				if (info[x]) wolf++;
				else sheep++;
			}
			if (wolf == sheep) {
				return false;
			}
		}
		while (!tmp.empty()) {
			int x = tmp.front();
			tmp.pop_front();
			visited[x] = true;
		}
		return true;
	}
	bool ret = false;
	if (tree[cur][0]) {
		Dq.push_back(tree[cur][0]);
		ret |= tree_traversal(tree[cur][0], fin, sheep, wolf, info, Dq);
		Dq.pop_back();
		if (tree[cur][1]) {
			Dq.push_back(tree[cur][1]);
			ret |= tree_traversal(tree[cur][1], fin, sheep, wolf, info, Dq);
			Dq.pop_back();
		}
	}
	return ret;
}

// 역으로 방문을 해제해주는 함수
// 이때 양(해제) => 늑대(해제) => 늑대(해제) => 양(종료) 방법으로 진행
// 즉, 양을 한번 더 만날 경우 return  
void visited_restore(int cur, int fin, int& sheep, int& wolf,
	vector<int> info, deque<int> Dq) {
	if (cur == fin) {
		visited[Dq.back()] = false;
		Dq.pop_back();
		sheep--;
		while (!Dq.empty()) {
			int x = Dq.back();
			Dq.pop_back();
			if (info[x]) {
				wolf--;
				visited[x] = false;
			}
			else {
				break;
			}
		}
		return;
	}
	if (tree[cur][0]) {
		Dq.push_back(tree[cur][0]);
		visited_restore(tree[cur][0], fin, sheep, wolf, info, Dq);
		Dq.pop_back();
		if (tree[cur][1]) {
			Dq.push_back(tree[cur][1]);
			visited_restore(tree[cur][1], fin, sheep, wolf, info, Dq);
			Dq.pop_back();
		}
	}
}

// 재귀적으로 양을 최대로 모을 수 있도록 구하는 함수
int sheep_and_wolf(int sheep_cnt, int wolf_cnt, vector<int>& info, vector<int>& order) {
	int result = sheep_cnt;
	int tmp_sheep = sheep_cnt, tmp_wolf = wolf_cnt;
	bool op = false;
	deque<int> Dq;
	Dq.push_back(0);
	for (int i = 0; i < order.size(); i++) {
		int move = order[i];
		if (!info[move] && !visited[move]) {
			if (tree_traversal(0, move, sheep_cnt, wolf_cnt, info, Dq)) {
				result = max(result, sheep_cnt);
				result = max(result, sheep_and_wolf(sheep_cnt, wolf_cnt, info, order));
				visited_restore(0, move, sheep_cnt, wolf_cnt, info, Dq);
			}
			sheep_cnt = tmp_sheep;
			wolf_cnt = tmp_wolf;
		}
	}
	return result;
}

int solution(vector<int> info, vector<vector<int>> edges) {
	vector<int> order;
	int answer = 1, sheep_cnt = 1, wolf_cnt = 0;

	for (int i = 0; i < edges.size(); i++) {
		int cur = edges[i][0], next = edges[i][1];
		if (!tree[cur][0]) tree[cur][0] = next;
		else tree[cur][1] = next;
	}

	set_order(0, order);

	visited[0] = true;
	answer = sheep_and_wolf(1, 0, info, order);

	return answer;
}

 

---

6. 파괴되지 않은 건물

 

문제 링크 : 코딩테스트 연습 - 파괴되지 않은 건물 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 파괴되지 않은 건물

 

imos 기법을 활용하는 문제이다.

이 문제는 어떻게 해결해야 할지 몰라서 아이디어를 얻고 해결하였다.

 

imos 기법이란?

 

예를 들어 2차원 배열 Map[N][N] 이 존재한다고 할 때, (x1, y1) 지점부터 (x2, y2) 지점까지 값을 t 만큼 증가시킨다고 할 때, Imos[N][N] 배열을 활용하여 Map[N][N] 의 값을 업데이트 하는 기법이다. (이때 x1 ≤ x2,  y1 ≤ y2)

 

 

위와 같이 (x1, y1) ~ (x2, y2) 의 직사각형 영역에 t 값을 증가하려고 한다.

 

 

Imos 배열에 위와 같이 값을 넣어준다. (이때 Imos 배열의 모든 원소의 초기값은 0)

 

• Imos[x1][y1] = Imos[x1][y1] + t
• Imos[x1][y2 + 1] = Imos[x1][y2 + 1] - t
• Imos[x2 + 1][y1] = Imos[x2 + 1][y1] - t
• Imos[x2 + 1][y2 + 1] = Imos[x2 + 1][y2 + 1] + t

 

 

오른쪽으로 Imos 값을 스위핑 해준다.

아래 코드와 같이 스위핑 가능하다.

for(int i=0; i<R; i++){
    for(int j=1; j<C; j++){
        imos[i][j] += imos[i][j - 1]; 
    }
}

 

 

이번엔 아래쪽으로 Imos 값을 스위핑 해준다.

아래 코드와 같이 스위핑 가능하다.

for(int i=0; i<C; i++){
    for(int j=1; j<R; j++){
        imos[j][i] += imos[j - 1][i]; 
    }
}

 

마지막으로 Imos 값을 Map 에 적용하면 된다.

아래 코드와 같이 적용하면 된다.

for(int i=0; i<R; i++){
    for(int j=0; j<C; j++){
        Map[i][j] += imos[i][j];
    }
}

 

#include <string>
#include <vector>

using namespace std;

int Map[1001][1001], imos[1001][1001];

void get_Imos(int r1, int c1, int r2, int c2, int degree) {
	imos[r1][c1] += degree;
	imos[r1][c2 + 1] += -degree;
	imos[r2 + 1][c1] += -degree;
	imos[r2 + 1][c2 + 1] += degree;
}

void sweep_Map(int R, int C) {
	int tmp = 0;
	// 1. 오른쪽으로 sweep
	for (int i = 0; i < R; i++) {
		for (int j = 1; j < C; j++) {
			imos[i][j] += imos[i][j - 1];
		}
	}

	// 2. 아래로 sweep
	for (int i = 0; i < C; i++) {
		for (int j = 1; j < R; j++) {
			imos[j][i] += imos[j - 1][i];
		}
	}

	// 3. imos 적용
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			Map[i][j] += imos[i][j];
		}
	}
}

int find_Destory(int R, int C) {
	int ret = 0;
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			if (Map[i][j] <= 0) ret++;
		}
	}
	return ret;
}

int solution(vector<vector<int>> board, vector<vector<int>> skill) {
	int answer = 0, row, col;

	row = board.size();
	for (int i = 0; i < board.size(); i++) {
		col = board[i].size();
		for (int j = 0; j < board[i].size(); j++) {
			Map[i][j] = board[i][j];
		}
	}

	for (int i = 0; i < skill.size(); i++) {
		int type, r1, c1, r2, c2, degree;
		type = skill[i][0];
		r1 = skill[i][1], c1 = skill[i][2];
		r2 = skill[i][3], c2 = skill[i][4];
		degree = skill[i][5];
		if (type == 1) degree = -degree;
		get_Imos(r1, c1, r2, c2, degree);
	}

	sweep_Map(row, col);
	answer = row * col - find_Destory(row, col);

	return answer;
}