[리트코드] 12일차

 

289. Game of Life

 

class Solution {
    public void gameOfLife(int[][] board) {
        List<List<Integer>> needToChange = new ArrayList<>();
        int rows = board.length;
        int cols = board[0].length;

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

        for (int r = 0; r < rows; r++){
            for (int c = 0; c < cols; c++){
                int count = 0;
                for (int d = 0; d < 8; d++){
                    int nextX = r + dx[d];
                    int nextY = c + dy[d];
                    if (((nextX >= 0) && (nextX < rows)) && ((nextY >= 0 )&&(nextY < cols))){
                        if (board[nextX][nextY] == 1){
                            count++;
                        }    
                    }    
                }
                // live cell
                if (board[r][c] == 1){
                    if ((count < 2) || (count > 3)){
                        needToChange.add(Arrays.asList(r, c));
                    }
                }else{ // dead cell
                    if (count == 3){
                        needToChange.add(Arrays.asList(r, c));
                    }
                }
            }
        }
        System.out.println(needToChange.toString());

        for (int i = 0; i < needToChange.size(); i++){
            int x = needToChange.get(i).get(0);
            int y = needToChange.get(i).get(1);

            board[x][y] = (board[x][y] == 1 ? 0 : 1);
        }

        
    }
}

처음에 상태를 바꿀 곳을 찾는다. 이후에 바꿀 곳을 다시 탐색하여 바꾸도록 코드를 작성했다. 이랬더니 2ms 가 나온다...

조금 더 줄일 순 없을까? 생각하면서 공유된 답을 보니 딱히 다르게 풀진 않는 것 같아서 여기서 마무리해본다.

 

383. Ransom Note

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        HashMap<Character, Integer> magazineMap = new HashMap<>();
        for (int i = 0; i < magazine.length(); i++){
            char ch = magazine.charAt(i);
            magazineMap.put(ch, magazineMap.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < ransomNote.length(); i++){
            char ch = ransomNote.charAt(i);
            if(!magazineMap.containsKey(ch)){
                return false;
            }
            int magazineCount = magazineMap.get(ch);
            if (magazineCount<1){
                return false;
            }
            magazineMap.replace(ch, magazineCount-1);
        }
        return true;
    }
}

처음에는 매거진 내용을 다 넣고 1개씩 빼면서 확인하는 방식으로 풀었다.

근데 너무 느리게 나와서.. 다른 방법을 찾아야했다.

다른 곳들 답안들을 바탕으로 테스트 해본 결과 해시맵을 쓰는 순간 너무 오랜 시간이 걸린다. 아무래도 배열보다 오래 걸릴 수 밖에 없다. 

동적으로 크기 할당하고, 또 key 로 계산도 하고..

그래서 시간을 줄이고 싶다면 배열을 사용해서 해결하면 되는 것이었다.