2021 KAKAO BLIND RECRUITMENT 문제 리뷰

1. 신규 아이디 추천

 

문제 링크 : 코딩테스트 연습 - 신규 아이디 추천 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 신규 아이디 추천

 

단순 문자열 구현 문제이다.

문제에서 주어진 7단계를 순차적인 처리 과정을 통해 신규 유저가 입력한 아이디가 카카오 아이디 규칙에 맞는 지 검사하고 규칙에 맞지 않은 경우 규칙에 맞는 새로운 아이디를 추천해주도록 구현해야 한다.

신규 유저가 입력한 아이디가 new_id 라고 할 때,

1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다.
2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다.
3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다.
4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다.
5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다.
6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다.
     만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다.
7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

위 단계를 거쳐서 아이디를 지정해주면 된다.

 

 

※ 단계별 코드 

① new_id의 모든 대문자를 대응되는 소문자로 치환하는 코드

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

	// 1단계
	for (int i = 0; i < new_id.size(); i++) {
		if (new_id[i] >= 'A' && new_id[i] <= 'Z') {
			char c = (new_id[i] - 'A' + 97);
			answer += c;
		}
		else answer += new_id[i];
	}

우선 빈 문자열 answer 에다가 new_id 문자를 하나씩 접근해가며 대문자를 발견할 경우, 소문자로 변경하여 더해준다.

 

② new_id 에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거하는 코드

	// 2단계
	new_id = answer;
	answer = "";
	for (int i = 0; i < new_id.size(); i++) {
		if ((new_id[i] >= 'a' && new_id[i] <= 'z') || (new_id[i] >= '0' && new_id[i] <= '9')
			|| new_id[i] == '-' || new_id[i] == '_' || new_id[i] == '.')
			answer += new_id[i];
	}

1단계에서 만든 문자열(answer)을 new_id 에 담아두고 다시 answer 를 빈 문자열부터 시작하여 위 조건을 발견할 때만 이어주도록 해준다.

 

③ new_id 에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환하는 코드

	// 3단계
	new_id = answer;
	answer = "";
	for (int i = 0; i < new_id.size(); i++) {
		if (new_id[i] == '.') {
			while (i < new_id.size() && new_id[i] == '.') {
				i++;
			}
			answer += ".";
			i -= 1;
		}
		else
			answer += new_id[i];
	}

2단계에서 만든 문자열(answer)을 new_id 에 담아두고 다시 answer 를 빈 문자열부터 시작하여 마침표(.)를 발견할 때마다 마침표를 스킵하여 마침표 하나만을 붙여주도록 구현하였다.

이때 i -= 1 을 한 이유는 마침표가 아닌 문자에서 그 다음 문자로 넘어가는 것을 방지하기 위함이다.

 

④ new_id 에서 마침표(.)가 처음이나 끝에 위치한다면 제거하는 코드

	// 4단계
	new_id = answer;
	answer = "";
	for (int i = 0; i < new_id.size(); i++) {
		if (i == 0 && new_id[i] == '.') continue;
		if (i == new_id.size() - 1 && new_id[i] == '.') continue;
		answer += new_id[i];
	}

3단계에서 마침표를 2번 이상 연속된 부분을 하나의 마침표로 치환하였기 때문에, 첫번째 인덱스와 마지막 인덱스에서 마침표를 발견하게 될 경우만 고려해서 문자를 이어가도록 하면 된다.

 

⑤ new_id 가 빈 문자열일 경우, new_id 에 "a" 를 대입하는 코드

	// 5단계
	new_id = answer;
	if (new_id.size() == 0) new_id += "a";

단순하게 빈 문자열일때 "a" 를 대입하도록 하면 된다.

 

⑥ new_id 길이가 16자 이상일때, 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거하고 만약 제거 후 마침표(.)가 new_id 의 끝에 위치할 때 끝에 위치한 마침표(.) 문자를 제거하는 코드

	// 6단계
	answer = "";
	if (new_id.size() >= 16) {
		answer = new_id.substr(0, 15);
		if (new_id[14] == '.')
			answer = new_id.substr(0, 14);
	}
	else answer = new_id;

16자 이상일 경우 첫 15개의 문자를 모두 이어준 후에 가장 마지막에 마침표가 있을 경우 마침표를 제외한 나머지 문자들을 가져오도록 하면 된다.

16자 미만일 경우 가장 마지막에 마침표를 이전 단계에서 제거하였으므로 그대로 가면 된다.

 

⑦ new_id의 길이가 2 이하일 경우, new_id의 마지막 문자를 new_id 길이가 3이 될 때까지 반복해서 끝에 붙이는 코드

	// 7단계
	if (answer.size() <= 2) {
		char c = answer[answer.size() - 1];
		if (answer.size() == 1) {
			for (int i = 0; i < 2; i++) {
				answer += c;
			}
		}
		else {
			answer += c;
		}
	}

new_id의 길이가 1일 경우 마지막 문자를 2번 붙여주고 길이가 2일 경우 마지막 문자를 1번 붙여주면 된다.

 

전체 코드는 다음과 같다.

#include <string>
#include <vector>

