사전 문자열
자료구조

문자열

gabury1고친 사람 github-actions[bot]

문자열은 글자 여러 개를 순서대로 묶어 하나의 값으로 다루게 해 줍니다. 프로그램 안에서 사람이 읽는 글은 대개 문자열로 담깁니다. 컴퓨터 메모리에는 숫자만 들어가므로 글자마다 정해진 숫자로 바꿔 저장합니다.

쉽고 빠른 이해

문자열은 글자를 한 줄로 꿰어 한 덩어리로 다루는 값입니다. 로그인 창에 적은 아이디 kim 은 k · i · m 세 글자가 순서대로 묶인 문자열 하나입니다.

글자를 하나씩 따로 들고 다니면 이름 하나를 넘기는 데도 글자 수만큼 값을 챙겨야 합니다. 문자열로 묶으면 이름 하나가 값 하나가 됩니다.

메모리에 담기는 순서는 이렇습니다.

  1. 글자마다 정해진 글자 번호가 있습니다. 그 글자 번호를 바이트로 바꿉니다.
  2. 바뀐 바이트를 메모리에 빈틈 없이 나란히 둡니다.
  3. 몇 글자인지 함께 적어 두거나, 끝에 끝 표시를 붙입니다.

자바나 파이썬에서 문자열은 한 번 만들면 못 고칩니다. 그렇게 만든 대가로 고치기가 비쌉니다. 뒤에 글자 하나를 붙여도 새 문자열을 처음부터 다시 만듭니다.

문자열은 사람이 읽는 글에 씁니다. 숫자나 이미지 같은 값은 문자열로 담지 않습니다.

상세

이 절은 문자열이 글자를 메모리에 담는 모양과, 그 모양 때문에 연산마다 드는 비용을 다룹니다. 글자를 칸에 늘어놓은 그림에서 출발해 글자가 바이트로 바뀌는 방식, 길이를 아는 두 방법, 고칠 수 없는 문자열을 차례로 봅니다. 예시 코드는 자바로 적습니다.

글자를 순서대로 담는 모양

문자열은 문자 여러 개를 순서대로 담은 값입니다. 문자는 a · 가 · 7 · 띄어쓰기처럼 글 한 자를 가리킵니다. 문자열 "hello" 는 문자 다섯 개가 이 순서로 놓인 것입니다.

글자를 묶지 않으면 이름 하나를 함수에 넘길 때도 글자 수만큼 값을 넘겨야 합니다. 몇 글자인지도 따로 챙겨야 합니다. 문자열은 이 글자들을 값 하나로 묶어서 이름 하나를 변수 하나에 담게 합니다.

안쪽 모양은 대개 배열입니다. 배열은 같은 크기의 칸을 메모리에 빈틈 없이 붙여 둔 구조입니다. 글자마다 칸 크기가 같으면 글자 하나가 칸 하나를 씁니다.

몇 번째 칸인지를 나타내는 수를 인덱스라고 부릅니다. 인덱스는 0부터 셉니다. 아래 그림은 "hello" 가 칸 다섯 개에 놓인 모습입니다.

block-beta
columns 5
  a["0번 · h"] b["1번 · e"] c["2번 · l"] d["3번 · l"] e["4번 · o"]

메모리의 위치는 주소라는 수로 가리킵니다. 칸 크기가 같으면 몇 번째 칸의 주소를 곱셈 한 번으로 구합니다. 첫 칸의 주소에 인덱스 × 칸 크기를 더하면 됩니다. 그래서 글자가 몇 개든 원하는 칸을 곧바로 꺼냅니다.

코드에서는 글자를 큰따옴표로 감싸 문자열을 만듭니다. 이렇게 코드에 바로 적은 값을 문자열 리터럴이라고 부릅니다. 아래 코드는 문자열 하나를 만들고 길이와 글자를 꺼냅니다. 줄마다 내는 값을 오른쪽 주석에 적었습니다.

Java
String s = "hello";
s.length()         // 5
s.charAt(1)        // 'e'
s.substring(1, 3)  // "el"

length() 는 글자 수를 돌려줍니다. charAt(1) 은 1번 칸의 글자를 꺼냅니다. 인덱스가 0부터라서 두 번째 글자 e 가 나옵니다.

