뚝딱뚝딱

요격 시스템

요격 시스템 문제는 먼저 sorting을 해주어야 한다.

이 때 어느 값을 기준으로 정렬할 것인지가 관건이 되는데..

주어진 예제에서 어떤 폭격 미사일 하나의 구간만을 고려한다고 해보자.

 예를 들면 4-5 구간의 미사일만을 고려해 보자.

4를 요격 범위의 start로 S, 5를 요격 범위의 end로 E라고 표현하고, 현재의 요격 범위로 두자.

end가 4(현재의 S)보다 작은 미사일의 경우, 현재의 요격 범위에 포함될 수 없다.

따라서 start가 5(현재의 E)보다 큰 미사일의 경우에도 현재의 요격 범위에 포함될 수 없다.

그러므로 요격 범위에 들어올 자격이 되는지는, 각 미사일 구간의 end 포인트 지점에 달려있다.

따라서 end를 기준으로 오름차순 정렬해준다.

end를 기준으로 오름차순 정렬해주면

[4,5],[4,8],[10,14],[11,13],[5,12],[3,7],[1,4] → [1,4], [4,5], [3,7], [4,8], [5,12], [11,13], [10,14]
이 된다.

미사일을 어차피 한번이상 쏘게 되어 있으니까, count는 1로 시작한다.

처음 요격 구간을 [1,4]로 설정하고 그 다음 구간부터 차례로 순회한다.

첫 S=1, E=4가 된다.

다음 미사일의 범위가 [4,5]이고, 이것의 시작 지점인 4가 현재 요격 구간의 E보다 작아야 한번에 쏠 수 있다.
(엔드 포인트인 4에서는 쏘지 못한다. 조건에 명시되어 있다.)

그런데 E보다 작지 않기 때문에 이 구간에는 첫번째 미사일 구간 빼고는 더이상 요격할 미사일이 없는 것이다.

따라서 count를 1올려주고, 다음 미사일 구간의 시작점을 s로, 끝점을 e로 하여 새로운 요격 범위를 갱신하고 위 과정을 반복하도록 한다.

그럼 최종 요격 발사 횟수를 COUNT를 반환함으로써 얻을 수 있다.

C++로 해결한 코드는 아래와 같다.

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

using namespace std;

bool cmp(vector<int> &v1, vector<int> &v2) {
	if (v1[1] == v2[1])
		return v1[0] < v2[0];
	else return v1[1] < v2[1];
}

int solution(vector<vector<int>> targets) {
	
	int answer = 0;

	sort(targets.begin(), targets.end(), cmp);

	int e = targets[0][1];

	answer++;

	for (int i = 1; i < targets.size(); i++) {
		if (targets[i][0] < e) {
			continue;
		}
		else {
			answer++;
			e = targets[i][1];
		}

	}

	return answer;
}

대충 만든 자판

이제는 익숙해진 문자열과 숫자 한번에 다루기!

문제를 몇번 풀어보니, 이 문제 역시 문자열과 숫자 개념이 더해진 것임을 바로 파악할 수 있었고, map을 사용하여 쉽게 해결할 수 있었다.

자판의 등장하는 문자를 char형태의 index로 보고, 어떤 위치의 버튼이든 최소한으로 눌렀을 때를 그 알파벳의 버튼 횟수로 저장하도록 하였다.

그러니까 keymap을 순회하면서, 등장하는 문자를 map의 인덱스로 넣고, 해당 위치를 저장하였다.

그리고 같은 문자가 또 한번 등장할 때마다 기존에 저장해 두었던 위치와 비교해보아서 더 작은 위치로 갱신되도록 하였다.

이렇게 하여 문자당 최소 터치 수를 map에 저장해 두면 80 프로는 다 한 것이다!!

이제 targets을 순회하면서 해당 문자의 최소 터치 수가 저장된 map에서 값을 가져와 count시키고, 

만약 해당 문자가 map에 존재하지 않는다면, 작성할 수 없는 문자열이므로, 문제에서 요구한 것처럼 count를 -1로 하고, 해당 문자열은 넘어가도록 코드를 구현했다.

그리고 한 문자열씩 돌때마다 answer벡터에 count값을 push해주면 끝!

코드는 아래와 같다.

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

using namespace std;

vector<int> solution(vector<string> keymap, vector<string> targets) {
    vector<int> answer;
    
    map<char, int> m1;

	for (int i = 0; i < keymap.size(); i++) {
		for (int j = 0; j < keymap[i].size(); j++) {
			if (m1.find(keymap[i][j]) == m1.end()) {//map에 존재하지 않은 문자면 입력
				m1.insert(pair<char, int>(keymap[i][j], j+1));
			}
			else {
				if (m1[keymap[i][j]] > j + 1) {
					m1[keymap[i][j]] = j + 1;//더작은 값으로 바꾼다
				}
			}
		}
	}

	int cnt;

	for (int i = 0; i < targets.size(); i++) {
		cnt = 0;
		for (int j = 0; j < targets[i].size(); j++) {
			if (m1.find(targets[i][j]) == m1.end()) {
				cnt = -1;
				break;
			}
			auto temp = targets[i][j];
			cnt += m1[temp];
		}
		answer.push_back(cnt);
	}

    
    return answer;
}