using namespace std;

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

	// 1단계
	for (int i = 0; i < new_id.size(); i++) {
		if (new_id[i] >= 'A' && new_id[i] <= 'Z') {
			char c = (new_id[i] - 'A' + 97);
			answer += c;
		}
		else answer += new_id[i];
	}

	// 2단계
	new_id = answer;
	answer = "";
	for (int i = 0; i < new_id.size(); i++) {
		if ((new_id[i] >= 'a' && new_id[i] <= 'z') || (new_id[i] >= '0' && new_id[i] <= '9')
			|| new_id[i] == '-' || new_id[i] == '_' || new_id[i] == '.')
			answer += new_id[i];
	}

	// 3단계
	new_id = answer;
	answer = "";
	for (int i = 0; i < new_id.size(); i++) {
		if (new_id[i] == '.') {
			while (i < new_id.size() && new_id[i] == '.') {
				i++;
			}
			answer += ".";
			i -= 1;
		}
		else
			answer += new_id[i];
	}

	// 4단계
	new_id = answer;
	answer = "";
	for (int i = 0; i < new_id.size(); i++) {
		if (i == 0 && new_id[i] == '.') continue;
		if (i == new_id.size() - 1 && new_id[i] == '.') continue;
		answer += new_id[i];
	}

	// 5단계
	new_id = answer;
	if (new_id.size() == 0) new_id += "a";

	// 6단계
	answer = "";
	if (new_id.size() >= 16) {
		answer = new_id.substr(0, 15);
		if (new_id[14] == '.')
			answer = new_id.substr(0, 14);
	}
	else answer = new_id;

	// 7단계
	if (answer.size() <= 2) {
		char c = answer[answer.size() - 1];
		if (answer.size() == 1) {
			for (int i = 0; i < 2; i++)
				answer += c;
		}
		else {
			answer += c;
		}
	}

	return answer;
}

 

 

---

 

2. 메뉴 리뉴얼

 

문제 링크 : 코딩테스트 연습 - 메뉴 리뉴얼 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 메뉴 리뉴얼

 

dfs 를 활용한 문제이다.

우선, orders 배열의 크기는 최대 20 이며 orders 배열의 원소의 최대 크기는 10 이다.

그리고 course 배열의 크기는 최대 10이다.

인풋 사이즈가 적은 만큼 널널하게 통과가 가능한 것을 파악할 수 있다.

 

이때 orders 배열의 크기를 n, orders 배열의 원소 크기를 m, 그리고 course 배열의 크기를 k 라고 한다면,

시간복잡도는 course 배열의 크기만큼 orders 에 담긴 원소들을 dfs 를 통해 가져올 수 있는 음식들을 선별하여 가장 많이 담긴 메뉴를 선별해야 하므로 O(n * m * k * \(2^{m}\)) 이 된다.

k = 10, n = 20, m = 10 라고 한다면, 10 * 20 * 1024 * 10= 2,048,000 으로 널널하게 통과가 가능해보인다.

 

 

※ 문제 접근 방법

① 우선 orders 의 각 원소들을 오름차순으로 정렬한다.

입출력 예시로 ["XYZ", "XWY", "WXA"] 를 살펴본다면, dfs 를 통해 2번째 원소를 통해 XW 가 선택이 될 수 있고 3번째 원소중에 WX 가 선택이 될 수 있다.

이는 같은 요리임에도 불구하고 map 으로 해당 요리를 카운팅하는 과정에서 다른 요리로 인식하는 문제점이 있다.

따라서 각 원소마다 오름차순으로 정렬시켜서 요리가 오름차순으로 선택이 될 수 있도록 해야 한다.

 

② course 의 각 값 마다 요리들이 몇 번 선택될 수 있는지를 저장하기 위한 vector와 새로운 요리들이 몇번 카운팅 됬는지를 판별할 수 있는 map을 생성한다.

 

• vector<pair<string, int>> menu : dfs 를 통해 얻어낸 요리, 그리고 몇 번 선택됬는지를 저장하기 위한 용도
• map<string, int> m : dfs 를 통해 얻어낸 요리를 카운팅하기 위한 용도

 

그리고 dfs 를 통해 course 의 값만큼 요리를 선정하여 해당 요리가 몇번 카운팅 됬는지를 map 을 통해 알 수 있으며 이를 vector 에 map 에 담긴 값들을 넣어주고 정렬하여 max 값과 동일한 요리들을 answer 에 push 해주면 된다.

 

dfs 함수를 보도록 한다.

bool visited[10];

void dfs(int idx, int fin, string order,
	vector<pair<string, int>>& menu, map<string, int>& m)
{
	if (idx == order.size())
	{
		string tmp = "";
		for (int i = 0; i < order.size(); i++)
		{
			if (visited[i])
				tmp += order[i];
		}
		if (fin != tmp.size())
			return;
		if (!m[tmp])
			menu.push_back({ tmp, 1 });
		m[tmp]++;
		return;
	}
	visited[idx] = false;
	dfs(idx + 1, fin, order, menu, m);
	visited[idx] = true;
	dfs(idx + 1, fin, order, menu, m);
}

 

