단어 목록이 주어졌을 때, 표준 QWERTY 키보드 배열에서 한 줄에 있는 알파벳만으로 입력할 수 있는 단어들을 찾는 문제입니다.
예를 들어, 입력이 ["hello", "world", "mom", "dad", "try", "type", "tom"]이라면 출력은 ["dad", "try", "type"]이 됩니다. 'dad'는 키보드 두 번째 줄(a, s, d, f...)의 문자로만, 'try'와 'type'은 첫 번째 줄(q, w, e, r...)의 문자로만 구성되어 있기 때문입니다.
문제 해결 접근 방법
이 문제는 다음 단계를 통해 해결할 수 있습니다:
- 결과를 저장할 output 배열을 정의합니다.
- 각 알파벳이 키보드의 몇 번째 줄에 위치하는지 저장하는 charToRowMap 해시 맵을 정의합니다. 즉, {문자, 줄 번호} 쌍으로 구성되며, q~p는 1번째 줄, a~l은 2번째 줄, z~m은 3번째 줄에 해당합니다.
- words 배열의 각 단어에 대해 다음을 수행합니다:
- 단어가 비어 있지 않다면 oneRow 플래그를 true로 초기화합니다.
- 첫 번째 문자를 소문자로 변환한 뒤, 해당 문자가 속한 줄 번호를 row 변수에 저장합니다.
- 두 번째 문자부터 마지막 문자까지 반복하면서, 각 문자의 줄 번호가 row와 다르면 oneRow를 false로 설정하고 반복을 종료(break)합니다.
- 반복이 끝난 후 oneRow가 true라면 해당 단어를 output 배열의 끝에 추가합니다.
- 모든 단어 검사가 완료되면 output을 반환합니다.
예제 코드
아래 C++ 구현을 통해 더 자세히 이해할 수 있습니다:
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string> findWords(vector<string>& words) {
vector<string> output;
bool oneRow = true;
unordered_map<char, int> charToRowMap{
{ 'q', 1 }, { 'w', 1 }, { 'e', 1 }, { 'r', 1 }, { 't', 1 }, { 'y', 1 }, { 'u', 1 },
{ 'i', 1 }, { 'o', 1 }, { 'p', 1 }, { 'a', 2 }, { 's', 2 }, { 'd', 2 }, { 'f', 2 }, { 'g', 2 }, { 'h', 2 }, { 'j', 2 }, { 'k', 2 }, { 'l', 2 }, { 'z', 3 }, { 'x', 3 }, { 'c', 3 }, { 'v', 3 }, { 'b', 3 }, { 'n', 3 }, { 'm', 3 }
};
for (auto word : words)
if (!word.empty()) {
oneRow = true;
int row = charToRowMap[tolower(word[0])];
for (int i = 1; i < word.length(); i++)
if (charToRowMap[tolower(word[i])] != row) {
oneRow = false;
break;
}
if (oneRow)
output.push_back(word);
}
return output;
}
};
main(){
Solution ob;
vector<string> v = {"hello","world","mom","dad","try","type","tom"};
print_vector(ob.findWords(v));
}입력
{"hello","world","mom","dad","try","type","tom"}출력
[dad, try, type]
복잡도 분석
각 단어의 모든 문자를 한 번씩만 확인하므로 시간 복잡도는 O(N)입니다(여기서 N은 전체 단어들의 총 문자 수). 해시 맵의 크기는 알파벳 개수로 고정되어 있으므로 추가 공간 복잡도는 O(1)입니다.