500. Keyboard Row

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

ROUTINE-STUDY/Algorithm

 

문제 출처

Longest Substring Without Repeating Characters - LeetCode

 

[문제 설명]

문자열 배열이 주어졌을 때, 키보드 가로 한줄로만 이뤄진 문자로 이루어진 배열을 구하시오.

예시에 Alaska와 Dad는 키보드 가운데 줄 asdfghjkl을 이용해서만 작성 가능.

[처음 생각한 접근 방법]

1.키보드 각 줄을 character 형식으로 set에 저장해놓는다.

2.주어진 단어의 첫번째 문자를 뽑습니다.

3.각 키보드 줄을 저장한 셋에 뽑은 문자가 포함되는지 확인합니다.

4.있을 경우 두번째 글자부터 마지막 글자까지 그 키보드 줄의 포함되는지 확인합니다.

5.포함되면 리스트에 더해줍니다.

예시) 주어진 문자열이 Alaska일 때,

set1 = q,w,e,r,t,y,u,i,o,p

set2 = a,s,d,f,g,h,j,k,l

set3 = z,x,c,v,b,n,m

Alaska의 첫번째 문자 A를 뽑음.

set1에 A가 없음. -> set2로 넘어감.

set2에 A가 있음.

남은 문자 laska가 set2에 있나 확인함.

전부 있으므로 Alaska는 가능.

[내 코드]

class Solution {
    public String[] findWords(String[] words) {
        List<String> answer = new ArrayList<>();
        final String[] keyboardArray = new String[]{"qwertyuiop", "asdfghjkl","zxcvbnm"};

        //키보드 각 줄을 set으로 만들고 그것을 담을 list를 만듬.
        List<Set<Character>> list = new ArrayList<>();      
        for (int i = 0; i < keyboardArray.length; i++) {
            Set<Character> set = new HashSet<>();
            for (char c : keyboardArray[i].toCharArray()) {
                set.add(c);
            }
            list.add(set);
        }

        // 모두 일치하면 리스트에 담아줌.
        for (String word : words) {
            boolean haveToAdd = false;
            String temp = word.toLowerCase();
            for (Set set : list) {
                // 문자열 하나의 문자를 list에 있는 set들과 비교함
                if (set.contains(temp.charAt(0))) {
                    // 같은 set이 있으면 해당 문자열에 있는 모든 문자를 그 set과 비교함.
                    haveToAdd = isAllContains(temp,set);
                }
            }
            if (haveToAdd) answer.add(word);
        }

        String[] strArray = new String[answer.size()];

        return answer.toArray(strArray);
    }

    public boolean isAllContains(String word, Set<Character> set) {
        for (int i = 1; i < word.length(); i++) {
            if (!set.contains(word.charAt(i))) return false;
        }
        return true;
    }
}

[리트코드 답안]

Java 1 ms solution. Beats 100%. No Maps or Sets, still O(1) lookups. - LeetCode Discuss

// Maps each character to the row in the keyboard in which it occurs.
private int[] map = {2,3,3,2,1,2,2,2,1,2,2,2,3,3,1,1,1,1,2,1,1,3,1,3,1,3};

public String[] findWords(String[] words) {

    String[] w = new String[words.length];    // Store filtered words
    int index = 0;                            // Where to insert the filtered words
    for (String s: words)                    // for each word in words
        if (checkWord(s.toLowerCase()))        // convert it to lowercase and check if all char
            w[index++] = s;                    // occurs in the same row, if it does, add it
    return Arrays.copyOfRange(w, 0, index);    // Simply return a copy of the array from 0
}                                            // index

private boolean checkWord(String word){        // Check if all chars in the word belong in the
    int row = map[word.charAt(0)-'a'];        // same row. Check first chars row
    for (char c: word.toCharArray()){        // For all the chars in the word
        if (map[c-'a'] != row)                // if that char belongs to a different row,
            return false;                    // return false
    }
    return true;                            // All chars in same row, return true.
}

진짜 재밌는 답안 같다. 각 알파벳에 따라 몇번째 줄에 있는지 map 배열을 만들어준 후에 체크하는 방법.
a는 2번째 줄이므로 2,
b는 3번째 줄이므로 3,
c도 3번째 줄이므로 3,
d는 2번째 줄이므로 2,
-> 2,3,3,2,....,1,3
아주 재밌는 방법 같다. set도 필요 없고.

 

[스터디하면서 수정한 코드]
첫번째 방법과 똑같은데 set을 사용하지 않았습니다.
저는 HashSet을 사용하면 검색이 빠르므로 당연히 위에 코드가 빠를 거라 생각했지만, 실제로 짜보니 아래 코드가 더 길었습니다.
set을 만드는 시간과 list를 만드는 시간 등 때문에 오래 걸린 게 아닐까 싶습니다.

class Solution {
    public String[] findWords(String[] words) {
        List<String> answer = new ArrayList<>();
        final String[] keyboardArray = new String[]{"qwertyuiop", "asdfghjkl","zxcvbnm"};

        for (String word : words) {
            boolean haveToAdd = false;
            String temp = word.toLowerCase();
            for (String keyboardRow : keyboardArray) {
                if (keyboardRow.contains(String.valueOf(temp.charAt(0)))) {
                    haveToAdd = isAllContains(temp,keyboardRow);
                }
            }
            if (haveToAdd) answer.add(word);
        }

        return answer.toArray(new String[answer.size()]);
    }

    public boolean isAllContains(String word, String keyboardRow) {
        for (int i = 1; i < word.length(); i++) {
            if (!keyboardRow.contains(String.valueOf(word.charAt(i)))) return false;
        }

        return true;
    }
}