• idx : orders 의 원소를 한 문자씩 접근하기 위한 용도 (0 => 1 => ... => orders.size() - 1)
• fin : course 의 값으로 즉, 몇 개의 요리를 선별해야 할 지에 대한 값을 의미
• order : orders 의 원소들 중 하나
• vector<pair<string, int>> menu : dfs 를 통해 얻어낸 요리, 그리고 몇 번 선택됬는지를 저장하기 위한 용도
• map<string, int> m : dfs 를 통해 얻어낸 요리를 카운팅하기 위한 용도

 

visited 배열을 전역변수로 선언하여 선별할 수 있는 모든 요리를 탐색함으로써 얻어낸 요리 tmp 에 대해서 fin 값과 동일하게 될 경우 map 을 이용하여 아직 카운팅 되지 않을 경우 menu 벡터에 해당 요리를 push 하며 m[tmp]++ 을 함으로써 해당 요리가 몇번 카운팅 되었는지를 알 수 있도록 해주었다.

 

dfs 를 모든 orders 의 원소들에 적용함으로써 menu 에 요리들이 담겨져 있을 경우, map 으로 카운팅했던 값들을 옮겨준 후에 카운팅된 값을 기준으로 내림차순으로 sorting 한다.

그리고 첫번째 원소가 결국 가장 많이 선택된 요리이며 2번 이상 선택이 된 경우에만 answer 벡터에 요리를 push 한다.

선택이 동일하게 될 경우가 존재하므로 이를 고려해서 push 해주면 된다.

 

③ answer 에 담긴 요리들을 오름차순으로 정렬한다.

 

전체 코드는 다음과 같다.

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

using namespace std;

bool visited[10];

void init()
{
	for (int i = 0; i < 10; i++)
		visited[i] = false;
}

void dfs(int idx, int fin, string order,
	vector<pair<string, int>>& menu, map<string, int>& m)
{
	if (idx == order.size())
	{
		string tmp = "";
		for (int i = 0; i < order.size(); i++)
		{
			if (visited[i])
				tmp += order[i];
		}
		if (fin != tmp.size())
			return;
		if (!m[tmp])
			menu.push_back({ tmp, 1 });
		m[tmp]++;
		return;
	}
	visited[idx] = false;
	dfs(idx + 1, fin, order, menu, m);
	visited[idx] = true;
	dfs(idx + 1, fin, order, menu, m);
}

bool compare(pair<string, int> x, pair<string, int> y)
{
	return (x.second > y.second);
}

vector<string> solution(vector<string> orders, vector<int> course) {
	vector<string> answer;

	for (int i = 0; i < orders.size(); i++)
		sort(orders[i].begin(), orders[i].end());
	for (int i = 0; i < course.size(); i++)
	{
		vector<pair<string, int>> menu;
		map<string, int> m;
		for (int j = 0; j < orders.size(); j++)
		{
			if (orders[j].size() < course[i])
				continue;
			init();
			dfs(0, course[i], orders[j], menu, m);
		}
		if (menu.size())
		{
			for (int j = 0; j < menu.size(); j++)
				menu[j].second = m[menu[j].first];
			sort(menu.begin(), menu.end(), compare);
			int max_order = menu[0].second;
			if (max_order > 1)
			{
				for (int j = 0; j < menu.size(); j++)
				{
					if (menu[j].second != max_order)
						break;
					answer.push_back(menu[j].first);
				}
			}
		}
	}
	sort(answer.begin(), answer.end());

	return answer;
}

 

 

---

 

3. 순위 검색

 

문제 링크 : 코딩테스트 연습 - 순위 검색 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 순위 검색

 

다차원 배열을 활용한 구현 문제이다.

5차원 배열을 활용하여 해결하였으며, int people[4][3][3][3][100001] 를 전역변수로 선언하였다.

 

people[a][b][c][d][e] 의 값을 info 로 주어진 여러 조건들을 통해 값을 설정할 수 있다.

 

• a : "cpp", "java", "python" 을 0, 1, 2 으로 설정하였으며 해당 조건을 고려하지 않을 경우는 3 으로 설정
• b : "backend", "frontend" 를 0, 1 으로 설정하였으며 해당 조건을 고려하지 않을 경우는 2 으로 설정
• c : "junior", "senior" 를 0, 1 으로 설정하였으며 해당 조건을 고려하지 않을 경우는 2 으로 설정
• d : "chicken", "pizza" 를 0, 1 으로 설정하였으며 해당 조건을 고려하지 않을 경우는 2 으로 설정
• e : a, b, c, d 의 조건을 만족할 때, e 점 이상인 사람들의 숫자는 people[a][b][c][d][e] 가 되도록 설정

 

위와 같이 인덱스를 부여하기 위해 map 을 사용했으며 다음과 같이 설정하였다.

map<string, int> m;

void init()
{
	m["cpp"] = 0, m["java"] = 1, m["python"] = 2;
	m["backend"] = 0, m["frontend"] = 1;
	m["junior"] = 0, m["senior"] = 1;
	m["chicken"] = 0, m["pizza"] = 1;
	m["-"] = -1;
}

 

이 문제를 풀면서 느꼇던 점은 조건을 고려하지 않을 경우를 처리하는 부분이다.

이 부분에 대해서 고민을 여러번 해봤지만, 아무래도 모든 케이스에 대해서 값을 하나하나 증가시켜서 단순하게 값을 내도록 하였다.

 

