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

Leetcode를 풀던 중, 나는 모든 문제를 거의 brute force를 이용해 풀고 있다는걸 알았다. 내가 배운 자료구조와 알고리즘의 기초적인 개념만 알고 넘어갔기 때문에, 어떤 문제를 봤을때 어떤 알고리즘과 자료구조를 써야 할지 감이 하나도 안 잡히는 상황이였다. 이때 무턱대고 문제를 풀게 아니라, 자료구조와 알고리즘을 좀 더 깊이 공부해 보고자 책을 샀다. 미국에서 CS 전공생이라면 한번씩은 들어본 "Cracking the coding interview"이다. 코테의 교과서 같은 존재이다. 좀 오래되긴 했지만, 그래도 근본은 변하지 않기 때문에 공부를 해보고자 한다.

사실 대부분 다 아는 내용이지만, 여기에 기록하며 한번씩 더 공부 해 보기로 했다. 필자도2 그렇고 대부분 다 아는 내용이고 무엇보다 이 블로그는 내 개인 공부 기록용이기 때문에 너무 깊게는 안 살펴보겠다.

 

1. Array

- 자바에서는 배열이라고 불리우고, 파이썬에서는 리스트 라고 불리운다. 자료구조적인 관점에서 배열을 설명한다면 배열은 한마디로 "같은 타입을 가진 연속된 메모리 덩어리" 라고 한다. 하지만, 자바와 파이썬에서의 리스트(배열)은 차이가 있다.

 

- 파이썬 : 리스트의 길이는 유동적이며, 처음 리스트를 선언할때 초기 크기를 지정하지 않아도 된다.

- 자바 : 배열의 길이는 유동적이지 않고, 처음 배열을 선언할때 배열의 길이도 정해주어야 한다.

 

하지만, 자바에서는 편의를 위해 유동적인 배열 클래스를 제공해 준다. ArrayList는 배열과 유사하지만 길이가 유동적으로 변할 수 있으며, O(1)의 탐색시간을 제공한다. 예를 들어보면,

ArrayList<String> sentence = new ArrayList<String>();
sentence.add("hi!");

 

위처럼 처음에 자료형을 명시해준다.(자바는 자료형을 무조건 지정해주어야 하지만, 파이썬은 따로 자료형을 지정해 줄 필요가 없다.) 여기서의 가장 큰 특징은 ArrayList는 배열의 형태이지만 초기 길이를 정해주지 않았고, sentence.add를 하는 순간 한 칸이 늘어난다.

 

2. StringBuilder

 

- 이 StrigBuilder도 마찬가지로 ArrayList와 비슷한 역할을 한다. 하지만 이 자료구조의 자료형은 String이다.

 

예를 들어보자. 만약 여러개의 문자열을 하나로 합친다고 생각해 보자. 이 과정의 러닝타임은 대략 얼마나 될까?(여기서 문자열의 길이를 x라고 하고, n개의 문자열이 있다고 해 보자.)

String joinWords(String[] words) {
	String sentence = "";
    for(String w : words) {
    	sentence += w;
     }
     return sentence;
     }

1. 문자열 결합의 비용:
   - Java에서 문자열은 불변 객체(immutable)이다. 따라서 문자열을 결합할 때마다 새로운 문자열 객체가 생성되고, 기존의 문자열과 새로 추가되는 문자열이 모두 복사된다.
   - `sentence += w`는 사실상 `sentence = sentence + w`와 동일한 작업이다. 이 작업은 `sentence`의 길이와 `w`의 길이만큼의 시간 복잡도를 가진다.

2. 반복문 분석:
   - 처음에 `sentence`는 빈 문자열이다. 따라서 첫 번째 반복에서는 `w`의 길이만큼의 시간 복잡도가 발생한다. (`O(x)`, 여기서 `x`는 `w`의 길이다.)
   - 두 번째 반복에서는 `sentence`의 길이가 `x`가 되고, 다시 `w`를 더하므로 `2x`의 시간 복잡도가 발생한다.
   - 세 번째 반복에서는 `sentence`의 길이가 `2x`가 되고, 다시 `w`를 더하므로 `3x`의 시간 복잡도가 발생한다.

이 과정을 n개의 문자열에 대해 반복하면, 총 복사 비용은 다음과 같이 계산할 수 있다:
= O(x) + O(2x) + O(3x) + ... + O(nx)

이 합은 수학적으로 등차수열의 합과 같으며, 다음과 같이 표현된다:
O(x (1 + 2 + 3 + ... + n))

등차수열의 합은 다음과 같다:
1 + 2 + 3 + ... + n = {n(n + 1)} / 2

여기서 x는 일정한 문자열 길이이므로 이를 무시할 수 있으며, 빅오 표기법은 O(n^2) 와 같이 나타낼 수 있다. 하지만 알다시피, O(n^2)라는 시간 복잡도는 효율적이지 못한 시간 복잡도이다. 여기서 쓸 수 있는게 StringBuilder이다. 이 자료구조는 단순히 동적으로 길이 조절이 가능한 배열을 생성한다.

String joinWords(String[] words) {
	StringBuilder sentece = new StringBuilder();
    for (String w : words) {
    sentence.append(w);
    }
    return sentence.toString();
    }