Problem

• 문제 링크

주어진 숫자를 뒤집으면 됩니다.

Solution

평범하게 1 의 자릿수부터 더해가면 됩니다.

한 가지 주의할 점은 res 값이 int 의 범위를 벗어날 수 있기 때문에 long 타입으로 선언 후에 나중에 바꿔주어야 합니다.

Java Code

class Solution {
    public int reverse(int x) {
        long res = 0;

        while (x != 0) {
            res *= 10;
            res += x % 10;
            x /= 10;
        }

        if (-Integer.MAX_VALUE <= res && res <= Integer.MAX_VALUE) {
            return (int) res;
        } else {
            return 0;
        }
    }
}

Problem

• 문제 링크

주어지는 숫자보다 작은 모든 소수의 개수를 구하는 문제입니다.

Solution

에라토스테네스의 체를 사용하여 소수를 미리 구해두면 O(n) 시간복잡도로 구할 수 있습니다.

2의 곱셉, 3의 곱셈, 4의 곱셉.. 전부 isNotPrime 으로 체크한 뒤에

false 인 숫자들만 카운팅하면 됩니다.

+) 2020. 01. 03

Discuss 보고 개선한 코드를 추가했습니다.

count = n / 2 로 시작하는 이유는 2 를 제외한 짝수는 소수가 될 수 없기 때문입니다.

2 의 배수는 어차피 셀 필요가 없기 때문에 처음부터 제외하고 3 부터 홀수들의 배수만 체크해서 소수가 아닌 값들을 제외합니다.

Java Code

class Solution {
    public int countPrimes(int n) {
        boolean[] isNotPrime = new boolean[n];
        int count = 0;

        for (int i = 2; i * i < n; i++) {
            if (isNotPrime[i]) continue;

            for (int j = 2; i * j < n; j++) {
                isNotPrime[i * j] = true;
            }
        }

        for (int i = 2; i < n; i++) {
            if (!isNotPrime[i]) {
                count++;
            }
        }

        return count;
    }
}

// Discuss 참고 개선
class Solution {
    public int countPrimes(int n) {
        if (n < 3) return 0;

        boolean[] isNotPrime = new boolean[n];
        int count = n / 2;

        for (int i = 3; i * i < n; i += 2) {
            for (int j = i * i; j < n; j += i * 2) {
                if (isNotPrime[j]) continue;
                count--;
                isNotPrime[j] = true;
            }
        }

        return count;
    }
}

Problem

• 문제 링크

주어지는 숫자 x 의 제곱근을 구하는 문제입니다.

만약 8 의 제곱근처럼 정수로 나누어 떨어지지 않으면 소수점 자리를 전부 버립니다.

Solution

1 ~ x 까지를 범위로 잡고 Binary Search 를 실시합니다.

중간값 mid 가 정답이 되는 조건은 mid * mid <= x < (mid + 1) * (mid + 1) 이 될 때입니다.

한가지 주의할 점은 mid * mid 가 너무 큰 수가 되어버리면 int 범위를 벗어나서 음수가 될 수 있습니다.

따라서 안전하게 양변을 나눈 값으로 비교합니다.

Java Code

class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;

        int lo = 1, hi = x;

        while (lo <= hi) {
            int mid = lo + (hi - lo)/2;

            if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {
                return mid;
            } else if (mid <= x / mid) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }

        return lo;
    }
}

Problem

• 문제 링크

문자열 두개가 주어졌을 때 haystack 안에 needle 문자열의 위치를 구하는 문제입니다.

Java 의 indexOf 함수를 직접 구현한다고 생각하면 됩니다.

Solution

단순하게 비교하면 됩니다.

substring 을 쓰면 좀더 쉬우나, 문제의 취지가 이것도 허용하지 않는거라면 직접 charAt 으로 일일히 비교하거나 substring 처럼 문자열을 만들어서 비교하면 됩니다.

Java Code

// using substring
class Solution {
    public int strStr(String haystack, String needle) {
        int len = needle.length();

        for (int i = 0; i < haystack.length() - len + 1; i++) {
            String s = haystack.substring(i, i + len);

            if (s.equals(needle)) {
                return i;
            }
        }

        return -1;
    }
}

// normal
class Solution {
    public int strStr(String haystack, String needle) {
        int len = needle.length();

        for (int i = 0; i < haystack.length() - len + 1; i++) {
            boolean isEqual = true;

            for (int j = 0; j < len; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    isEqual = false;
                }
            }

            if (isEqual) {
                return i;
            }
        }

        return -1;
    }
}

Problem

• 문제 링크

주어진 문자열들의 공통되면서 가장 긴 prefix 를 구하는 문제입니다.

Solution

단순하게 이중 for 문으로 구하면 됩니다.

strs 배열의 첫 번째 문자열을 기준으로 하여 나머지 문자열들과 각 인덱스의 문자가 일치하는 지 확인합니다.

만약 전부 일치하여 for 문이 통과되면 해당 문자를 StringBuilder 에 추가합니다.

