01. 배열과 문자열

Hash table

• 효율적인 탐색을 위한 자료구조
• key-value 방식

구현방법

• 키의 해시 코드를 계산한다. (키의 개수는 무한한데 int 의 개수는 유한하기 때문에 서로다른 두 개의 키가 같은 해시코드를 가리킬 수 있다.)
• hash(key) % array_length 같은 방식으로 해시코드를 이용해 배열의 인덱스를 구한다. (서로다른 두개의 해시 코드가 같은 인덱스를 가리킬 수 있다.)
• 배열의 각 인덱스에는 키와 값으로 이루어진 연결 리스트가 존재한다. 키와 값을 해당 인덱스에 저장한다. 충돌에 대비하여 반드시 연결 리스트를 이용한다. (충돌 : 서로다른 두 개의 키가 같은 해시 코드를 가리킬때, 서로다른 두 개의 해시 코드가 같은 인덱스를 가리킬때)

값을 찾을 때

• 주어진 키로부터 해시 코드를 계산하고 이를 통해 인덱스를 계산한다.
• 해당 키에 상응하는 값을 연결리스트에서 탐색한다.

충돌이 최소화 되도록 잘 구현 된 경우 탐색 시간은 O(1) 이다.

---

ArrayList 와 가변 크기 배열

• 자바같은 언어에는 배열의 길이가 고정되어있다.
• ArrayList 는 필요에 따라 크기를 변화시킬 수 있고 O(1) 의 접근 시간을 유지한다.
• 배열이 가득차는 순간 배열의 크기를 두배로 늘린다.
• 크기를 두배로 늘리는 시간은 O(n)이지만 자주 발생하지 않아 O(1) 로 생각한다.

상환시간은 왜 O(1) 일까

• 1개 복사
• 2개 복사
• 3개 복사
• ...
• n/16 복사
• n/8 복사
• n/4 복사
• n/2 복사

총 1의 길이만큼 이동해야 한다고 생각할때 하루의 총길이의 반만 간다면 무한히 많은 날을 걸어도 절대 1에 도달할 수 없다.

따라서 수열의 합은 O(N)이 되는데 배열의 상황에 따라 최악의 경우 O(N)이 소요되는 삽입 연산도 있지만 평균적으로 각 삽입은 O(1) 이 소요된다.

---

StringBuilder

• 가변 크기 배열을 이용해서 필요한 경우에만 문자열을 복사하게끔 해준다.

---

문제 1.1

중복이 없는가: 문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀수 있는 알고리즘 또한 고민하라.

 

방법: HashSet을 이용하여 문자 중복을 판단한다.

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
        System.out.println(solve("aiejfijefaef"));
        System.out.println(solve("abcdefghijk"));
        System.out.println(solve("abcdefghijkj"));
     }
     public static boolean solve(String str){
            HashSet<Character> set = new HashSet();
            for(int i = 0 ; i < str.length() ; i++){
                char ch = str.charAt(i);
                if(set.contains(ch)){
                    System.out.print(ch+" is duplicated //");
                    return false;
                }else{
                    set.add(ch);
                }
            }
            return true;
     }
}

---

문제 1.2

순열확인 : 문자열 두 개가 주어졌을 때 이 둘이 서로 순열 관계에 있는지 확인하는 메서드를 작성하라.

*순열이라는 것은 서로가 문자열의 종류와 숫자가 같으면서 배열된 순서가 다른 것을 말한다.

방법1: 정렬 후 문자열이 같은지 확인한다.

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
        System.out.println(solve("abcde","deabc"));
        System.out.println(solve("abcdghijk","abcdeghijkh"));
        System.out.println(solve("bcdef","cbfed"));

     }
     public static boolean solve(String str1, String str2){
         if(str1.length() != str2.length()){
             System.out.print("length not equal //");
             return false;
         }
            if(sort(str1).equals(sort(str2))){
                return true;
            }else{
                return false;
            }
     }
     
     public static String sort(String str){
         char[] array = str.toCharArray();
         Arrays.sort(array);
         return new String(array);
     }
}

---

