가장 기본이자 가장 많이 쓰이는 자료구조가 배열이에요. 인덱스 접근은 O(1)로 번개같지만, 중간에 넣고 빼는 건 생각보다 비싸요. 그 차이를 정확히 이해하면 코테 문제의 절반이 풀려요.
Array, 자바 ArrayList)의 개념을 알아요.배열(Array)은 같은 타입의 데이터를 연속된 자리에 나란히 저장하는 자료구조예요. 각 자리에는 0부터 시작하는 번호(인덱스)가 붙어요. 그래서 arr[0]이 첫 번째 요소, arr[1]이 두 번째 요소예요.
arr[0] 자리의 10, arr[1] 자리의 20처럼, 배열을 이루는 낱개 데이터가 바로 요소예요. "배열엔 요소가 5개 있다" = "칸이 5개 채워져 있다"는 뜻이에요.const arr = [10, 20, 30, 40, 50];
// 0 1 2 3 4 ← 인덱스(0부터!)
console.log(arr[0]); // 10 (첫 번째 요소)
console.log(arr[2]); // 30
console.log(arr.length); // 5 (요소 개수)O(1)은 그래도 시간이 그대로(안 늘어남), O(n)은 시간도 2배, O(n²)은 시간이 4배로 늘어나요. 그래서 O(1)이 가장 좋고, 숫자·글자가 붙을수록(O(n) → O(n²)) 점점 느려진다고 기억하면 쉬워요.arr[2]를 찾을 때 앞 칸을 하나씩 세지 않아요. "시작 + 2칸" 위치를 바로 계산하니 몇 번째든 단번에 닿아요 → O(1)int[] arr = {10, 20, 30}; 처럼 쓰고, arr[0]으로 첫 요소에 접근해요. 인덱스가 0부터인 것도, 접근이 O(1)인 것도 완전히 동일해요. 다만 자바 기본 배열은 크기가 고정이라는 점이 달라요(뒤에서 다뤄요).인덱스로 접근하는 건 O(1)이에요. 하지만 값을 찾는 것(탐색)과 중간에 넣고 빼는 것은 이야기가 달라요.
function indexOf(arr, target) {
for (let i = 0; i < arr.length; i++) { // 앞에서부터 하나씩
if (arr[i] === target) return i; // 찾으면 위치 반환
}
return -1;
}const arr = [10, 20, 30, 40];
// 인덱스 1 자리에 99를 끼워넣으려면?
// 20, 30, 40 을 전부 한 칸씩 뒤로 밀어야 해요.
arr.splice(1, 0, 99); // [10, 99, 20, 30, 40]| 연산 | 복잡도 | 이유 |
|---|---|---|
인덱스 접근 arr[i] | O(1) | 위치를 바로 계산해 단번에 접근 |
| 값 탐색 (찾기) | O(n) | 처음부터 하나씩 훑어야 함 |
| 끝에 삽입 (push) | O(1) | 뒤에 밀 요소가 없음 (평균) |
| 중간 삽입·삭제 | O(n) | 뒤 요소를 전부 밀거나 당겨야 함 |
순수한 배열은 크기가 고정이에요(자바 기본 배열처럼). 하지만 실무·코테에선 동적 배열(Dynamic Array)을 훨씬 많이 써요. 요소를 계속 추가하면 내부적으로 알아서 공간을 늘려주는 배열이에요.
const arr = []; // 빈 배열로 시작
arr.push(10); // [10]
arr.push(20); // [10, 20]
arr.push(30); // [10, 20, 30]
console.log(arr.length); // 3 ← 크기가 알아서 늘어남push로 끝에 추가하는 건 대부분 O(1)이에요(가끔 공간이 꽉 차서 내부적으로 복사하는 순간만 느리지만, 평균적으로 O(1)이에요).
💡 이런 걸 "평균 O(1)"(분할 상환, amortized)이라고 불러요. 대부분 빠르고, 아주 가끔만 느려서, 평균으로 보면 O(1)이라는 뜻이에요.
int[]는 크기가 고정이라 늘릴 수 없어요. 대신 ArrayList<Integer>를 쓰면 list.add(10)으로 계속 추가할 수 있어요. 이게 바로 동적 배열이고, JS의 Array·push와 역할이 같아요.문자열(String)은 문자들이 순서대로 나열된 것이에요. 배열처럼 인덱스로 각 문자에 접근할 수 있어요. "hello"[0]은 "h"예요.
const s = "hello";
console.log(s[0]); // "h"
console.log(s[4]); // "o"
console.log(s.length); // 5let s = "hello";
s[0] = "H"; // ❌ 아무 일도 안 일어나요! (조용히 무시)
console.log(s); // "hello" ← 그대로
// 바꾸려면 새 문자열을 만들어야 해요
s = "H" + s.slice(1); // "Hello" ← 새 문자열 생성+로 이어붙이면 매번 새 문자열이 생겨 느려질 수 있어요. 많이 이어붙일 땐 배열에 모았다가 join하는 게 좋아요.
String도 불변이에요. 그래서 문자열을 많이 조합할 땐 StringBuilder를 써요. JS에서 배열에 모아 join하는 것과 같은 이유예요 — 매번 새 문자열을 만드는 낭비를 피하려는 거예요.const arr = [10, 20, 30];
// 방법 1: 인덱스로 (i가 필요할 때)
for (let i = 0; i < arr.length; i++) {
console.log(i, arr[i]); // 0 10 / 1 20 / 2 30
}
// 방법 2: for-of (값만 필요할 때 간결)
for (const x of arr) {
console.log(x); // 10 / 20 / 30
}const arr = [1, 2, 3];
arr.reverse(); // [3, 2, 1] (배열은 제자리에서 뒤집힘)
// 문자열 뒤집기: 문자열은 불변이라 배열로 바꿔서!
const s = "abc";
const rev = s.split("").reverse().join(""); // "cba"split("")로 배열로 바꾼 뒤 뒤집고 다시 join해요.
const s = "hello";
console.log(s.slice(0, 3)); // "hel" (0번부터 3번 앞까지)
console.log(s.slice(1)); // "ello" (1번부터 끝까지)
console.log(s.substring(1, 4)); // "ell"
const arr = [1, 2, 3, 4, 5];
console.log(arr.slice(1, 3)); // [2, 3] (배열에도 slice가 있어요)slice(시작, 끝)은 끝 인덱스 바로 앞까지 잘라요. 원본은 건드리지 않고 새 값을 돌려줘요.
💡 문자열에 slice·substring을 써도 원본은 그대로예요(불변이니까!). 잘라낸 결과가 새 문자열로 나올 뿐이에요.
arr[0]이 첫 요소.Array · 자바 ArrayList)은 크기가 알아서 늘고, push는 평균 O(1).