우선, info 로 주어지는 언어, 직군, 경력, 소울푸드, 그리고 점수 5가지 정보를 통해 다음과 같이 처리를 하였다.

people[언어][직군][경력][소울푸드][점수]++;

 

문제는 나중에 쿼리로 주어지는 경우에 조건을 고려하지 않은 경우에 대해 값을 낼 수 있어야 한다.

이 부분 때문에 조건을 고려하지 않는 경우의 모든 케이스를 나눠서 다음과 같이 처리를 하였다.

// 조건을 1개 고려하지 않을 경우
people[3][직군][경력][소울푸드][점수]++; people[언어][2][경력][소울푸드][점수]++;
people[언어][직군][2][소울푸드][점수]++; people[언어][직군][경력][2][점수]++;

// 조건을 2개 고려하지 않을 경우
people[3][2][경력][소울푸드][점수]++; people[3][직군][2][소울푸드][점수]++;
people[3][직군][경력][2][점수]++; people[언어][2][2][소울푸드][점수]++;
people[언어][2][경력][2][점수]++; people[언어][직군][2][2][점수]++;

// 조건을 3개 고려하지 않을 경우
people[3][2][2][소울푸드][점수]++; people[3][2][경력][2][점수]++;
people[3][직군][2][2][점수]++; people[언어][2][2][2][점수]++;

// 조건을 4개 고려하지 않을 경우
people[3][2][2][2][점수]++;

 

모든 info 에 대해 처리하였다면, 몇 점 이상일 경우 몇명에 대한 세팅 작업이 이뤄져야 한다.

예를 들어 20점 1명, 40점 2명, 60점 3명 80점 2명 100점 1명 이 있다고 가정해본다.

그렇다면 100점 1명 => 80점 3명(2 + 1) => 60점 6명(3 + 3) => 40점 8명(2 + 6) => 20점 9명(1 + 8)

와 같이 현재 점수에 해당하는 인원의 수를 현재 점수보다 높은 점수 이상의 인원의 수를 누적하여 몇 점 이상일 경우 몇명인지에 대해서 알 수 있다.

 

즉, 다음과 같이 세팅이 가능하다.

void set_scores()
{
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 3; j++)
			for (int u = 0; u < 3; u++)
				for (int v = 0; v < 3; v++)
					for (int k = 99999; k >= 1; k--)
						people[i][j][u][v][k] += people[i][j][u][v][k + 1];
}

 

이제 쿼리에 대한 답을 answer 벡터에 넣어주면 된다.

이때, "-" 는 조건을 고려하지 않기 때문에 해당 값을 발견하게 될 경우, 조건을 고려하지 않도록 하는 인덱스로 변환함으로써 인원의 수를 내면 된다.

 

다음과 같이 query 각각에 해당하는 언어, 직군, 경력, 소울푸드, 그리고 점수를 통해 answer 벡터에 인원수를 push가 가능하다.

void solve_query(vector<int>& answer, int language, int work,
	int level, int food, int score)
{
	if (language == -1) language = 3;
	if (work == -1) work = 2;
	if (level == -1) level = 2;
	if (food == -1) food = 2;
	answer.push_back(people[language][work][level][food][score]);
}

 

 

전체 코드는 다음과 같다.

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

using namespace std;

int people[4][3][3][3][100001];
map<string, int> m;

void init()
{
	m["cpp"] = 0, m["java"] = 1, m["python"] = 2;
	m["backend"] = 0, m["frontend"] = 1;
	m["junior"] = 0, m["senior"] = 1;
	m["chicken"] = 0, m["pizza"] = 1;
	m["-"] = -1;
}

string get_info(string info, int* idx)
{
	string ret = "";

	while (info[*idx] != ' ')
	{
		ret += info[*idx];
		*idx += 1;
	}
	*idx += 1;
	return (ret);
}

void set_scores()
{
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 3; j++)
			for (int u = 0; u < 3; u++)
				for (int v = 0; v < 3; v++)
					for (int k = 99999; k >= 1; k--)
						people[i][j][u][v][k] += people[i][j][u][v][k + 1];
}

void solve_query(vector<int>& answer, int language, int work,
	int level, int food, int score)
{
	if (language == -1) language = 3;
	if (work == -1) work = 2;
	if (level == -1) level = 2;
	if (food == -1) food = 2;
	answer.push_back(people[language][work][level][food][score]);
}

