배열과 문자열

배열과 문자열

---

참고

1. 기본 자료 구조 비교

   • 배열(array):
     • + 내부 인덱스를 이용하여 자료의 검색이 한번에 이루어지기 때문에 빠른 검색 속도
     • - 데이터의 삽입, 삭제시 많은 데이터가 밀리거나 빈자리를 채우기 위해 이동해야 하기 때문에 많은 시간이 소요된다
   • 리스트(list):
     • + 삽입, 삭제시 인근 노드들의 참조값만 수정해 줌으로써 빠른 처리가 가능
     • - 데이터의 수가 많아질수록 효율이 떨어진다
   • hash:
     • 배열(array), 리스트(list)의 한계를 극복하기 위한 자료구조
     • 내부적으로 배열을 사용하여 데이터를 저장하기 때문에 빠른 검색 속도를 갖는다
     • 데이터의 삽입과 삭제시 기존 데이터를 밀어내거나 채우는 작업이 필요 없도록 특별한 알고리즘을 이용하여 데이터와 연관된 고유한 숫자를 만들어 낸뒤 이를 인덱스로 사용한다
     • 특정 데이터가 저장되는 인덱스를 그 데이터만의 고유한 위치이기 때문에 삽입시 다른 데이터의 사이에 끼어들거나 삭제시 다른 데이터로 채울 필요가 없으므로 삽입과 삭제시 데이터의 이동이 없도록 만들어진 구조다
   • JAVA 기준으로 각 자료 구조의 특징 정리
     • ArrayList: 배열 기반, 데이터의 추가와 삭제 유용하지 못함, 순차적인 추가 삭제는 제일 빠름, 인덱스가 있어 임의의 요소에 대한 접근성이 뛰어남
     • LinkedList: 연결 기반, 데이터의 추가와 삭제에 유용함, 임의의 요소에 대한 접근성이 좋지 못함
     • HashMap: 배열과 연결이 결합된 형태, 추가, 삭제, 검색, 접근성이 모두 뛰어남, 검색에는 최고 성능을 보인다

2. hash table

   • key-value 의 쌍
   • key 의 유일성이 보장되어야 데이터가 안전하게 저장된다
   • 이진 탐색 트리 를 사용한 hash table 의 경우 시간복잡도 O(logN) 을 보장한다
   • JAVA 에서의 hashtable
     • HashTable(o), HashMap(x): thread safe 한지 하지않은지 로 나뉜다

3. ArrayList

   • 동적으로 크기가 조정되는 배열
   • 일반적으로 배열의 크기가 증가할 때, 배열의 크기를 늘리는 시간은 O(N)
   • 자주 일어나는 일이 아니므로 O(1) 로 생각한다

4. StringBuffer

   • String 과 비교: append 작업시 O(xN2) 만큼 차이를 보인다

   •   for(String a:aLists){
           string = string + a; // 계속해서 새로운 객체를 생성하기 때문이다
           stringBuffer.append(a);
       }
     

5. 문제풀이

   • 문제 풀기 전 확인하고 싶은 사항
     • 같은 문자는 대소문자 구분이 없는가
     • 문자열의 길이 제한이 있는가

   •   StringBuffer result = "";
       String previousChar = "";
       int sameCnt = 0;
       for(int i=0;i<str.length();i++){
           if (result.toString().length() > str.length()){
               return str;
           }else{
               if(previousChar.equel(str.indexOf(i))){
                   sameCnt++;
     
                   if(){
     
                   }
               }else{
                   if(sameCnt!=0){
                       // result.append(previousChar+sameCnt);
                       result.append(previousChar);
                       result.append(sameCnt);
                   }
     
                   previousChar = str.indexOf(i)
                   sameCnt = 1;
               }
           }
       }