Google Mock Interview #2

제발 이렇게만 나와라..^^

그래도 60%네요..^^

Remove Outer Parenthesis

class Solution {
    public String removeOuterParentheses(String s) {
        String result = "";
        int count = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) - '(' == 0) {
                count++;
            } else {
                count--; 
            }
            
            if (s.charAt(i) - '(' == 0 && count != 1) {
                result += s.charAt(i);
            }
            
            if (s.charAt(i) - ')' == 0 && count != 0) {
                result += s.charAt(i);
            }
        }
        
        return result; 
    }
}

Runtime: 14 ms, faster than 10.39% of Java online submissions for Remove Outermost Parentheses.
Memory Usage: 38.8 MB, less than 85.02% of Java online submissions for Remove Outermost Parentheses.

여기서 삽질을 좀 했네요..
정답이 나왔는데 정답 나온지도 모르고 잘못한줄 알고 괜히 계속보고 있었읍니다..^^
바부팅..☆

근데 런타임 실화냐;;;;
O(n)인데 10%면 죽으라는 소리 아닌가요;;;

제가봤을땐 binary search 함 가야할거 같네요 ==> 근데 생각해보니깐 진짜 전혀 아닌디???? 언제 끝날지 어케알어 이건 binary search가 훨 느릴듯...

class Solution {
    public String removeOuterParentheses(String s) {
        String result = "";
        int count = 0;
        
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) - '(' == 0) {
                count++;
                if (count != 1) {
                    result += '(';
                }
            } else {
                count--; 
                if (count != 0) {
                    result += ')';
                }
            }
        }
        
        return result; 
    }
}

Runtime: 7 ms, faster than 28.61% of Java online submissions for Remove Outermost Parentheses.
Memory Usage: 39.6 MB, less than 16.24% of Java online submissions for Remove Outermost Parentheses.

안에 넣어주는거만으로도 훨씬 빨라지네요

class Solution:
    def removeOuterParentheses(self, S: str) -> str:
        res = ""
        count = 0
        
        for i in S:
            if i == '(':
                count = count + 1
                if count != 1:
                    res = res + '('
            else:
                count = count - 1
                if count != 0:
                    res = res + ')'
        
        return res

Runtime: 32 ms, faster than 94.22% of Python3 online submissions for Remove Outermost Parentheses.
Memory Usage: 14.2 MB, less than 86.08% of Python3 online submissions for Remove Outermost Parentheses.

이선이로 푸니깐 바로 빨라지네요 어이없어;;

==> 자바에서 Stringbuilder 안쓰면 더럽게 느려짐

class Solution {
    public String removeOuterParentheses(String S) {
        
        StringBuilder sb = new StringBuilder();
        int open=0, close=0, start=0;
        for(int i=0; i<S.length(); i++) {
            if(S.charAt(i) == '(') {
                open++;
            } else if(S.charAt(i) == ')') {
                close++;
            }
            if(open==close) {
                sb.append(S.substring(start+1, i));
                start=i+1;
            }
        }
        return sb.toString();
    }
}

Divisor Game

class Solution {
    public boolean divisorGame(int N) {
        return (N % 2 == 0);
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for Divisor Game.
Memory Usage: 36 MB, less than 28.36% of Java online submissions for Divisor Game.

처음에는 1-100까지의 모든 prime수를 잡으려고 했는데 생각해보니깐 2의 배수가 나왔다 --> 마지막 수가 odd면 짐 --> 마지막 고를 수 잇는게 A씨임 --> 그러니 횟수가 짝수면 A씨가 이기고 홀수면 B씨가 이김

이 로직으로 풀었읍니다