vector<int> solution(vector<string> info, vector<string> query) {
	vector<int> answer;

	init();
	for (int i = 0; i < info.size(); i++)
	{
		int idx = 0;
		string language = get_info(info[i], &idx);
		string work = get_info(info[i], &idx);
		string level = get_info(info[i], &idx);
		string food = get_info(info[i], &idx);
		int score = stoi(&info[i][idx]);
		people[m[language]][m[work]][m[level]][m[food]][score]++;

		// 조건을 1개 고려하지 않을 경우
		people[3][m[work]][m[level]][m[food]][score]++; people[m[language]][2][m[level]][m[food]][score]++;
		people[m[language]][m[work]][2][m[food]][score]++; people[m[language]][m[work]][m[level]][2][score]++;

		// 조건을 2개 고려하지 않을 경우
		people[3][2][m[level]][m[food]][score]++; people[3][m[work]][2][m[food]][score]++;
		people[3][m[work]][m[level]][2][score]++; people[m[language]][2][2][m[food]][score]++;
		people[m[language]][2][m[level]][2][score]++; people[m[language]][m[work]][2][2][score]++;

		// 조건을 3개 고려하지 않을 경우
		people[3][2][2][m[food]][score]++; people[3][2][m[level]][2][score]++;
		people[3][m[work]][2][2][score]++; people[m[language]][2][2][2][score]++;

		// 조건을 4개 고려하지 않을 경우
		people[3][2][2][2][score]++;
	}
	set_scores();
	for (int i = 0; i < query.size(); i++)
	{
		int idx = 0;
		string language = get_info(query[i], &idx);
		idx += 4;
		string work = get_info(query[i], &idx);
		idx += 4;
		string level = get_info(query[i], &idx);
		idx += 4;
		string food = get_info(query[i], &idx);
		int score = stoi(&query[i][idx]);
		solve_query(answer, m[language], m[work], m[level], m[food], score);
	}

	return answer;
}

 

 

---

 

4. 합승 택시 요금

 

문제 링크 : 코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 합승 택시 요금

 

다익스트라를 이용한 문제이다.

"무지" 와 "어피치" 가 택시 합승을 적절히 이용하여 택시요금을 얼마나 아낄 수 있는지를 묻는 문제이다.

 

 

우선 2차원 배열 int dist[201][201] 에 대해 살펴보도록 한다.

dist[x][y] : x 지점을 시작지점으로 하여 y 지점까지 이동하는데 최소 택시요금

위와 같이 dist 배열을 설계하게 된다면, 이 문제를 해결할 수 있다는 것을 짐작할 수 있다.

 

그렇다면 2차원 배열 dist 를 설정하는데 시간복잡도는 어떻게 될까?

 

지점 갯수 |V| = n 이며 fully connected graph 라고 한다면, 간선의 갯수 |E| = \(\frac{n(n-1)}{2}\) 이다.

이때 특정 지점에서 모든 지점으로의 최소 택시요금을 알아내기 위해 필요한 시간 복잡도는 O(|E| log(|V|)) 이다.

그리고 특정 지점이 결국 모든 지점이 되도록 위에서 설계하였기 때문에 최종 시간 복잡도는 O(\(|E|^{2}\) log(|V|)) 이다. 

인풋 사이즈로 지점 갯수가 최대 200으로 주어지기 때문에 모든 지점에서의 다익스트라 알고리즘을 사용할 수 있게 된다.

 

dist 배열을 채우는 과정은 다음과 같이 구현하였다.

void set_dijkstra(int s)
{
    priority_queue<pair<int, int>> pq;
    
    pq.push({0, s});
    dist[s][s] = 0;
    while (!pq.empty())
    {
        int d = -pq.top().first, cur = pq.top().second;
        pq.pop();
        
        if (d < dist[s][cur])
            continue;
        for (int i=0; i<info[cur].size(); i++)
        {
            int next = info[cur][i].first, next_d = d + info[cur][i].second;
            if (next_d < dist[s][next])
            {
                dist[s][next] = next_d;
                pq.push({-next_d, next});
            }
        }
    }
}

 

 

그렇다면 지점 갯수가 n 이며 start 지점을 S, "무지" 가 도착해야 할 지점을 A, "어피치" 가 도착해야 할 지점을 B, 그리고 "무지" 와 "어피치" 가 택시를 합승하고 내리는 곳을 E 라고 할 때, 다음과 같이 설계할 수 있다.

answer = \(\underset{1\leq E\leq N}{min}\){ dist[S][E] + (dist[E][A] + dist[E][B]) }

 

합승하고 내리는 지점을 1부터 N까지 설정함으로써 내야할 택시요금중 가장 적은 택시요금이 되도록 하는 값을 할당하여 반환하기만 하면 된다.

 

전체 코드는 다음과 같다.

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

using namespace std;

int dist[201][201];
vector<pair<int, int>> info[201];

void init()
{
    for (int i=1; i<=200; i++)
        for (int j=1; j<=200; j++)
            dist[i][j] = 100000000;
}

void set_dijkstra(int s)
{
    priority_queue<pair<int, int>> pq;
    
    pq.push({0, s});
    dist[s][s] = 0;
    while (!pq.empty())
    {
        int d = -pq.top().first, cur = pq.top().second;
        pq.pop();
        
        if (d < dist[s][cur])
            continue;
        for (int i=0; i<info[cur].size(); i++)
        {
            int next = info[cur][i].first, next_d = d + info[cur][i].second;
            if (next_d < dist[s][next])
            {
                dist[s][next] = next_d;
                pq.push({-next_d, next});
            }
        }
    }
}

int solution(int n, int s, int a, int b, vector<vector<int>> fares) {
    int answer = 100000000;
   
    for (int i=0; i<fares.size(); i++)
    {
        int u = fares[i][0], v = fares[i][1], d = fares[i][2];
        info[u].push_back({v, d});
        info[v].push_back({u, d});
    }
    
    init();
    for (int i=1; i<=n; i++)
        set_dijkstra(i);
    
    for (int e=1; e<=n; e++)
        answer = min(answer, dist[s][e] + dist[e][a] + dist[e][b]);
    
    return answer;
}

 

 