방법2: 문자열에 포함된 문자의 출현횟수가 같은지 검사한다.

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
        System.out.println(solve("abcde","deabc"));
        System.out.println(solve("abcdghijk","abcdeghijkh"));
        System.out.println(solve("bcdef","cbfed"));

     }
     public static boolean solve(String str1, String str2){
         if(str1.length() != str2.length()){
             System.out.print("length not equal //");
             return false;
         }
         char[] array1 = str1.toCharArray();
         int[] letters = new int[128]; //ASCII
         for(char c : array1){
             letters[c]++;
         }
         char[] array2 = str2.toCharArray();
         for(char c : array2){
             letters[c]--;
             if(letters[c] != 0){
                 return false;
             }
         }
         return true;
     }
     
     
}

---

---

문제 1.3

URL화: 문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메서드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다.

 

방법: StringBuilder 를 사용하고 공백일 경우 %20을 append 한다.

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
        System.out.println(solve("Mr John Smith",13));
     }
     public static String solve(String str, int size){
         char[] array = str.toCharArray();
         StringBuilder builder = new StringBuilder();
         for(char c: array){
             if(c == ' '){
                 builder.append("%20");
             }else{
                 builder.append(c);
             }
         }
         return new String(builder);
     }

}

---

문제 1.4

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

 

방법: 문자열에서 동일한 문자가 짝수개가 있으면 회문이다.

예를들어 tactcoa 라고 하면 t가 2개 a가 2개 c가 2개 o가 1개 이다. 사전에 등장하는 단어일 필요가 없으니 tacocat 로 만들 수 있다.

문자열 길이가 짝수 일 경우 각 문자가 짝수개씩 있어야 하며 홀수 일 경우 중간에 들어가는 문자 빼고 짝수개 여야 한다.

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
        System.out.println(solve("tact coa"));
     }
     public static boolean solve(String str){
         HashMap<Character,Integer> map = new HashMap();
         
         char[] array = str.toCharArray();
         for(char c : array){
             if(c==' ') continue;
             if(map.containsKey(c)==false){
                 map.put(c,1);
             }else{
                 int temp = map.get(c);
                 temp++;
                 map.put(c,temp);
             }
         }
         
         int oddCount = 0;
         for( Character key : map.keySet() ){
            if(map.get(key)%2!=0){
                oddCount++;
            }
        }
        System.out.println(map);
        if(map.size()%2 == 0 && oddCount %2 == 1){
            return true;
        }else if(map.size()%2 == 1 && oddCount == 0){
            return true;
        }
        return false;
         
     }

}

---

문제 1.5

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

 

방법: 길이가 같을 경우 문자 교체만 할 수 있는데 한개 이상 다른 부분이 발견되면 false 를 리턴한다. 

길이가 1 이상 차이날 경우는 방법이 없으므로 false 를 리턴한다.

길이가 1차이나는 경우 위치값 변수 2개를 가지고 iterate 한다. 같을 경우 두 변수 다 ++ 해주고 다를 경우 문자열 길이가 긴 변수만 ++ 해준다. 그 뒤 한번더 다른 경우가 발생 할 때(위치값 변수도 다르고 해당하는 문자도 다른 경우) false를 리턴한다.

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
        System.out.println(solve("pale","ple"));
        System.out.println(solve("pales","pale"));
        System.out.println(solve("pale","bale"));        
        System.out.println(solve("pale","bake"));


     }
     public static boolean solve(String str1,String str2){
         if(str1.length() < str2.length()){
             String temp = str1;
             str1 = str2;
             str2 = temp;
         }
        int longLen = str1.length();
        int shortLen = str2.length();
        
        if(longLen - shortLen > 1){
            return false;
        }
        System.out.println(shortLen + " " + longLen);
        char[] array1 = str1.toCharArray();
        char[] array2 = str2.toCharArray();
        
        System.out.println(Arrays.toString(array1));
        System.out.println(Arrays.toString(array2));
        
        //문자열 교체
        if(shortLen == longLen){
            int count = 0;
            for(int i = 0 ; i < shortLen ; i++){
                if(array1[i] != array2[i]) count++;
            }
            if(count == 0 || count == 1) return true;
        }else{ //문자열 추가 삭제
            int index1 = 0;
            int index2 = 0;
            while(index1 < longLen && index2 < shortLen){
                if(array1[index1] != array2[index2]){
                    if(index1 != index2){
                        return false;
                    }
                    index1++;
                }else{
                    index1++;
                    index2++;
                }
            }
            return true;
        }
        
        return false;
     }

}

