책너두 (코딩 인터뷰 완전분석) 9일차 (예제 1.4 ~ 1.9) 배열과 문자열 (2)

메모

면접 문제

1.4 회문 순열

• 주어진 문자열이 회문(palindrome)의 순열인지 아닌지 확인하는 함수를 작성하라. 회문이란 앞으로 읽으나 뒤로 읽으나 같은 단어 혹은구절을 의미하며, 순열이란 문자열을 재배치하는 것을 뜻한다. 회문이 꼭 사전에 등장하는 단어로 제한될 필요는 없다.

public class Solution {
    public static void main(String[] args) {
        String pali = "Rats live on no evil star";
        System.out.println(isPermutationPalindrome(pali));
    }

    public static boolean isPermutationPalindrome(String s) {
        Map<Character, Integer> characterIntegerMap = new HashMap<>();
        for (char c : s.toCharArray()) {
            char lowerCase = Character.toLowerCase(c);
            if (c == ' ') continue;
            characterIntegerMap.put(lowerCase, characterIntegerMap.getOrDefault(lowerCase, 0) + 1);
        }

        int oddCount = 0;
        for (Integer charCount : characterIntegerMap.values()) {
             if (charCount % 2 == 1) ++oddCount;
             if (oddCount > 1) return false;
        }

        return true;
    }
}

• 알파벳에 대해서만 커버한다고 가정
  • toLowerCase 가 커버하는 영역 확인 필요
• 문자열의 캐릭터가 짝수라면 회문 가능
• 문자열의 캐릭터가 홀수이면서 문자열의 캐릭터가 홀수인 갯수가 1 초과이면 회문 순열일 수 없음.

1.5 하나 빼기

• 문자열을 편집하는 방법에는 세 가지 종류가 있다. 문자 삽입, 문자 삭제, 문자 교체. 문자열 두 개가 주어졌을 때, 문자열을 같게 만들기 위한 편집 횟수가 1회 이내인지 확인하는 함수를 작성하라.

public class Solution {
    public static void main(String[] args) {
        System.out.println(isPossibleWithinOneTrial("pale", "ple"));
        System.out.println(isPossibleWithinOneTrial("pales", "pale"));
        System.out.println(isPossibleWithinOneTrial("pale", "bale"));
        System.out.println(isPossibleWithinOneTrial("pale", "bake"));
        System.out.println(isPossibleWithinOneTrial("pppe", "pae"));
    }

    public static boolean isPossibleWithinOneTrial(String s1, String s2) {
        int diffLength = s1.length() - s2.length();
        if (diffLength == 1) {
            return insert(s2, s1);
        }
        if (diffLength == -1) {
            return insert(s1, s2);
        }
        if (diffLength == 0) {
            return exchange(s1, s2);
        }
        return false;
    }

    private static boolean exchange(String s1, String s2) {
        char[] chars1 = s1.toCharArray();
        char[] chars2 = s2.toCharArray();
        int count = 0;
        for (int idx = 0; idx < chars1.length; idx++) {
            if (chars1[idx] != chars2[idx]) {
                count++;
            }
            if (count >= 2) {
                return false;
            }
        }
        return true;
    }

    private static boolean insert(String s1, String s2) {
        int idx1 = 0;
        int idx2 = 0;
        int countOverTwoDiff = 0;

        while (idx1 < s1.length() && idx2 < s2.length()) {
            if (s1.charAt(idx1) != s2.charAt(idx2)) {
                if (countOverTwoDiff >= 2) {
                    return false;
                }
                ++countOverTwoDiff;
                ++idx2;
            } else {
                ++idx1;
                ++idx2;
            }
        }

        return true;
    }
}

• 두 문자열의 길이 차이를 이용해서 다른 함수를 사용
• 교환 함수는 문자가 다른 경우가 1개일 경우에만 true
• 추가 함수는 투포인터를 이용함.
  • 문자가 다를 경우가 1번을 초과할 경우 false

1.6 문자열 압축

• 반복되는 문자의 개수를 세는 방식의 기본적인 문자열 압축 메서드를 작성하라. 예를 들어 문자열 aabccccaaa를 압축하면 a2b1c5a3이 된다. 만약 '압축된 문자열의 길이가 기존 문자열의 길이보다 길다면 기존문자열을 반환해야 한다. 문자열은 대소문자 알파벳(a~z)으로만 이루어져 있다.

1.7 행렬 회전

• 이미지를 표현하는 NXN 행렬이 있다. 이미지의 각 픽셀은 4바이트로 표현된다. 이때, 이미지를 90도 회전시키는 메서드를 작성하라. 행렬을 추가로 사용하지 않고서도 할 수 있겠는가?
• 추가 문제 → MXN 행렬의 90도 회전 → 배열의 사이즈가 달라지므로 인덱스를 잘 고려해야 함.

1.8 0행렬

• MXN 행렬의 한 원소가 0일 경우, 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라.

1.9 문자열 회전

• 한 단어가 다른 문자열에 포함되어 있는지 판별하는 isSubstring이라는 메서드가 있다고 하자. S1과 2의 두 문자열이 주어졌고, 2가 S1을 회전시킨 결과인지 판별하고자 한다(가령 'waterbottle’은 ‘erbottlewat'을 회전시켜 얻을 수 있는 문자열이다). issubstring 메서드를 한 번만 호출해서 판별할 수 있는 코드를 작성하라.