---

 

5. 광고 삽입

 

문제 링크 : 코딩테스트 연습 - 광고 삽입 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 광고 삽입

 

Prefix Sum 을 활용하여 해결해야 하는 문제이다.

2022 KAKAO BLIND RECRUITMENT 문제 중에 2차원 배열을 누적 합으로 해결하는 문제가 있었는데 이 문제는 1차원 배열을 누적 합으로 해결하는 문제이다.

연속으로 누적 합에 대한 문제를 묻는걸 보니 올해 시험에도 나올 수 있는 가능성이 농후에 보인다. (잘 봐둬야겠다)

 

우선 시간이 주어졌기 때문에 이를 하나의 자연수 형태로 나타내도록 해야 하는것을 짐작할 수 있다.

시간은 00:00:01 이상 99:59:59 이하이므로 이를 자연수로 나타낼 경우 최댓값은 다음과 같다.

(99 * 3600) + (59 * 60) + (59) = 359999 

 

따라서 long long 형 배열 long long sum[360000] 을 선언하여 누적합에 대한 처리가 가능하도록 설정하였다.

(int 형 대신 long long 형으로 선언한 이유는 아래에서 설명)

 

 

위 그림과 같이 매개변수로 주어진 vector<string> logs 의 시간들에 대해서 누적합에 대한 처리가 필요하다.

따라서 다음과 같이 sum 배열을 시작 시간(log_s)과 끝나는 시간(log_e) 을 가지고 누적합 처리가 가능하다.

    for (int i=0; i<logs.size(); i++)
    {
        int log_s = get_time(logs[i], 0);
        int log_e = get_time(logs[i], 9);
        sum[log_s] += 1, sum[log_e] -= 1;
    }

 

sum[log_e + 1] -= 1 이 아닌 sum[log_e] -= 1 을 한 이유 ?

 

문제에서 의도하는 정답은 예를 들어 01:00:00 에서 1 시간 광고를 시청한다고 가정할 때, 

01:00:00 (1초), 01:00:01 (2초), 01:00:02 (3초), ... 01:59:59 (3600초)

즉, 01:00:00 부터 01:59:59 까지 광고를 시청한 다음에 02:00:00 에 끝나는 것을 의미한다.

즉, 끝나는 시간이 log_e 이므로 sum[log_e] -= 1 을 해줘야 한다.

 

logs 에 대한 모든 sum 처리를 해주었다면, 스위핑 기법을 이용하여 각 시간 별로 광고를 몇 번 시청하였는지에 대한 정보를 세팅하도록 한다.

코드는 다음과 같다.

    for (int i=1; i<=360000; i++)
        sum[i] += sum[i-1];

 

시작 시간을 start, 광고가 끝나는 시간을 end 라고 설정할 때,

start = 0, end = adv_time 으로 설정이 가능하다. (00:00:00 ~ adv_time)

그리고 long long 타입으로 time, max_time 을 선언하여 start ~ end 시간이 1 초씩 증가하면서 누적 시간을 갱신함으로써 최대 누적 시간을 구해낼 수 있다.

이때 int 타입으로 누적 시간을 구할때 최악의 경우 int 형이 최대 max 범위를 넘어가버리는 overflow 가 발생하기 때문에 이를 방지하기 위해 long long 타입으로 구해야만 한다.

이에 대한 코드는 다음과 같다.

    int start = 0, end = adv;
    long long max_time = 0, time = 0;
    
    answer = make_time(0);
    for (int i=0; i<end; i++)
    {
        time += sum[i];
    }
    max_time = time;
    start++, end++;
    while (end <= play)
    {
        time += (sum[end - 1] - sum[start - 1]);
        if (time > max_time)
        {
            max_time = time;
            answer = make_time(start);
        }
        start++, end++;
    }

 

전체 코드는 다음과 같다.

#include <string>
#include <vector>

using namespace std;

long long sum[360000];

int get_time(string time, int idx)
{
	return (3600 * stoi(&time[idx]) + 60 * stoi(&time[idx + 3]) + stoi(&time[idx + 6]));
}

string make_time(int time)
{
	int hour, minute, second;
	string ret = "";

	second = time % 60;
	time /= 60;
	minute = time % 60;
	time /= 60;
	hour = time;

	if (hour < 10) ret += "0" + to_string(hour);
	else ret += to_string(hour);
	ret += ":";
	if (minute < 10) ret += "0" + to_string(minute);
	else ret += to_string(minute);
	ret += ":";
	if (second < 10) ret += "0" + to_string(second);
	else ret += to_string(second);

	return ret;
}

