1주차
Array와 String은 코딩 테스트에서 가장 기본적으로 등장하는 자료 구조이며, 대부분의 알고리즘 문제는 순회, 비교, 변환, 탐색을 기반으로 해결되고 특히 배열과 문자열은 거의 모든 알고리즘 문제의 기초가 되기 때문에 시간 복잡도, 인덱스 접근, 문자열 처리 방식을 정확히 이해하는 것이 중요합니다.
Array는 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 자료 구조이며 각 데이터는 인덱스(index) 를 통해 접근할 수 있고 인덱스 접근의 시간 복잡도는
- 동일한 타입의 데이터만 저장 가능
- 메모리에 연속적으로 저장
- 인덱스를 이용한 빠른 접근 가능
$O(1)$ - 순회하면서 조건을 찾는 문제가 많이 등장
| 연산 | 시간복잡도 |
|---|---|
| 접근 (Access) | |
| 탐색 (Search) | |
| 삽입 (Insertion) | |
| 삭제 (Deletion) |
- 최댓값 / 최솟값 찾기
- 특정 조건을 만족하는 값 찾기
- 누적 합 계산
- 배열 뒤집기
- 정렬 후 처리
- 두 포인터 문제
String은 문자(char)의 배열 형태로 이루어진 자료 구조이며 대부분의 문자열 문제는 문자 비교, 문자열 탐색, 부분 문자열 처리와 관련되어 있고 언어에 따라 대부분 immutable(불변 객체) 의 특징을 가집니다.
- 문자(
char)의 배열 형태 - 인덱스를 통해 문자 접근 가능
- 문자열 비교 및 변환 문제 자주 등장
- 대부분의 언어에서 immutable
- 팰린드롬 검사
- 문자열 뒤집기
- 특정 문자 개수 세기
- 아나그램 판별
- 부분 문자열 탐색
- 문자열 압축
| 구분 | Immutable (불변) | Mutable (가변) |
|---|---|---|
| 의미 | 생성 후 내부 값을 변경할 수 없음 | 생성 후 내부 값을 변경할 수 있음 |
| 값 수정 | 수정 시 새 객체 생성 | 기존 객체의 값이 변경됨 |
| 장점 | 안정성 높음, 사이드 이펙트 적음 | 수정이 빠르고 효율적 |
| Java 예시 | String | ArrayList, StringBuilder |
| Python 예시 | str, tuple | list, dict |
| JavaScript 예시 | String | Array, Object |
문자열이 immutable이기 때문에 다음과 같은 코드에서는 성능 문제가 발생할 수 있습니다.
| 언어 | 비효율적인 방식 | 효율적인 방식 |
|---|---|---|
| Java | 문자열 반복 연결 |
StringBuilder 사용 |
| JavaScript | 문자열 반복 연결 | 배열 후 join()
|
| Python | 문자열 반복 연결 | 리스트 후 join()
|
Java
String result = "";
for (int i = 0; i < n; i++) {
result += "a";
}StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++) {
sb.append("a");
}
String result = sb.toString();Python
result = ""
for i in range(n):
result += "a"arr = []
for i in range(n):
arr.append("a")
result = "".join(arr)JavaScript
let result = "";
for (let i = 0; i < n; i++) {
result += "a";
}const arr = [];
for (let i = 0; i < n; i++) {
arr.push("a");
}
const result = arr.join("");Array / String 문제는 대부분 배열이나 문자열을 어떻게 순회하고 처리하느냐에 따라 해결되고 다음과 같은 패턴이 등장하면 Array 또는 String 문제일 가능성이 높습니다.
배열이나 문자열을 처음부터 끝까지 순회하면서 값을 계산하는 방식이며 가장 기본적인 형태의 문제입니다.
- 배열의 최댓값 / 최솟값 찾기
- 특정 조건을 만족하는 값 찾기
- 배열의 합 / 평균 계산
- 특정 문자 개수 세기
배열 또는 문자열을 for문으로 순회하면서 조건을 검사하거나 값을 누적합니다.
배열이나 문자열의 서로 다른 위치의 값을 비교하는 방식입니다.
- 문자열 뒤집기
- 팰린드롬 검사
- 특정 위치 문자 비교
인덱스를 이용하여 앞과 뒤의 값을 비교하거나 교환합니다.
순회하면서 특정 값을 누적하거나 계산하는 방식입니다.
- 배열의 합
- 구간 합 계산
- 특정 조건을 만족하는 개수 계산
반복문을 통해 값을 누적하거나 필요한 값을 계속 업데이트합니다.
문자나 숫자가 몇 번 등장했는지 계산하는 방식입니다.
- 특정 문자 개수 세기
- 가장 많이 등장한 문자 찾기
- 아나그램 문제
배열 또는 해시맵을 사용해
각 문자 또는 숫자의 등장 횟수를 저장합니다.
배열이나 문자열의 구조나 순서를 변경하는 문제입니다.
- 배열 뒤집기
- 문자열 변환
- 배열 재배치
- 문자열 압축
새로운 배열을 만들거나 기존 배열의 인덱스를 변경하여 문제를 해결합니다.
프로그래머스 - 가장 긴 팰린드롬
https://school.programmers.co.kr/learn/courses/30/lessons/12904
문자열 s가 주어질 때, 문자열의 부분 문자열 중 가장 긴 팰린드롬의 길이를 구하는 문제이며 팰린드롬이란 앞에서 읽어도 뒤에서 읽어도 같은 문자열을 의미합니다.
| s | return |
|---|---|
| "abcdcba" | 7 |
| "abacde" | 3 |
이 문제는 문자열의 인덱스를 활용하여 좌우를 확장하면서 팰린드롬을 검사하는 방식으로 해결할 수 있는데 문자열의 각 위치를 팰린드롬의 중심(center) 으로 두고 다음 두 가지 경우를 확인합니다.
- 홀수 길이 팰린드롬
- 짝수 길이 팰린드롬
각 중심에서 좌우로 확장하면서 문자가 같은지 확인하면 가장 긴 팰린드롬을 찾을 수 있습니다.
class Solution {
public int solution(String s) {
int max = 1;
for(int i = 0; i < s.length(); i++){
max = Math.max(max, expand(s, i, i));
max = Math.max(max, expand(s, i, i + 1));
}
return max;
}
private int expand(String s, int left, int right){
while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)){
left--;
right++;
}
return right - left - 1;
}
}- 문자열의 각 인덱스를 팰린드롬의 중심(center) 으로 설정합니다.
-
expand()메서드를 호출하여 중심에서 좌우로 확장하면서 문자가 같은지 비교합니다. - 팰린드롬은 홀수 길이 (
i, i)와 짝수 길이 (i, i+1) 두 가지 경우가 존재하므로 두 경우를 모두 검사합니다. - 좌우 문자가 다르거나 문자열 범위를 벗어나면 확장을 멈추고 현재 팰린드롬의 길이를 계산하여 반환합니다.
- 확장하면서 얻은 길이 중 가장 긴 팰린드롬 길이를
max변수에 저장하고 최종 결과로 반환합니다.
def solution(s):
max_len = 1
def expand(left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
for i in range(len(s)):
max_len = max(max_len, expand(i, i))
max_len = max(max_len, expand(i, i+1))
return max_len- 문자열의 각 인덱스를 팰린드롬의 중심(center) 으로 설정합니다.
-
expand()함수에서 좌우 인덱스를 확장하면서 문자가 같은지 확인합니다. - 팰린드롬은 홀수 중심 (
i, i)과 짝수 중심 (i, i+1) 두 가지 경우가 있으므로 두 경우를 모두 검사합니다. - 확장 과정에서 문자열 범위를 벗어나거나 문자가 다르면 현재 팰린드롬 길이를 계산하여 반환합니다.
- 모든 중심에 대해 탐색하면서 가장 긴 팰린드롬 길이를
max_len에 저장합니다.
function solution(s){
let max = 1
const expand = (left, right) => {
while(left >= 0 && right < s.length && s[left] === s[right]){
left--
right++
}
return right - left - 1
}
for(let i = 0; i < s.length; i++){
max = Math.max(max, expand(i, i))
max = Math.max(max, expand(i, i+1))
}
return max
}- 문자열의 각 인덱스를 팰린드롬의 중심(center) 으로 설정합니다.
-
expand()함수에서 좌우 인덱스를 확장하면서 문자가 같은지 비교합니다. - 팰린드롬은 홀수 길이 (
i, i)와 짝수 길이 (i, i+1) 중심을 모두 고려해야 합니다. - 좌우 문자가 다르거나 문자열 범위를 벗어나면 확장을 멈추고 현재 팰린드롬 길이를 계산합니다.
- 탐색 과정에서 가장 긴 팰린드롬 길이를
max변수에 저장하여 최종 결과로 반환합니다.
배열이나 문자열을 순회할 때 인덱스 범위를 잘못 설정하면 런타임 오류가 발생할 수 있고 배열의 마지막 인덱스는 length - 1 이므로 반복문 조건을 주의해야 합니다.
잘못된 예
for (int i = 0; i <= arr.length; i++) {
System.out.println(arr[i]);
}올바른 예
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}잘못된 예
arr = [1,2,3]
for i in range(len(arr)+1):
print(arr[i])올바른 예
arr = [1,2,3]
for i in range(len(arr)):
print(arr[i])잘못된 예
for(let i = 0; i <= arr.length; i++){
console.log(arr[i])
}올바른 예
for(let i = 0; i < arr.length; i++){
console.log(arr[i])
}문자열 비교 방식은 언어마다 다르기 때문에 잘못된 비교 연산자를 사용하면 예상과 다른 결과가 발생할 수 있습니다.
잘못된 예
String a = "hello";
String b = "hello";
if(a == b){
System.out.println("same");
}올바른 예
String a = "hello";
String b = "hello";
if(a.equals(b)){
System.out.println("same");
}잘못된 예
a = "hello"
b = "hello"
if a is b:
print("same")올바른 예
a = "hello"
b = "hello"
if a == b:
print("same")잘못된 예
let a = "hello"
let b = "hello"
if (a == b) {
console.log("same")
}올바른 예
let a = "hello"
let b = "hello"
if (a === b) {
console.log("same")
}