//문자열 길이 체크할때 절댓값을 쓰면 편하다.
Math.abs(first.length() - second.length())

---

문제 1.6

문자열 압축: 반복되는 문자의 개수를 세는 방식의 기본적인 문자열 압축 메서드를 작성하라.

예를 들어 문자열 aabccccaaa를 압축하면 a2b1c5a3가 된다.

만약 압축된 문자열의 길이가 기존 문자열의 길이보다 길다면 기존 문자열을 반환해야 한다.

문자열은 대소문자 알파벳으로만 이루어져 있다.

 

방법1: StringBuilder 를 사용한다.

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
        System.out.println(solve("aabccccaa"));
    
     }
     public static String solve(String str){
         StringBuilder compressed = new StringBuilder();
         int count = 1;
         
         for(int i = 0 ; i < str.length(); i++){
             if(i+1 >= str.length() || str.charAt(i) != str.charAt(i+1)){
                 compressed.append(""+str.charAt(i)+count);
                 count = 1;
             }else{
                 count++;
             }
            //마지막 edge case 일때 추가하는 조건
            //i+1 >= str.length();
         }
        return compressed.length() < str.length() ? new String(compressed) : str;
     }

}

---

문제 1.7

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

 

방법1: (0,0)->(0,N) (0,1) -> (1,N) ...  // (1,0)->(0,N-1) (1,1)->(1,N-1) ...

이런식으로 행렬을 추가로 만드는 방법이 있다.

 

방법2: 레이어로 나누어 교체 작업을 인덱스 별로 수행한다.

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
         char[][] array = {
             {'a','b','c','d'},
             {'f','g','h','i'},
             {'k','l','m','n'},
             {'p','q','r','s'}
         };
         System.out.println(solve(array));
    
     }
     public static boolean solve(char[][] arr){
         for(int i = 0 ; i < arr.length ; i ++){
             System.out.println(Arrays.toString(arr[i]));
         }
         int n = arr.length;
         if(arr.length == 0 || arr.length != arr[0].length) return false;
         for(int layer = 0 ; layer < n/2 ; layer++){
             int first = layer;
             int last = n-1-layer;
             for(int i = first; i < last ; i++){
                 int offset = i - first;
                 char top = arr[first][i]; //윗부분 저장
                 
                 //왼쪽->위쪽
                 arr[first][i] = arr[last-offset][first];
                 //아래쪽->왼쪽
                 arr[last-offset][first] = arr[last][last-offset];
                 //오른쪽->아래쪽
                 arr[last][last-offset] = arr[i][last];
                 //위쪽->오른쪽
                 arr[i][last] = top;
             }
         }
         System.out.println("------------");
         for(int i = 0 ; i < arr.length ; i ++){
             System.out.println(Arrays.toString(arr[i]));
         }
         
         return true;
     }

}

---

문제 1.8

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

 

방법1: O(MN)의 추가 공간을 만들어서 0을 발견하는 즉시 0으로 만들어 준다.

바로바로 0을 만들어 주면 나중에 생긴 0을 또 참고 하므로 반드시 추가 공간이 필요하다.

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
         char[][] array = {
             {'a','b','c','d','e'},
             {'f','g','h','i','f'},
             {'k','l','0','n','o'},
             {'p','0','r','s','t'}
         };
         System.out.println(solve(array));
    
     }
     public static boolean solve(char[][] arr){
         for(int i = 0 ; i < arr.length ; i ++){
             System.out.println(Arrays.toString(arr[i]));
         }
         int n = arr.length;
         int m = arr[0].length;
         for(int i = 0 ; i < arr.length ; i ++){
             for(int j = 0 ; j < arr.length ; j++){
                 if(arr[i][j] == '0'){
                     int x = i;
                     int y = j;
                     for(int k=0 ; k < m ; k++){
                         arr[x][k] = 'X';
                        
                     }
                     for(int k=0 ; k < n ; k++){
                         arr[k][y] = 'X';
                     }
                      
                    //  x,0, x,1 .. x,m-1
                    //  0,y 1,y .. n-1,y
                 }
             }
         }
         
        
         System.out.println("------------");
         for(int i = 0 ; i < arr.length ; i ++){
             System.out.println(Arrays.toString(arr[i]));
         }
         
         return true;
     }

}