문자열 안의 한 토막을 부분 문자열이라고 부릅니다. substring(1, 3) 은 1번 칸부터 3번 칸 바로 앞까지를 잘라 새 문자열로 돌려줍니다.

글자와 바이트 사이의 변환

앞 그림은 글자 하나가 칸 하나를 쓰는 모습이었습니다. 실제 메모리에서는 글자가 바이트로 바뀌어 들어갑니다. 이 소절은 문자열 "A가" 가 바이트 몇 개가 되는지를 가지고, 글자 수와 바이트 수가 왜 갈리는지 봅니다.

메모리는 글자를 모릅니다. 바이트만 담습니다. 바이트는 비트 여덟 개로 이루어진 저장 단위입니다. 0부터 255까지의 수 하나를 담습니다.

그래서 글자마다 번호를 하나씩 정해 둡니다. A 는 65 로 정하는 식입니다. 이 글자 번호를 바이트로 적어 메모리에 담습니다.

글자와 바이트를 짝짓는 이 규칙을 문자 인코딩이라고 부릅니다. 규칙이 정해져 있어야 저장한 바이트를 나중에 같은 글자로 읽어 낼 수 있습니다.

오래 쓰여 온 규칙으로 ASCII(American Standard Code for Information Interchange, 미국 정보 교환 표준 부호)가 있습니다. 영문자와 숫자와 기호 128개에 글자 번호를 붙였습니다. 이 글자들은 한 바이트에 하나씩 들어갑니다.

한글처럼 ASCII 에 없는 글자를 담으려면 글자 번호가 더 많이 필요합니다. 유니코드는 세계의 글자 대부분에 글자 번호를 하나씩 붙인 표입니다.

UTF-8(Unicode Transformation Format 8-bit, 8비트 단위로 적는 유니코드 변환 형식)은 유니코드 글자 번호를 바이트로 적는 방법 가운데 하나입니다. 글자마다 1바이트에서 4바이트까지 씁니다. ASCII 글자는 1바이트, 한글 음절 하나는 3바이트입니다.

아래 그림은 문자열 "A가" 를 UTF-8 로 적은 바이트입니다. 앞 그림과 달리 칸 하나가 바이트 하나입니다. 칸마다 어느 글자의 바이트인지와 그 바이트의 값을 적었습니다.

block-beta
columns 4
  a["A · 65"] b["가 · 234"] c["가 · 176"] d["가 · 128"]

글자는 둘인데 바이트는 넷입니다. 글자마다 차지하는 바이트 수가 다릅니다. 그래서 n 번째 글자가 몇 번째 바이트에서 시작하는지 곱셈으로는 알 수 없습니다. 앞에서부터 글자를 세어 가야 합니다.

아래 코드는 같은 세 글자라도 바이트 수가 다르다는 것을 보입니다. UTF_8 은 자바의 StandardCharsets.UTF_8 을 줄여 적은 것입니다.

Java
"abc".getBytes(UTF_8).length     // 3
"가나다".getBytes(UTF_8).length  // 9

그래서 저장할 곳의 크기를 10바이트로 정해 두면 영문자는 열 글자가 들어갑니다. UTF-8 한글은 세 글자까지만 들어갑니다.

받은 바이트를 인코딩 규칙에 따라 글자로 되돌리는 일을 디코딩이라고 합니다. 저장할 때와 다른 규칙으로 디코딩하면 글자가 엉뚱한 글자로 깨져 보입니다. 이 현상을 모지바케라고 부릅니다.

자바에서 「한 글자」는 사람이 보는 글자와 다르게 셀 때가 있습니다. 자바 문자열은 안쪽을 UTF-16(Unicode Transformation Format 16-bit, 16비트 단위로 적는 유니코드 변환 형식)으로 적기 때문입니다.

UTF-16 은 2바이트 조각 하나에 글자 번호를 적습니다. 2바이트로는 6만 5천여 개까지만 적힙니다. 글자 대부분은 이 안에 들어갑니다. 글자 번호가 그보다 큰 글자는 조각 두 개를 씁니다.

자바의 length() 는 사람이 보는 글자 수가 아니라 이 조각의 개수를 셉니다. 아래 둘째 줄의 𝄞 는 글자 번호가 큰 악보 기호라서 한 글자인데 길이가 2로 나옵니다.

