[자료구조] 01. 배열과 문자열

참고: http://www.yes24.com/Product/Goods/7434347?Acode=101

코딩인터뷰 완전분석

해당 문제들은 위 책에서 출제된 문제들이고, 처음엔 직접 풀어본 뒤 뒷장의 풀이를 보면서 피드백 한 내용입니다.

 

---

1.1 문자열에 포함된 문자들이 전부 유일한지를 검사하는 알고리즘을 구현하라. 다른 자료구조를 사용할 수 없는 상황이라면 어떻게 하겠는가?

 

- 먼저 주어진 문자열이 ASCII 문자열인지, 유니코드 문자열인지 질문한다.

참고: https://ko.wikipedia.org/wiki/ASCII

ASCII - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/%EC%9C%A0%EB%8B%88%EC%BD%94%EB%93%9C

유니코드 - 위키백과, 우리 모두의 백과사전

 

- 문자열의 길이가 문자 집합 크기보다 클 경우, 바로 false를 반환하도록 한다.

예) ASCII 코드 문자열인 경우, 문자 집합의 크기가 128개이므로, 문자열의 길이가 128개를 넘으면 중복이 존재한다.

 

- 코드

public class Main {
    public static void main(String[] args) {
        String str = "ABcDEFAAAA";
        Solution solution = new Solution();
        System.out.println("solution.checkDuplication(str) : " + solution.checkDuplication(str));
    }
}

class Solution {
    public boolean checkDuplication(String str) {
        // ASCII 문자열인 경우 문자의 갯수가 128개이므로, 그 이상의 길이를 가진 문자열의 경우 중복이
        if(str.length() > 128) {
            return true;
        }

        // ASCII 문자열인 경우 문자의 갯수가 128개이므로 128개의 배열을 생성한다.
        boolean[] checked = new boolean[128];
        for(int i=0; i<str.length(); i++) {
            int val = str.charAt(i);
            if(checked[val]) {
                return true;
            }
            checked[val] = true;
        }

        return false;
    }
}

 

 

 

---

1.2 널(NULL) 문자로 끝나는 문자열을 뒤집는 reverse(char* str) 함수를 C나 C++로 구현하라.

1.3 문자열 두 개를 입력으로 받아 그 중 하나가 다른 하나의 순열인지 판별하는 메서드를 작성하라.

 

순열 : 문자열에 사용된 문자의 종류와 갯수가 같지만 순서가 다른 것.

 

이 문제도 마찬가지로 확인해야할 사항들이 있다.

- 대소문자 구별을 따져야 하는지.

- 공백은 어떻게 처리해야 하는지.

 

대소문자 구별을 하지 않고, 공백을 하나의 문자로 처리한다면 아래 코드와 같이 작성할 수 있다.

 

- 두 문자열을 정렬하여 비교하는 방법

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        String str = "abbcccdddd";
        String str2 = "dabccbcddd";
        Solution solution = new Solution();
        System.out.println("solution.checkArray(str, str2) : " + solution.checkArray(str, str2));
    }
}

class Solution {
    public boolean checkArray(String str, String str2) {
        if(str.length() != str2.length()) {
            return false;
        }

        char[] strArr = str.toCharArray();
        char[] strArr2 = str2.toCharArray();

        Arrays.sort(strArr);
        Arrays.sort(strArr2);

        for(int i=0; i<strArr.length; i++) {
            if(!Character.toString(strArr[i]).equals(Character.toString(strArr2[i]))) {
                return false;
            }
        }

        return true;
    }
}

 

 

---

1.4 주어진 문자열 내의 모든 공백을 '%20'으로 바꾸는 메서드를 작성하라. 문자열 끝에 추가로 필요한 문자들을 더할 수 있는 충분한 공간이 있다고 가정하라. 그리고 공백을 포함하는 문자열의 길이도 함께 주어진다고 가정하라.(주의: Java로 구현한다면, 문자 배열을 사용하여 필요한 연산을 각 문자에 바로 적용할 수 있도록 하라.)

예)

입력 : "Mr John Smith     ", 13

출력 : "Mr%20John%20Smith"

 

문자열을 char 배열로 바꾼 뒤, 문자 하나씩 비교하면서 공백일 경우 isBlank 값을 true로 변환한다.

다음 차례의 문자가 공백이 아니고 isBlank가 true이면 '%20'을 추가한다.

public class Main {
    public static void main(String[] args) {
        String str = "Mr John Smith     ";
        Solution solution = new Solution();
        System.out.println("solution.changeBlank(str) : " + solution.changeBlank(str));
    }
}

class Solution {
    public String changeBlank(String str) {
        StringBuffer answer = new StringBuffer();
        char[] strArr = str.toCharArray();
        boolean isBlank = false;

        for(int i=0; i<strArr.length; i++) {
            if(strArr[i] == ' ') {
                if(isBlank) {
                    continue;
                }
                isBlank = true;
            } else {
                if(isBlank) {
                    answer.append("%20");
                }
                isBlank = false;
                answer.append(strArr[i]);
            }
        }
        return answer.toString();
    }
}

 

 

 

