Mock Interview: Google #4

런타임 진짜 그진데.. 왜이런거죠

Height Checker

class Solution {
    public int heightChecker(int[] heights) {
        int[] target = heights.clone();
        Arrays.sort(target);
        int count = 0;
        for (int i = 0; i < heights.length; i++) {
            if (heights[i] != target[i]) {
                count++;
            }
        }
        
        return count;
    }
}

Runtime: 1 ms, faster than 75.67% of Java online submissions for Height Checker.
Memory Usage: 39.1 MB, less than 6.56% of Java online submissions for Height Checker.

이거 푸는데 단 3분 걸려서

역쉬,,,ㅎ 나는 알고의 신인것인가,,ㅎ
이거이거 10분안에 끝나는거 아냐?^__^

했지만..^^...

class Solution {
    public int heightChecker(int[] heights) {
        int[] heightToFreq = new int[101];
        
        for (int height : heights) {
            heightToFreq[height]++;
        }
        
        int result = 0;
        int curHeight = 0;
        
        for (int i = 0; i < heights.length; i++) {
            while (heightToFreq[curHeight] == 0) {
                curHeight++;
            }
            
            if (curHeight != heights[i]) {
                result++;
            }
            heightToFreq[curHeight]--;
        }
        
        return result;
    }
}

Long Pressed Name

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int[] c = new int[26];
        
        for (int i = 0; i < typed.length(); i++) {
            c[typed.charAt(i) - 'a']++;
        }
        
        for (int j = 0; j < name.length(); j++) {
            if (c[name.charAt(j) - 'a'] == 0) {
                return false;
            } else {
                c[name.charAt(j) - 'a']--;
            }
        }
        
        return true; 
    }
}

75 / 94 test cases passed

문제를 잘못 읽어 dp를 쓰려고 했으나 순서를 고려해야 한다는 것을 깨달음..

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        Queue<Character> n = new LinkedList<Character>();
        Queue<Character> t = new LinkedList<Character>();
        
        for (int i = 0; i < name.length(); i++) {
            n.add(name.charAt(i));
        }
        
        for (int j = 0; j < typed.length(); j++) {
            t.add(typed.charAt(j));
        }
        
        while (! n.isEmpty() && ! t.isEmpty()) {
            if (n.peek() == t.peek()) {
                n.remove();
                t.remove();
            } else {
                t.remove();
            }
        }
        
        return n.isEmpty();
    }
}

87 / 94 test cases passed.
요즘에 꽂힌 queue..
이건 끝에 댕글거리거나 중간에 새로운 글자가 들어오면 무시한다는 큰 단점이 있음..

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        Queue<Character> n = new LinkedList<Character>();
        Queue<Character> t = new LinkedList<Character>();
        
        for (int i = 0; i < name.length(); i++) {
            n.add(name.charAt(i));
        }
        
        for (int j = 0; j < typed.length(); j++) {
            t.add(typed.charAt(j));
        }
        
        while (! n.isEmpty() && ! t.isEmpty()) {
            if (n.peek() == t.peek()) {
                int cur = n.peek();
                int nnum = 0;
                int tnum = 0;
                
                while (! n.isEmpty() && n.peek() == cur) {
                    n.remove();
                    nnum++;
                }
                
                while (! t.isEmpty() && t.peek() == cur) {
                    t.remove();
                    tnum++;
                }
                
                if (tnum < nnum) {
                    return false; 
                }
            } else {
                return false; 
            }
        }
        
        
        return (n.isEmpty() && t.isEmpty());
    }
}

Runtime: 4 ms, faster than 6.87% of Java online submissions for Long Pressed Name.
Memory Usage: 39.2 MB, less than 5.11% of Java online submissions for Long Pressed Name.

드러운 코드 & 노답 런타임..^^
그래도 풀리긴 해서 다행입니다..
two pointer을 이용하려고 while loop 냅다 던져서 몇개씩 있는지 세줬어요
중간에 잡것들 들어오면 냅다 버리기~~

class Solution {
    public boolean isLongPressedName(String name, String typed) {

        // two pointers to the "name" and "typed" string respectively
        int np = 0, tp = 0;
        // convert the string to array of chars, for ease of processing later.
        char[] name_chars = name.toCharArray();
        char[] typed_chars = typed.toCharArray();

        // advance two pointers, until we exhaust one of the strings
        while (np < name_chars.length && tp < typed_chars.length) {
            if (name_chars[np] == typed_chars[tp]) {
                np += 1;
                tp += 1;
            } else if (tp >= 1 && typed_chars[tp] == typed_chars[tp - 1]) {
                tp += 1;
            } else {
                return false;
            }
        }

        // if there is still some characters left *unmatched* in the origin string,
        // then we don't have a match.
        // e.g. name = "abc" typed = "aabb"
        if (np != name_chars.length) {
            return false;
        } else {
            // In the case that there are some redundant characters left in typed
            // we could still have a match.
            // e.g. name = "abc" typed = "abccccc"
            while (tp < typed_chars.length) {
                if (typed_chars[tp] != typed_chars[tp - 1])
                    return false;
                tp += 1;
            }
        }

        // both strings have been consumed.
        return true;
    }
}

two pointer의 더 깔끔한 ver 루션이
윗부분은 같은데 마지막에 while (tp < typed_chars.length)부분이 제꺼보다 30배 깔끔하네요^^

Runtime: 1 ms, faster than 48.56% of Java online submissions for Long Pressed Name.
Memory Usage: 38.5 MB, less than 17.73% of Java online submissions for Long Pressed Name.