string solution(string play_time, string adv_time, vector<string> logs) {
	string answer = "";

	int play = get_time(play_time, 0);
	int adv = get_time(adv_time, 0);

	for (int i = 0; i < logs.size(); i++)
	{
		int log_s = get_time(logs[i], 0);
		int log_e = get_time(logs[i], 9);
		sum[log_s] += 1, sum[log_e] -= 1;
	}

	for (int i = 1; i <= 360000; i++)
		sum[i] += sum[i - 1];

	int start = 0, end = adv;
	long long max_time = 0, time = 0;

	answer = make_time(0);
	for (int i = 0; i < end; i++)
	{
		time += sum[i];
	}
	max_time = time;
	start++, end++;
	while (end <= play)
	{
		time += (sum[end - 1] - sum[start - 1]);
		if (time > max_time)
		{
			max_time = time;
			answer = make_time(start);
		}
		start++, end++;
	}

	return answer;
}

 

---

 

6. 카드 짝 맞추기

 

문제 링크 : 코딩테스트 연습 - 카드 짝 맞추기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 카드 짝 맞추기

 

완전 탐색과 다익스트라를 이용한 문제이다.

 

4 x 4 크기로 격자 형태가 주어지며 최대 카드가 (6 * 2)개 배치된다는 점에서 완전 탐색이 가능하다는 것을 짐작할 수 있다.

이 문제에서 구현이 어려운 점은 방향키 or [Ctrl] + 방향키 에 대한 처리인 것 같다.

다익스트라 알고리즘과 동일한 방법으로 동일한 카드에서 동일한 카드로 방향키를 최대한 적게 누르는 동작의 횟수를 구하도록 하는 아이디어를 생각해내기 어려운 것 같다. 

 

※ 문제 접근 방법

① 놓여진 모든 카드에 대해서 모든 경우를 고려하여 카드를 제거해가도록 해야한다.

예를 들어 A, B, C 카드가 2개씩 있다고 하면, 카드를 제거하는 방법은 다음과 같다.

 

A => B => C, A => C => B,

B => A => C, B => C => A,

C => A => B, C => B => A

 

총 6(3!)가지 방법을 통해 카드를 제거할 수 있다.

그렇다면 문제에서 최대 6개의 카드가 2개씩 존재한다고 했으므로 (6!)가지 방법을 통해 카드를 제거할 수 있다.

 

② 동일한 카드를 2가지 경우로 나눠서 제거해야 한다.

예를 들어 카드 A_1, A_2 의 위치를 (x1, y1), (x2, y2) 라 하고 현재 위치 (r, c) 에서 제거한다고 할 때, 

1. (r, c) => (x1, y1) => (x2, y2) : 현재 위치에서 A_1 카드로 이동 후, enter 키를 누른 후에 A_2 카드로 이동하여 enter 키를 눌러서 카드를 제거한다.
2. (r, c) => (x2, y2) => (x1, y1) : 현재 위치에서 A_2 카드로 이동 후, enter 키를 누른 후에 A_1 카드로 이동하여 enter 키를 눌러서 카드를 제거한다.

위 2가지 방법으로 동일한 카드를 제거할 수 있다.

이때, 현재 위치에서 A_1 카드로 이동할 때 누를 수 있는 방향키의 최소 갯수와 A_1 카드에서 A_2 카드로 이동할 때 누를 수 있는 방향키의 최소의 갯수를 어떻게 구해야 할 지에 대해서 생각해봐야 한다.

 

① , ② 에 대한 전반적인 코드를 아래와 같이 설계할 수 있다.

int go(vector<vector<int>>& board, int r, int c)
{
	int ret = 10000;
	int enter_key = 1;

	if (is_finish(board))
		return 0;

	for (int card = 1; card <= 6; card++)
	{
		int x[2], y[2], idx = 0;
		for (int i = 0; i < 4; i++)
			for (int j = 0; j < 4; j++)
				if (board[i][j] == card)
					x[idx] = i, y[idx] = j, idx++;
		if (idx == 0)
			continue;
		int key1 = direct_key(board, r, c, x[0], y[0]) + enter_key
			+ direct_key(board, x[0], y[0], x[1], y[1]) + enter_key;
		int key2 = direct_key(board, r, c, x[1], y[1]) + enter_key
			+ direct_key(board, x[1], y[1], x[0], y[0]) + enter_key;
		board[x[0]][y[0]] = board[x[1]][y[1]] = 0;
		ret = min({ ret, key1 + go(board, x[1], y[1]), key2 + go(board, x[0], y[0]) });
		board[x[0]][y[0]] = board[x[1]][y[1]] = card;
	}
	return ret;
}

 

• go(vector<vector<int>>& board, int r, int c) : 현재 (r, c) 에서 격자 위에 놓여진 카드를 전부 제거할 때 누를 수 있는 키의 최소 갯수를 반환하는 함수
• is_finish(board) : 현재 4x4 격자 위에 카드가 놓이지 않은 경우 true 를 반환하며, 더 이상 키를 누르지 않아도 되는 것을 암시 

key1, key2 의 값은 위에서 언급한 것 처럼, 현재 위치에서 동일한 카드를 2가지 경우로 나눠서 제거하는 과정에서 키를 누를 수 있는 최소 갯수를 의미한다.

그리고 key1, key2 를 구하면서 동시에 4 x 4 격자 위에 해당 카드를 제거하며 재귀적으로 그 다음 위치에서 동일한 카드를 누를 수 있는 키의 최소 갯수를 더한 것 중에 최솟값이 결국 정답이 된다.