---

방법2: 한번 루프를 돌면서 0이있는 행과열을 저장한 후 다시 루프를 돌면서 0으로 만들어준다. 

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
         char[][] array = {
             {'a','b','c','d','e'},
             {'f','g','h','i','f'},
             {'k','l','0','n','o'},
             {'p','0','r','s','t'}
         };
         System.out.println(solve(array));
    
     }
     public static boolean solve(char[][] arr){
         for(int i = 0 ; i < arr.length ; i ++){
             System.out.println(Arrays.toString(arr[i]));
         }
         
          int m = arr[0].length;
         int n = arr.length;
        HashMap<Integer,Integer> map = new HashMap();
        
         for(int i = 0 ; i < n ; i ++){
             for(int j = 0 ; j < m ; j++){
                 if(arr[i][j] == '0'){
                     map.put(i,j);
                 }
             }
         }
         
         for(Integer key : map.keySet()){
             int x = key;
             int y = map.get(key);
             for(int i = 0 ; i < n ; i++){
                 arr[i][y] = '0';
             }
             for(int i = 0 ; i < m ; i++){
                 arr[x][i] = '0';
             }
         }
         
        
        
         System.out.println("------------");
         for(int i = 0 ; i < arr.length ; i ++){
             System.out.println(Arrays.toString(arr[i]));
         }
         
         return true;
     }

}

---

문제 1.9

문자열 회전: 한 단어가 다른 문자열에 포함되어 있는지 판별하는 isSubstring이라는 메서드가 있다고 하자. s1과 s2의 두 문자열이 주어졌고, s2가 s1을 회전시킨 결과인지 판별하고자 한다.

(가렬 'waterbottle'은 'erbottlewat'을 회전시켜서 얻을 수 있는 문자열이다.)

isSubstring 메서드를 한번만 호출해서 판별할 수 있는 코드를 작성하라.

 

방법1: s2를 s2.length 만큼 한칸씩 뒤로 밀면서 s1과 비교한다. s1과 같으면 loop 도중 true 로 탈출하고 s2를 한바퀴 돌릴때 까지 s1과 같은 경우가 없다면 false를 리턴한다. 근데 isSubstring 이라는 메서드를 써서 구현을 해야하는거니 다시하겠다.

import java.util.*;
public class HelloWorld{
     public static void main(String []args){
         
         System.out.println(isSubstring("waterbottle","erbottlewat"));
    
     }
     public static boolean isSubstring(String a, String b){
         char[] arrayA = a.toCharArray();
         char[] arrayB = b.toCharArray();
         int count=0;
         while(count<arrayA.length){
             
            if(arrayA != arrayB){
                char last = arrayB[arrayB.length-1];
                char[] array = new char[arrayB.length];
                array[0] = last;
                for(int i = 0 ; i < arrayB.length-1 ; i++){
                    array[i+1] = arrayB[i];
                }
                arrayB = array;
                System.out.println("A : " + Arrays.toString(arrayA));
                System.out.println("B : " + Arrays.toString(arrayB));
                if(Arrays.equals(arrayA,arrayB)){
                    return true;
                }
               
             }
            
             count++;
         }

         return false;
     }

}

---

방법2: s1과 s2가 회전한 문자열이라면 회전한 지점을 알아야 한다. 

s1을 xy로 쪼개진다고 하면 s2는 yx가 되어야 한다. 이때 s2가 쪼개진 yx는 s1s1인 xyxy의 부분 문자열 이여야 한다.

String s1s1 = s1+s1;
return isSubstring(s1s1,s2);