n칸의 벽 중 덧칠해야 할 칸 번호가 적힌 벡터를 참고하여, 한번에 m칸 칠할 수 있는 페인트 롤러를 이용해 최소의 페인트칠 횟수 구하는 문제.

문제의 조건을 보면 section 벡터의 크기가 무조건 1이상이므로, 최소 한번은 칠해야 한다는 점을 기억하자.

section[0]에서 시작해서 한번 칠할 때 section[0]+m-1번 칸 까지는 칠해진다.

그리고 한번 칠했으므로, 칠한 횟수(answer)를 1 증가시켜준다.

temp에 section[0]+m에 대한 값을 저장해두고, for문을 통해 section[1]부터 section의 크기만큼 순회한다.

그래서, 다음 칠해야 할 칸이, 이전에 한번 칠했던 범위에 포함이 되는지를 살펴보고, 포함이 된다면 현재 회차는 넘어가도록 한다.이는 현재 section[i]의 값이 temp보다 작은지를 보면 된다.

만약 현재 section[i]의 값이 temp와 같거나 더 크다면 이전에 칠했을 때, 같이 칠해지지 못한 것이므로, temp를 다시 section[i]+m으로 갱신해주고, 이를 기준으로 한번 더 칠하는 것이므로 answer를 1 증가 시킨다.

위 과정을 모든 section벡터 값에 대해 순회해주면 최소 페인트 칠 횟수를 반환할 수 있다! 

코드는 아래와 같다.

#include <string>
#include <vector>

using namespace std;

int solution(int n, int m, vector<int> section) {
    int answer = 0;
    
    int temp = section[0] + m;
	answer++;
	
	for (int i = 1; i < section.size(); i++) {
		if (section[i] < temp) {//한번 칠한것에 같이 포함이 되면
			continue;//넘어간다
		}
		else {
			temp = section[i] + m;
			answer++;
		}
	}
    
    return answer;
}

이 문제는 배열의 유효범위를 이해하고, 입력으로 받은 문자열에서 한 글자씩 접근하여 장애물(X)이면 해당 이동을 진행하지 않고, 장애물이 아니면 이동을 진행하도록 하는 쉬운 문제였다.

로직을 이해하고 짜는데에는 금방이었는데, 3가지 케이스를 제외하고 모두 실패가 떠서 왜 그런가.. 테스트 케이스 결과를 보니, 처음 start 위치를 찾고 난 후부터는 전혀 이동하지 못하고 그대로 반환되는 것을 확인할 수 있었다.

원인은 너무 단순한 거였는데, string에서 이동 칸 수를 char로 읽어와서 int로 변경하는 과정에, ASCII 형식을 고려하지 않은 채로 static_case를 씌워 단순히 <int>로 형변환 하려고 해서 정확한 숫자값을 읽어오지 못한 것이었따...

char타입을 레퍼런스로 가져와서 const char 포인터에 저장해 준 후 char->int로 바꾸어주는 atoi함수를 통해 쉽게 해결하였다!!

const char *jump_char = &routes[i][2];
		int jump = atoi(jump_char);

전체 코드는 아래와 같다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<string> park, vector<string> routes) {
	vector<int> answer;

	int start_row = 0;
	int start_col = 0;

	bool isbreak = false;

	for (int i = 0; i < park.size(); i++) {//행길이
		for (int j = 0; j < park[i].size(); j++) {//열길이
			if (park[i][j] == 'S') {
				start_row = i;
				start_col = j;
				isbreak = true;
				break;
			}
		}
		if (isbreak) break;
	}

	for (int i = 0; i < routes.size(); i++) {
		const char *jump_char = &routes[i][2];
		int jump = atoi(jump_char);//char를 읽어와 숫자로 변환하는 과정에서 오류가 발생했음. 이렇게 수정하니 해결됨
		switch (routes[i][0])
		{
		case 'N':
			if (start_row - jump >= 0){
				bool flag = false;
				for (int j = 1; j <= jump; j++) {
					if (park[start_row - j][start_col] == 'X') {
						flag = true;
						break;
					}
				}
				if (!flag) {
					start_row -= jump;
				}
			}
			break;
			
		case 'S':
			if (start_row + jump < park.size()) {
				bool flag = false;
				for (int j = 1; j <= jump; j++) {
					if (park[start_row + j][start_col] == 'X') {
						flag = true;
						break;
					}
				}
				if (!flag) {
					start_row += jump;
				}
			}
			break;

		case 'W':
			if (start_col - jump >= 0) {
				bool flag = false;
				for (int j = 1; j <= jump; j++) {
					if (park[start_row][start_col-j] == 'X') {
						flag = true;
						break;
					}
				}
				if (!flag) {
					start_col -= jump;
				}
			}
			break;

		case 'E':
			if (start_col + jump < park[0].size()) {
				bool flag = false;
				for (int j = 1; j <= jump; j++) {
					if (park[start_row][start_col + j] == 'X') {
						flag = true;
						break;
					}
				}
				if (!flag) {
					start_col += jump;
				}
			}
			break;

		default:
			break;
		}
	}

	answer.push_back(start_row);
	answer.push_back(start_col);

	return answer;
}