Java
"가".length()   // 1
"𝄞".length()   // 2

길이를 아는 두 방법

문자열이 어디서 끝나는지 아는 방법은 둘입니다. 끝에 표시를 붙이거나, 길이를 따로 적어 둡니다. 이 소절은 두 모양을 그림으로 나란히 봅니다. 그 차이가 길이를 재는 비용으로 어떻게 이어지는지도 봅니다.

C 언어는 끝 표시를 씁니다. 글자들 뒤에 값이 0인 바이트를 하나 붙입니다. 이 바이트를 널 문자라고 부릅니다. 아래는 C 에서 "hi" 가 놓인 모습입니다.

block-beta
columns 3
  a["h"] b["i"] c["널 문자 · 0"]

길이를 알려면 앞에서부터 글자를 세다가 널 문자를 만나야 멈춥니다. 글자 수를 n 이라고 하면 길이를 재는 데 n 에 비례하는 시간이 듭니다.

자바나 파이썬 같은 언어는 글자 수를 문자열과 함께 적어 둡니다. 모양을 간단히 그리면 아래와 같습니다.

block-beta
columns 3
  a["길이 · 2"] b["h"] c["i"]

길이를 물으면 적어 둔 값을 읽기만 합니다. 글자가 몇 개든 한 번에 끝납니다.

끝 표시 방식에는 제약이 하나 더 있습니다. 값 0 이 끝을 뜻하므로 문자열 한가운데에 값 0 인 바이트를 둘 수 없습니다. 그래서 이미지처럼 글자가 아닌 바이트를 담은 이진 데이터를 문자열로 다루지 못합니다.

한 번 만들면 못 고치는 문자열

자바와 파이썬의 문자열은 만든 뒤에 고칠 수 없습니다. 만든 뒤 내용을 못 바꾸는 성질을 불변이라고 부릅니다. 글자를 바꾸는 메서드는 원래 문자열을 두고 새 문자열을 만들어 돌려줍니다.

Java
String a = "hi";
String b = a.toUpperCase();
a   // "hi"
b   // "HI"

toUpperCase() 를 불러도 a 는 "hi" 로 남습니다. 대문자로 바뀐 글자는 새 문자열 b 에 들어 있습니다.

고칠 수 없게 만든 까닭은 나눠 쓰기 때문입니다. 같은 문자열을 여러 곳이 가리켜도 한쪽이 몰래 바꿀 걱정이 없습니다. 여러 스레드가 함께 읽어도 잠금 없이 안전합니다.

해시테이블의 키로 쓸 때도 이 성질이 쓸모 있습니다. 해시테이블은 키에서 수 하나를 계산해 값을 둘 칸을 정합니다. 이 수를 해시값이라고 합니다. 키가 나중에 바뀌면 해시값도 바뀌어서 넣어 둔 값을 다시 못 찾습니다. 문자열은 안 바뀌므로 이 걱정이 없습니다.

이어 붙이기가 비싸지는 때

불변에는 대가가 있습니다. 문자열 두 개를 이어 붙이면 두 문자열의 글자를 전부 새 칸에 옮겨 담습니다. 길이가 n 과 m 이면 n + m 글자를 복사합니다.

반복문 안에서 한 글자씩 이어 붙이면 이 복사가 쌓입니다. 첫 바퀴는 1글자, 둘째 바퀴는 2글자, n 번째 바퀴는 n 글자를 복사합니다. 다 합치면 복사량이 n 의 제곱에 가깝게 늘어납니다.

Java
String s = "";
for (int i = 0; i < n; i++) {
    s = s + "x";
}

StringBuilder 는 이 문제를 푸는 도구입니다. 고칠 수 있는 배열에 글자를 모았다가 마지막에 한 번만 문자열로 만듭니다. 글자를 붙일 때마다 앞 글자를 다시 복사하지 않습니다.

그 배열은 동적 배열입니다. 동적 배열은 칸이 모자라면 더 큰 배열을 잡아 글자를 옮겨 담습니다. 이때 한 칸씩이 아니라 크기를 두 배쯤으로 늘립니다. 그래서 옮기는 일이 점점 드물어집니다.