---

1.5 같은 문자가 연속으로 반복될 경우, 그 횟수를 사용해 문자열을 압축하는 메서드를 구현하라. 가령 압축해야 할 문자열이 aabccccccccaaa라면 a2b1c8a3과 같이 압축되어야 한다. 압축 결과로 만들어지는 문자열이 원래 문자열보다 짧아지지 않는 경우, 이 메서드는 원래 문자열을 그대로 반환해야 한다.

 

이 문제도 마찬가지로 문자열을 Char 배열로 변환했다.

for문을 이용해 순환할 때, index가 1부터 시작하도록 해서, 

이전 문자와 현재 문자를 비교해서 같으면 카운트를 증가시키고,

다르면 '이전 문자 + 카운트' 를 newStr 에 추가한다.

 

 

public class Main {
    public static void main(String[] args) {
        String str = "aabccccccccaaa";
        Solution solution = new Solution();
        System.out.println("solution.compressStr(str) : " + solution.compressStr(str));     // 결과 값 : a2b1c8a3
    }
}

class Solution {
    public String compressStr(String str) {
        if(str.length() == 0) {
            return "";
        }

        char[] strArr = str.toCharArray();

        String newStr = "";
        int cnt = 1;            // 연속되는 문자 갯수

        for(int i=1; i<strArr.length; i++) {
            if(strArr[i] == strArr[i-1]) {
                cnt++;
            } else {
                newStr += strArr[i-1] + Integer.toString(cnt);
                cnt = 1;
            }
        }

        if(newStr.length() >= str.length()) {
            return str;
        }
        return newStr;
    }
}

 

 

---

 

1.6 이미지를 표현하는 NxN 행렬이 있다. 이미지의 각 픽셀은 4바이트로 표현된다. 이때, 이미지를 90도 회전시키는 메서드를 작성하라. 부가적인 행렬을 사용하지 않고서도 할 수 있겠는가?

 

 

 

 

---

 

1.7 MxN 행렬을 순회하면서 0인 원소를 발견하면, 해당 원소가 속한 행과 열의 모든 원소를 0으로 설정하는 알고리즘을 작성하라.

 

원소가 0인 행렬의 행과 열의 값을 boolean 배열의 index 값이 true로 줬다.

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] arr = {{0,1,1,1,1},{2,2,2,2,2},{3,3,3,3,3}};
        solution.changeMatrix(arr);
    }
}

class Solution {
    public int[][] changeMatrix(int[][] arr) {
        if(arr.length == 0) {
            return arr;
        }

        boolean[] row = new boolean[arr.length];    // 원소가 0인 인덱스는 true
        boolean[] col = new boolean[arr[0].length]; // 원소가 0인 인덱스는 true

        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr[i].length; j++) {
                if(arr[i][j] == 0) {
                    row[i] = true;
                    col[j] = true;
                }
            }
        }

        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr[i].length; j++) {
                if(row[i] || col[j]) {
                    arr[i][j] = 0;
                }
            }
        }

        // 행렬 확인을 위한 출력 코드
        for(int i=0; i<arr.length; i++) {
            for(int j=0; j<arr[i].length; j++) {
                System.out.print("arr[" + i + "][" + j + "] = " + arr[i][j] + ", ");
            }
            System.out.println("");
        }
        return arr;
    }
}

결과 값

arr[0][0] = 0, arr[0][1] = 0, arr[0][2] = 0, arr[0][3] = 0, arr[0][4] = 0, 
arr[1][0] = 0, arr[1][1] = 2, arr[1][2] = 2, arr[1][3] = 2, arr[1][4] = 2, 
arr[2][0] = 0, arr[2][1] = 3, arr[2][2] = 3, arr[2][3] = 3, arr[2][4] = 3, 

 

 

 

 

---

1.8 한 단어가 다른 단어에 포함된 문자열인지 판별하는 isSubstring 이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌을 때, s2가 가 s1을 회전시킨 결과인지 판별하는 코드를 isSubstring을 한 번만 호출하도록 하여 작성하라. (가령 'waterbottle'은 'erbottlewat'을 회전시켜 얻을 수 있는 문자열이다.)

 

코드

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s1 = "waterbottle";
        String s2 = "erbottlewat";
        System.out.println("solution.isRotated('waterbottle', 'erbottlewat') : " + solution.isRotated(s1, s2));
    }
}

class Solution {
    public boolean isRotated(String s1, String s2) {
        return isSubstring(s2.concat(s2), s1);
    }

    public boolean isSubstring(String s1, String s2) {
        return s1.contains(s2);
    }
}

결과 값

solution.isRotated('waterbottle', 'erbottlewat') : true