나머지 문자열들 중 하나라도 일치하지 않는다면 가장 긴 공통 prefix 에 해당하지 않기 때문에 바로 리턴하면 됩니다.

Java Code

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);

            for (String str : strs) {
                if (str.length() <= i || c != str.charAt(i)) {
                    return sb.toString();
                }
            }

            sb.append(c);
        }


        return sb.toString();
    }
}

Problem

• 문제 링크

주어진 문자열이 Palindrome 을 이루는지 확인하는 문제입니다.

대신 숫자, 알파벳 소문자/대문자 만 비교합니다.

Solution

처음에는 정규식으로 필요없는 모든 문자를 제거한 후 중간지점부터 양쪽으로 인덱스를 이동시키며 비교하는 방법을 했습니다.

제출하니 속도가 너무 안나와서 정석대로 양 끝부터 차례대로 비교해가는 방식으로 변경했습니다.

숫자나 소문자/대문자 여부는 Character.isLetterOrDigit 메소드로 확인하였고 다른 문자인 경우 인덱스를 이동시킵니다.

Java Code

// 직접 비교
class Solution {
    public boolean isPalindrome(String s) {       
        int i = 0, j = s.length() - 1;
        char[] chars = s.toLowerCase().toCharArray();

        while (i <= j) {
            if (!Character.isLetterOrDigit(chars[i])) {
                i++;
            } else if (!Character.isLetterOrDigit(chars[j])) {
                j--;
            } else if(chars[i++] != chars[j--]) {
                return false;
            }
        }

        return true;
    }
}

// 정규식
class Solution {
    public boolean isPalindrome(String s) {
        if (s.length() == 0) return true;

        // 정규식으로 다른 문자 제거
        s = s.replaceAll("[^0-9a-zA-Z]", "").toLowerCase();

        // 중간값부터 비교
        int toLeft = s.length() / 2;
        int toRight = s.length() / 2;

        // 짝수면 toLeft 를 하나 빼줌
        if (s.length() % 2 == 0) {
            toLeft -= 1;
        }

        while (toLeft >= 0) {
            if (s.charAt(toLeft--) != s.charAt(toRight++)) {
                return false;
            }
        }

        return true;
    }
}

Problem

• 문제 링크

주어진 문자열의 괄호쌍이 옳게 되어있는지 판단하는 문제입니다.

Solution

여는 괄호가 있으면 닫는 괄호가 반드시 존재해야 하고 ( 괄호가 } 나 ] 괄호와 매칭 될 수 없습니다.

스택을 이용하여 여는 괄호가 나오면 그대로 Stack 에 넣어주고, 닫는 괄호가 나오면 Stack.peek() 값과 비교하여 쌍이 제대로 맞는지 확인하면 됩니다.

단순하게 switch 문이나 if - else 문으로 짤수도 있지만 HashMap 을 사용하면 반복되는 로직을 어느정도 줄일 수 있습니다.

key = 닫는 괄호, value = 여는 괄호로 저장해두고 닫는 괄호가 주어졌을 때 stack 의 가장 최근 값이 여는 괄호와 일치하는 지 바로 비교할 수 있습니다.

Java Code

class Solution {
    public boolean isValid(String s) {
        Map<Character, Character> map = Map.of(')', '(', '}', '{', ']', '[');
        Stack<Character> stack = new Stack<>();

        for (Character c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else if (stack.isEmpty() || stack.pop() != map.get(c)) {
                return false;
            }
        }

        return stack.isEmpty();
    }
}

Problem

• 문제 링크

주어진 리스트 노드가 Palindrome 을 만족하는 지 확인하는 문제입니다.

O(n) time and O(1) space 에 해결하라는 조건이 있습니다.

Solution

추가 공간복잡도를 많이 사용하면 안되기 때문에 리스트 노드를 직접 조작해야 합니다.

원래는 리스트 노드 전체를 뒤집은 새 리스트 노드를 만들어 비교하려 했으나 이러면 O(n) 공간복잡도를 사용하게 됩니다.

어쩔 수 없이 직접 중간 지점을 찾아서 뒤집은 후에 직접 비교하면 됩니다.

주의할 점은 전체 길이가 홀수일 때 정가운데 있는 숫자는 비교할 필요가 없으므로 slow 를 한칸 더 이동시키는 것과 비교하는 while (head != null) 대신 while (tail != null) 값을 사용해야 하는 겁니다.

Java Code

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;

        // slow 를 중간 지점까지 이동
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }

        // 전체 길이가 홀수면 한칸 더 이동 (가운데 값은 비교할 필요 없음)
        if (fast != null) slow = slow.next;

        // 중간부터 마지막까지 노드 순서 뒤집기
        ListNode tail = reverse(slow);

        while (tail != null) {
            if (head.val != tail.val) {
                return false;
            }

            head = head.next;
            tail = tail.next;
        }

        return true;
    }

    private ListNode reverse(ListNode node) {
        ListNode tail = null;

        while (node != null) {
            ListNode next = node.next;
            node.next = tail;
            tail = node;
            node = next;
        }

        return tail;
    }
}