앞의 달리기 경주를 풀고 난 뒤 이 문제를 보니, 어떻게 풀어야 할지 바로 감이 잡혔다.

이 문제 역시 map을 사용하여 해결할 수 있다.

string과 int가 짝을 이루고, 주어진 string을 통해 탐색하는 과정이 필요하다면 map을 사용할 것!

풀이는 아래와 같다.

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

using namespace std;

vector<int> solution(vector<string> name, vector<int> yearning, vector<vector<string>> photo) {
    vector<int> answer;
    
    
	map <string, int> m1;

	for (int i = 0; i < name.size(); i++) {
		m1[name[i]] = yearning[i];
	}

	for (int i = 0; i < photo.size(); i++) {
		int cnt = 0;
		for (int j = 0; j < photo[i].size(); j++) {
			cnt += m1[photo[i][j]];
		}
		answer.push_back(cnt);
	}
    
    return answer;
}

string을 인덱스로 갖는 map을 하나 생성하여 주어진 값들을 대입해주었다.

그리고 photo를 한 줄 단위로 읽으며 값을 카운트 해주면 된다!

이 문제를 풀려고 했을 당시 처음엔 callings vector에 저장되어 있는 이름들을 players에서 찾아 내야 한다는 생각은 했으나, 이름과 등수를 바로바로 매치할 수 있는 방법이 떠오르지 않아서.. 단순히 while/for 반복문으로 하나씩 접근할 수 밖에 없었다.

그 코드는 아래와 같았고, 역시 몇개의 case에서 시간초과 문제가 발생하였다.

#include <string>
#include <vector>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {

	int sz = players.size();
	int cnt = 1;

	for (int i=0; i<callings.size(); i++){
		string temp = callings[i];

		if (i < callings.size() - 1 && temp == callings[i + 1]) {
			cnt++;
			continue;
		}

		for (int j = 0; j < sz; j++) {
			if (players[j] == temp) {
				int target = j - cnt;
				while (target < j) {
					swap(players[j], players[j - 1]);
					j--;
				}
				cnt = 1;
				break;
			}
		}
	}
	return players;
}

시간 초과가 발생한 부분은 [players를 일일이 탐색하는 부분]+[vector의 위치를 swap하는 부분] 이다. 

vector도 제법 빠른 자료구조라 생각했는데, 자리를 바꾸는 과정은 역시 O(N)이다.

이 문제의 핵심은 map을 사용하는 것이었다!!!!

map을 총 두개 사용하여 해결하였는데, 하나는 등수(int)를 기준으로 이름을 저장한 것과, 하나는 이름(string)을 기준으로 등수를 저장한 것이다.

이렇게 하면 반복문을 돌면서 callings에 있는 이름을 일일이 찾지 않고, 이름 자체를 인덱스로써 활용하여 현재 등수를 알아 낼 수 있다!!

해결한 코드는 아래와 같다.

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

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
	//답 : vector라는 자료구조를 사용하는 것보다 map으로 정렬과정을 거친 후 vector에는 최종 결과 삽입만 하기.

	vector<string> answer;

	int sz = players.size();
	map <int, string> m1;//등수 별 이름 기억해두기
	map <string, int> m2;//이름 별 등수 기억해두기

	for (int i = 0; i<players.size(); i++) {
		m1[i] = players[i];
		m2[players[i]] = i;
	}

	for (int i = 0; i < callings.size(); i++) {
		string temp = callings[i];
		int tempIdx = m2[temp];
		m1[tempIdx] = m1[tempIdx - 1];//swap과정
		m1[tempIdx - 1] = temp;
		m2[temp] = tempIdx - 1;
		m2[m1[tempIdx]] = tempIdx;

	}

	for (auto temp : m1) {
		answer.push_back(temp.second);//m1의 두번째 요소(이름)들을 넣는다.
	}

	return answer;
}

그 결과 map을 활용해서 탐색 시간을 확실히 줄일 수 있었다!!

반환하고자 하는 것은 vector이므로, m1에 등수대로 적힌 이름들을 answer에 push_back하였고 이를 반환하도록 하였다.