[Python-알고리즘] 배열과 문자열

배열과 문자열 상세 정리 및 자주 쓰이는 응용문제

1. 배열 (Array)

배열은 동일한 타입의 데이터를 메모리상에 연속적으로 저장하는 자료구조입니다.
배열의 가장 큰 특징은 인덱스(index)를 통해 원하는 위치의 원소에 O(1) 시간에 접근 가능하다는 점입니다.

배열의 장점:
- 빠른 인덱스 접근 (임의 접근이 가능)
- 메모리 연속적 할당으로 캐시 친화적

배열의 단점:
- 크기가 고정되어 변경이 어렵다
- 삽입, 삭제 시 데이터 이동이 필요하여 O(n)의 시간이 든다
- 동적 배열(예: Python의 리스트)은 내부적으로 크기를 재조정하며 관리한다

2. 문자열 (String)

문자열은 문자들이 순서대로 나열된 자료구조이며, 배열과 유사하지만 언어마다 다르게 취급됩니다.
많은 언어에서 문자열은 불변(immutable)인 경우가 많아, 직접 수정이 어렵고 새로운 문자열을 만들어야 합니다.
문자열 문제는 패턴 매칭, 접두사/접미사 처리, 슬라이딩 윈도우 등 다양한 알고리즘 기법이 활용됩니다.

문자열 특징 및 활용:
- 길이 조회, 특정 위치 문자 접근은 O(1)에 가능
- 회문 검사, 아나그램, 부분 문자열 탐색 등 다양한 문제에 자주 등장
- 해시, 투 포인터, 슬라이딩 윈도우 등의 기법으로 최적화 가능

3. 자주 쓰이는 배열 및 문자열 응용 문제

3-1. 두 수 합 (Two Sum)

배열에서 합이 특정 목표값인 두 수의 인덱스를 찾는 문제입니다.

풀이 전략: 해시맵을 사용하여 현재 수의 보완값이 이전에 나왔는지 빠르게 확인.
시간복잡도는 O(n)으로 효율적입니다.

def two_sum(nums, target):
    hashmap = {}  # 숫자: 인덱스를 저장하는 딕셔너리
    for i, num in enumerate(nums):
        complement = target - num  # 현재 숫자와 더해서 target이 되는 수
        if complement in hashmap:
            # 보완값이 이미 해시맵에 있으면 답을 찾은 것
            return [hashmap[complement], i]
        hashmap[num] = i  # 현재 숫자와 인덱스를 해시맵에 저장
    return []  # 답이 없으면 빈 리스트 반환

3-2. 최대 연속 1의 개수 (Max Consecutive Ones)

이진 배열에서 연속된 1이 가장 많이 나오는 부분의 길이를 찾는 문제입니다.

풀이 전략: 배열을 한 번 순회하며 현재 연속 1의 개수를 세고 최대값을 갱신.
시간복잡도는 O(n).

def find_max_consecutive_ones(nums):
    max_count = 0  # 최대 연속 1의 개수
    count = 0      # 현재 연속 1의 개수

    for num in nums:
        if num == 1:
            count += 1          # 1이면 연속 카운트 증가
            max_count = max(max_count, count)  # 최대값 갱신
        else:
            count = 0           # 0이면 연속 카운트 초기화
    return max_count

3-3. 배열의 중복 제거 (Remove Duplicates from Sorted Array)

정렬된 배열에서 중복 원소를 제거하고 새로운 배열 길이를 구하는 문제입니다.

풀이 전략: 두 포인터를 사용해 중복이 아닌 값만 앞으로 옮겨 효율적으로 처리.
시간복잡도는 O(n).

def remove_duplicates(nums):
    if not nums:
        return 0

    i = 0  # 중복 없는 배열의 마지막 인덱스
    for j in range(1, len(nums)):
        if nums[j] != nums[i]:  # 중복이 아니면
            i += 1
            nums[i] = nums[j]  # 중복 없는 배열 뒤에 값 넣기

    return i + 1  # 길이는 인덱스 + 1

3-4. 문자열 회문 검사 (Valid Palindrome)

문자열이 회문인지 확인하는 문제입니다. 영숫자만 고려하며 대소문자는 무시합니다.

풀이 전략: 투 포인터를 양 끝에 두고 문자가 유효한지 확인하며 비교.
시간복잡도는 O(n).

def is_palindrome(s):
    left, right = 0, len(s) - 1

    while left < right:
        # 왼쪽 문자가 영숫자가 아니면 건너뛰기
        while left < right and not s[left].isalnum():
            left += 1
        # 오른쪽 문자가 영숫자가 아니면 건너뛰기
        while left < right and not s[right].isalnum():
            right -= 1

        # 대소문자 무시하고 비교
        if s[left].lower() != s[right].lower():
            return False

        left += 1
        right -= 1

    return True