아래 코드는 앞 반복문을 StringBuilder 로 바꾼 것입니다. 옮기는 일이 드물어서 전체 복사량이 n 에 비례하는 수준에 머뭅니다.

Java
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
    sb.append("x");
}
String s = sb.toString();

연산마다 걸리는 시간

이 소절은 자주 쓰는 연산의 비용을 표 하나로 모읍니다. 비용은 빅오 표기법으로 적습니다. O(1) 은 글자 수와 상관없이 시간이 일정하다는 뜻입니다. O(n) 은 글자 수에 비례해 시간이 늘어난다는 뜻입니다.

연산 시간 까닭
인덱스로 글자 읽기 · 글자마다 바이트 수가 같을 때 O(1) 주소를 곱셈 한 번으로 구합니다
인덱스로 글자 읽기 · 글자마다 바이트 수가 다를 때 O(n) 앞에서부터 글자를 세어 갑니다
길이 재기 · 길이를 적어 둘 때 O(1) 적어 둔 값을 읽습니다
길이 재기 · 끝 표시를 쓸 때 O(n) 널 문자까지 셉니다
이어 붙이기 O(n + m) 두 문자열을 새 칸에 복사합니다
같은지 견주기 O(n) 앞에서부터 한 글자씩 견줍니다
부분 문자열 찾기 · 단순한 방법 O(n × m) 시작 위치마다 찾는 말을 처음부터 대 봅니다

표에서 m 은 이어 붙이는 쪽이나 찾는 말의 길이입니다.

KMP(Knuth-Morris-Pratt, 만든 세 사람의 이름) 알고리즘은 이미 견준 글자를 다시 보지 않습니다. 그래서 부분 문자열 찾기를 O(n + m) 에 끝냅니다.

문자열로 담지 않는 값

문자열은 사람이 읽는 글을 담는 구조입니다. 이 소절은 글이 아닌 값을 문자열에 담았을 때 생기는 실수 둘을 봅니다.

숫자를 문자열로 담으면 크기 비교가 어긋납니다. 문자열 비교는 앞 글자부터 하나씩 견주는 사전식 순서를 따르기 때문입니다. 첫 글자 1 이 9 보다 앞서므로 "10" 이 "9" 보다 작다고 나옵니다.

Java
"10".compareTo("9")   // 음수
10 > 9                // true

첫 줄의 음수는 "10" 이 앞선다는 뜻입니다. 둘째 줄처럼 숫자로 담아야 10 이 9 보다 크다고 나옵니다.

이미지나 압축 파일 같은 이진 데이터는 바이트 배열에 담습니다. 이진 데이터를 문자열로 디코딩하면 글자로 안 풀리는 바이트가 생깁니다. 그 바이트는 다른 글자로 바뀌어 원래 값을 잃습니다.

관련 항목

문자열을 이루는 구성 요소

문자 · 바이트 · 코드 포인트 · 코드 단위 · 널 문자 · 문자열 리터럴

문자열의 글자를 바이트로 적는 인코딩

문자 인코딩 · ASCII · Unicode · UTF-8 · UTF-16 · EUC-KR · 디코딩

문자열에 쓰는 연산

부분 문자열 · 문자열 비교 · 문자열 연결 · 문자열 보간 · 문자열 자르기 · 대소문자 변환 · 정규 표현식

문자열에서 말을 찾는 알고리즘

KMP 알고리즘 · 라빈-카프 알고리즘 · 보이어-무어 알고리즘 · 트라이 · 접미사 배열

문자열을 안쪽에서 받치는 자료구조

배열 · 동적 배열 · 로프 · 해시테이블

문자열의 불변과 맞물린 기법

불변 객체 · 문자열 인턴 · String pool · StringBuilder · 스레드 안전성

문자열에서 자주 나는 오류

모지바케 · 버퍼 오버플로 · off-by-one 오류 · SQL 인젝션 · 인코딩 불일치

문자열과 맞세워지는 값의 타입

정수 · 부동소수점 · 불리언 · 바이트 배열 · 열거형

문자열을 담아 주고받는 텍스트 포맷

JSON · CSV · XML · 이스케이프 시퀀스 · 직렬화

문자열이 속하는 상위 분류

데이터 타입 · 자료구조 · 시퀀스 · 참조 타입

다른 이름: string · 스트링