[LeetCode # 58, 59, 61] 문제 풀이

# 58. Length of Last Word

주어진 문자열 (문장) 에서 마지막 단어의 길이를 구하는 문제

간단하게 C++ 의 String 내장 메소드 find_last_of / find_last_not_of 를 사용해 문제 해결

 

int lengthOfLastWord(string s) {
	if (s.find_first_not_of(" ") == -1)
		return 0;
	int last = s.find_last_not_of(" ");
	int first = s.substr(0, last).find_last_of(" ");
	return last - first;
}

# 59. Spiral Matrix II

정수 N 이 주어졌을 때, N * N 크기의 Spiral Matrix 를 만드는 문제

 

Spiral Matrix 의 값이 증가하는 방향 순서대로 증가하는 값을 넣어주도록 했다.

 

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

    vector<vector<int>> generateMatrix(int n) {
	vector<vector<int>> ans(n, vector<int>(n, 0));
	int dir = 0, cy = 0, cx = 0;
	int max_val = n * n;
	for (int i = 1; i <= max_val; i++) {
		ans[cy][cx] = i;
		int ny = cy + dy[dir], nx = cx + dx[dir];
		if ((ny < 0 || ny >= n || nx < 0 || nx >= n) || ans[ny][nx] != 0) {
			dir = (dir + 1) % 4;
			ny = cy + dy[dir], nx = cx + dx[dir];
		}
		cy = ny, cx = nx;
	}
	return ans;
}

# 61. Rotate List

List 의 Head 가 주어지고, 정수 k 가 주어졌을 때 k 번만큼 오른쪽으로 회전한 리스트를 구하는 문제

 

처음 생각한 해결 방법은, List 의 tail 부터 탐색해서 해당 node 의 next 링크를 head 로 연결하고 해당 node 를 head 로 변경하는 것이었는데 이 방법은 List 에서 prev link 를 구할 수 없어 구현이 불가했다.

때문에 다시 생각해 낸 방법은, head 부터 끝까지 탐색하면서 각각 node 들이 저장하고 있는 값들을 구하고 그 값을 다시 node 에 순서를 변경해 저장하는 것이었다.

 

ListNode* rotateRight(ListNode* head, int k) {
	int val[501];
	int size = 0;
	for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next) {
		val[size++] = tmp->val;
	}
	if (size <= 1)
		return head;
	k %= size;
	int idx = (size - k) % size;
	for (ListNode* tmp = head; tmp != nullptr; tmp = tmp->next) {
		tmp->val = val[idx];
		idx = (idx + 1) % size;
	}
	return head;
}