뚝딱뚝딱

이 문제는 배열의 유효범위를 이해하고, 입력으로 받은 문자열에서 한 글자씩 접근하여 장애물(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하였고 이를 반환하도록 하였다.