3-5. 중복 없는 가장 긴 부분 문자열 길이 (Longest Substring Without Repeating Characters)

중복 문자가 없는 가장 긴 부분 문자열의 길이를 찾는 문제입니다.

풀이 전략: 슬라이딩 윈도우 + 해시셋으로 중복 문자 관리하며 윈도우 크기를 조절.
시간복잡도는 O(n).

def length_of_longest_substring(s):
    char_set = set()  # 현재 윈도우 내 문자 집합
    left = 0          # 슬라이딩 윈도우 왼쪽 인덱스
    max_len = 0       # 최대 길이

    for right in range(len(s)):
        # 현재 문자가 이미 있으면 왼쪽부터 중복 제거
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])  # 중복 없으면 추가
        max_len = max(max_len, right - left + 1)  # 최대 길이 갱신

    return max_len

3-6. 문자열 압축 (String Compression)

연속으로 반복되는 문자를 압축하여 "문자 + 개수" 형태로 변환하는 문제입니다.

풀이 전략: 문자열을 순회하면서 연속된 문자의 개수를 세고, 문자와 개수를 결과에 추가.
시간복잡도는 O(n).

def compress_string(s):
    if not s:
        return ""

    result = []  # 압축 결과를 저장할 리스트
    count = 1    # 현재 문자 반복 개수

    for i in range(1, len(s)):
        if s[i] == s[i-1]:
            count += 1   # 이전 문자와 같으면 카운트 증가
        else:
            # 문자와 반복 수(1인 경우 생략) 추가
            result.append(s[i-1] + (str(count) if count > 1 else ""))
            count = 1    # 카운트 초기화

    # 마지막 문자 처리
    result.append(s[-1] + (str(count) if count > 1 else ""))

    return "".join(result)  # 리스트를 문자열로 합치기

3-7. 배열 회전 (Rotate Array)

배열을 오른쪽으로 k칸 회전시키는 문제입니다.

풀이 전략: 배열 슬라이싱을 이용하여 효율적으로 회전.
시간복잡도는 O(n), 추가 공간은 O(n) (슬라이싱에 의함).

def rotate(nums, k):
    k %= len(nums)  # k가 배열 길이보다 크면 나머지 연산으로 조정
    # 뒤쪽 k개를 앞으로, 나머지는 뒤로 붙이기
    nums[:] = nums[-k:] + nums[:-k]

3-8. 아나그램 판별 (Valid Anagram)

두 문자열이 아나그램인지 (서로 문자를 재배열해서 같은지) 확인하는 문제입니다.

풀이 전략: 두 문자열의 문자 빈도 수를 비교.
시간복잡도는 O(n).

from collections import Counter

def is_anagram(s, t):
    # 두 문자열의 문자 개수를 비교해서 같으면 True
    return Counter(s) == Counter(t)

3-9. 부분 배열 합이 k인 경우의 수 (Subarray Sum Equals K)

연속된 부분 배열들의 합이 k가 되는 경우의 개수를 구하는 문제입니다.

풀이 전략: 누적합과 해시맵을 이용해 효율적으로 찾음.
시간복잡도는 O(n).

def subarray_sum(nums, k):
    count = 0               # 결과 개수
    prefix_sum = 0          # 누적합
    hashmap = {0: 1}        # 누적합 빈도 (합이 0인 경우 1회 포함)

    for num in nums:
        prefix_sum += num
        # 현재 누적합에서 k를 뺀 값이 해시맵에 있으면 해당 개수만큼 결과 증가
        if prefix_sum - k in hashmap:
            count += hashmap[prefix_sum - k]

        # 현재 누적합 빈도 증가
        hashmap[prefix_sum] = hashmap.get(prefix_sum, 0) + 1

    return count

4. 배열 & 문자열 활용 팁

• 배열은 인덱스 접근이 빠르므로 정렬, 이진 탐색 등에 적합합니다.
• 문자열 문제는 슬라이딩 윈도우, 투 포인터, 해시맵 등으로 효율적으로 해결할 수 있습니다.
• 문자열이 불변인 언어에서는 문자열을 리스트로 변환하여 조작 후 다시 문자열로 변환하는 것이 성능에 유리합니다.
• 부분 문제를 쪼개서 푸는 분할 정복, 동적 프로그래밍 문제도 배열/문자열 기반이 많습니다.
• 문제에 맞는 자료구조와 알고리즘을 적절히 조합하는 것이 중요합니다.