재귀를 마치면 제거하였던 카드를 원상복구 시켜서 모든 경우에 대해서 탐색이 가능하도록 한다.

더 이상 카드를 놓을 수 없는 경우에는 0을 반환함으로써 정상적으로 재귀를 멈추도록 한다.

 

③ 현재 위치에서 도착 지점까지 누를 수 있는 방향키의 최소 갯수를 구하도록 하기 위해 다익스트라 알고리즘을 약간의 변형을 통해서 구할 수 있다.

우선 코드를 보도록 한다.

int direct_key(vector<vector<int>>& board, int s_x, int s_y, int e_x, int e_y)
{
	int key[4][4];

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			key[i][j] = 10000;

	priority_queue<pair<int, pair<int, int>>> pq;
	key[s_x][s_y] = 0;
	pq.push({ 0, {s_x, s_y} });
	while (!pq.empty())
	{
		int d = -pq.top().first;
		int x = pq.top().second.first, y = pq.top().second.second;
		pq.pop();
		if (key[x][y] < d)
			continue;
		if (x == e_x && y == e_y)
			return d;
		for (int i = 0; i < 4; i++)
		{
			int next_x = x, next_y = y, next_d = d;
			while (is_in(next_x + dx[i], next_y + dy[i]))
			{
				next_x += dx[i], next_y += dy[i], next_d++;
				if (board[next_x][next_y])
					break;
				if (next_d < key[next_x][next_y])
				{
					key[next_x][next_y] = next_d;
					pq.push({ -(next_d), {next_x, next_y} });
				}
			}
			if (d + 1 < key[next_x][next_y])
			{
				key[next_x][next_y] = d + 1;
				pq.push({ -(d + 1), {next_x, next_y} });
			}
		}
	}
}

 

• key[4][4] : 현재 시작 지점을 (s_x, s_y) 라고 했을 때, key[a][b] 의 값은 (s_x, s_y) 지점 부터 (a, b) 지점까지 누를 수 있는 키의 최소 갯수

while-loop 부분에서 격자 끝 지점에 도착하게 되는 경우와 카드를 만나게 되는 부분을 아래의 if 문을 통해 처리가 가능하다.

if 문에서의 (next_x, next_y) 의 지점은 카드를 발견하게 된 경우 or 격자 끝 지점에 도착하게 된 경우이다.

그게 아닐 경우 while 문 안에 if 문을 통해 다익스트라 알고리즘과 동일한 방식으로 진행하면 된다.

 

전체 코드는 다음과 같다.

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

using namespace std;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

bool is_finish(vector<vector<int>>& board)
{
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			if (board[i][j])
				return false;
	return true;
}

bool is_in(int x, int y)
{
	if (x >= 0 && x <= 3 && y >= 0 && y <= 3)
		return true;
	return false;
}

int direct_key(vector<vector<int>>& board, int s_x, int s_y, int e_x, int e_y)
{
	int key[4][4];

	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 4; j++)
			key[i][j] = 10000;

	priority_queue<pair<int, pair<int, int>>> pq;
	key[s_x][s_y] = 0;
	pq.push({ 0, {s_x, s_y} });
	while (!pq.empty())
	{
		int d = -pq.top().first;
		int x = pq.top().second.first, y = pq.top().second.second;
		pq.pop();
		if (key[x][y] < d)
			continue;
		if (x == e_x && y == e_y)
			return d;
		for (int i = 0; i < 4; i++)
		{
			int next_x = x, next_y = y, next_d = d;
			while (is_in(next_x + dx[i], next_y + dy[i]))
			{
				next_x += dx[i], next_y += dy[i], next_d++;
				if (board[next_x][next_y])
					break;
				if (next_d < key[next_x][next_y])
				{
					key[next_x][next_y] = next_d;
					pq.push({ -(next_d), {next_x, next_y} });
				}
			}
			if (d + 1 < key[next_x][next_y])
			{
				key[next_x][next_y] = d + 1;
				pq.push({ -(d + 1), {next_x, next_y} });
			}
		}
	}
}

int go(vector<vector<int>>& board, int r, int c)
{
	int ret = 10000;
	int enter_key = 1;

	if (is_finish(board))
		return 0;

	for (int card = 1; card <= 6; card++)
	{
		int x[2], y[2], idx = 0;
		for (int i = 0; i < 4; i++)
			for (int j = 0; j < 4; j++)
				if (board[i][j] == card)
					x[idx] = i, y[idx] = j, idx++;
		if (idx == 0)
			continue;
		int key1 = direct_key(board, r, c, x[0], y[0]) + enter_key
			+ direct_key(board, x[0], y[0], x[1], y[1]) + enter_key;
		int key2 = direct_key(board, r, c, x[1], y[1]) + enter_key
			+ direct_key(board, x[1], y[1], x[0], y[0]) + enter_key;
		board[x[0]][y[0]] = board[x[1]][y[1]] = 0;
		ret = min({ ret, key1 + go(board, x[1], y[1]), key2 + go(board, x[0], y[0]) });
		board[x[0]][y[0]] = board[x[1]][y[1]] = card;
	}
	return ret;
}

int solution(vector<vector<int>> board, int r, int c) {
	int answer;
	return (answer = go(board, r, c));
}