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;
    }
}

Problem

• 문제 링크

두 개의 배열 nums1, nums2 를 nums1 에 하나로 합치는 문제입니다.

두 배열은 이미 정렬되어있고 합쳐진 nums1 도 정렬되어야 합니다.

nums1 은 nums2 의 길이인 n 만큼의 추가 공간이 있으며 해당 공간은 0 으로 채워져 있습니다.

Solution

단순하게 비교해서 넣으면 되는 문제입니다.

이렇게 추가 공간 없이 in place 로 구현해야 하는 문제는 새로 바뀐 값이 이후 로직에 영향을 주면 안됩니다.

따라서 배열의 뒤부터 비교해가며 넣어줍니다.

i 또는 j 가 0 이 되고 나면 나머지 하나가 0 이 될때까지 배열을 채워야 합니다.

i 는 이미 배열에 채워져 있기 때문에 j 가 0 이 될 때까지만 값을 넣어주면 됩니다

Java Code

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m + n - 1;
        int i = m - 1;
        int j = n - 1;

        while (i >= 0 && j >= 0) {
            if (nums1[i] < nums2[j]) {
                nums1[index--] = nums2[j--];
            } else {
                nums1[index--] = nums1[i--];
            }
        }

        while (j >= 0) {
            nums1[index--] = nums2[j--];
        }
    }
}

Problem

• 문제 링크

주어진 비트를 뒤집으면 됩니다.

Solution

비트 전체를 순회하면서 1 과 AND 연산을 반복합니다.

n 의 가장 오른쪽에 있는 값이 res 의 가장 왼쪽에 가야 하므로 res 는 0 부터 왼쪽 쉬프트, n 은 오른쪽 쉬프트를 반복하며 계속 비교하면 됩니다.

Java Code

public class Solution {
    public int reverseBits(int n) {
        int res = 0;

        for (int i = 0; i < 32; i++) {
            res <<= 1;
            res += n & 1;
            n >>= 1;
        }

        return res;
    }
}

// 이건 꼼수
public class Solution {
    public int reverseBits(int n) {
        return Integer.reverse(n);
    }
}