[Python] 문자열

※ 파이썬에서 문자열은 call by value 방식으로 동작한다, 반면에 리스트는 call by reference 방식으로 동작한다.

문자열 분할 - split( )

python에서는 문자열을 split() 함수에 아무런 파라미터를 넣지않고 실행하면 띄어쓰기 혹은 개행문자에 맞춰 문자열을 나눈 후, 리스트에 넣어준다. spilt() 함수는 괄호 안에 매개변수에 따라 사용법이 다양하다. 

1. 문자열.split() : 문자열에 있는 각각의 문자를 순서대로 나눈 후 리스트에 담는다.
2. 문자열.split('구분자') : 괄호 안에 파라미터로 구분자를 넣어주면 구분자를 기준으로 문자열을 나누어준다.
3. 문자열.split('구분자', 분할 횟수) :구분자에 따라 앞에서 부터 분할 횟수만큼만 나누고, 나머지는 나누지 않고 리스트의 마지막 항목으로 채워 반환
4. 문자열.split(sep='구분자', maxsplit=분할 횟수) : sep 과 maxsplit은 파라미터 명이며, 바로 위 코드와 동일한 역할

ex) baekjoon-1541

https://www.acmicpc.net/problem/1541

1541번: 잃어버린 괄호

arr = input().split('-')
s= 0
for i in arr[0].split('+') :
  s += int(i)
for i in arr[1:] :
  for j in i.split('+') :
    s-=int(j)
print(s)

 

알고리즘 구현 부분에서 문자열에 관련하여 문제가 출제되고 있다. 그중 문자열에서 각각의 단어가 문자(str)인지,

숫자(integer)인지 물어보는 문제가 많다. python에서 이런 경우에는 isalpha와 isdigit 함수를 사용하면 된다.\

알파벳인지 확인하기(isalpha) 

isalpha()는 문자열의 구성이 알파벳인지에 대해서 확인하는 방법이다 . isalpha()의 사용법은 문자열.isalpha()이다. 주의점은 문자열에 숫자 및 공백이 포함되어 있으면 False를 리턴한다.

숫자인지 확인하기(isdigit)

isdigit()는 문자열의 구성이 모두 숫자인지 확인하는 메서드이다. isdigit()의 사용방법은 문자열.isdigit()이다. 모든 문자가 숫자로 이루어져 있다면 True 아니면 False를 반환한다.

ex) facebook interview (문자열 재정렬)

[문제]
알파벳 대문자와 숫자(0 ~ 9)로만 구성된 문자열이 입력으로 주어집니다. 이때 모든 알파벳을 오름차순으로 정렬하여

이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력합니다.

예를 들어 K1KA5CB7 이라는 값이 들어오면 ABCKK13을 출력합니다.

[입력 조건]
1. 첫째 줄에 하나의 문자열 S가 주어집니다. (1 <= S의 길이 <= 10,000)

[출력 조건]
첫째 줄에 문제에서 요구하는 정답을 출력합니다.

[메모리 제한]
128MB

[시간 제한]
1초

<입력 예시 1>
K1KA5CB7

<출력 예시 1>
ABCKK13

<입력 예시 2>
AJKDLSI412K4JSJ9D

<출력 예시2>
ADDIJJJKKLSS20

 

문자열이 입력되었을 때 문자를 하나씩 확인한 뒤에 , 숫자인 경우 따로 합계를 계산하고, 알파벳인 경우 별도의 리스트에 저장한다. 그래서 결과적으로 리스트에 저장된 알파벳들을 정렬해 출력하고 , 합계를 뒤에 붙여서 출력하면 된다.

import sys
input = sys.stdin.readline
S = input()
arr = []
for i in S :
  arr.append(i)
sum_val = 0
new_arr = []
for i in arr :
  if i.isalpha() :
    new_arr.append(i)
  elif i.isdigit() :
    sum_val += int(i)

new_arr.sort()
new_arr.append(str(sum_val))

for i in new_arr :
  print(i,end="")

문자열 길이 구하기 - len()

str = "Hello"
length = len(str)
print(length)  # 출력: 5

문자열 선택 -  indexing ,slicing

str = "Hello, World!"
print(str[0])  # 출력: H
print(str[7])  # 출력: W
print(str[-1]) # 출력: !

print(str[0:5]) # 문자열의 첫 5글자 선택 / 출력: Hello
print(str[7:]) # 문자열의 7번째 글자부터 끝까지 선택 / 출력: World!
print(str[:5]) # 문자열의 처음부터 5번째 글자 전까지 선택 / 출력: Hello
print(str[:-2]) # 문자열의 끝에서 두 번째 글자까지 선택 / 출력: Hello, Worl
print(str[::2]) # 문자열의 처음부터 끝까지 2칸씩 띄어서 선택 / 출력: Hlo ol!

문자열 공백 제거 - strip()

str = "  Hello World  "
print(str.strip())  # 출력: Hello World

문자열 치환 - replace()

str = "I like apples"
result = str.replace("apples", "bananas")
print(result)  # 출력: I like bananas

문자열 특정 문자 위치 찾기 - find()

str = "Hello World"
index = str.find("World")
print(index)  # 출력: 6

문자열 합치기 - join()

list_of_str = ["apple", "banana", "cherry"]
result = ", ".join(list_of_str)
print(result)  # 출력: apple, banana, cherry

문자열 문제 유형

• 문자열 비교 및 정렬
  • 회문검사(Palindrome)
    • 문자열이 회문인지 검사를 위한 투 포인터 방식을 사용
    • 회문의 개념은 level 과 같이 앞/뒤로 동일하게 읽히는 문자를 뜻합니다.
    • 주어진 문자열에서 indexing을 활용하여 문자를 가져와 일치를 확인해야 한다

s = "level"
is_palindrome = True
idx = 0
end = len(s) // 2

while idx < end:
    if s[idx] != s[len(s) - idx - 1]:
        is_palindrome = False
        break
    idx += 1

print(is_palindrome)
# s == s[::-1]

• 애너그램(Anagram)
  • 애너그램이란 두 문자열의 구성 문자열이 모두 같은 문자열을 뜻
  • 문자열의 구성이 같지만 순서가 다른 문자열( listen과 silent)
  • 접근 방식은 두 문자열의 구성 내용이 같음으로 문자열을 정렬한 후 비교

def are_anagrams(str1, str2):
    return sorted(str1) == sorted(str2)

# 테스트
print(are_anagrams("listen", "silent"))  # 출력: True

• 중복문자 제거
  • 주어진 문자열에서 동일한 문자를 제거하는 문제로 Set자료구조를 사용하면 해결이 가능
  • 중복없는 데이터의 집한인 Set에 데이터를 추가하면 자연스레 중복이 제거

def remove_duplicates(s):
    return ''.join(set(s))

# 테스트
print(remove_duplicates("banana"))  # 출력: "ban"

• 최대 반복문자 찾기
  • 주어진 문자열에서 최대로 반복된 문자를 찾는 문제로 Counter 를 사용
  • 해시 가능한 객체를 세기 위한 딕셔너리의 하위 클래스
  • 주로 데이터의 빈도수를 계산하는 데 유용

from collections import Counter

def most_frequent_char(s):
    if not s:
        return None
    
    counter = Counter(s)
    most_common_char, _ = counter.most_common(1)[0]
    return most_common_char

# 테스트
s = "banana"
print(most_frequent_char(s))  # 출력: "a"

문자열 알고리즘

트라이(Trie) 자료구조

• 문자열 검색을 효율적으로 수행하기 위해 사용되는 트리 기반의 자료구조
• 문자열의 집합을 저장하고, 빠르게 검색, 삽입, 삭제할 수 있도록 설계
• 사전이나 접두사 검색과 같은 응용 분야에서 유용
• 루트에서부터 각 리프 노드까지의 경로가 하나의 문자열을 형성
• 트라이의 기본 개념
  • 각 노드: 문자를 저장하며, 각 간선은 다음 문자로의 이동을 나타낸다
  • 루트 노드: 빈 문자열을 나타낸다
  • 삽입: 문자열을 추가할 때, 각 문자를 따라 내려가면서 노드를 추가
  • 검색: 문자열을 찾을 때, 각 문자를 따라 내려가면서 노드를 탐색
• 트라이의 장점
  • 빠른 검색: 문자열 길이에 비례하는 시간 복잡도로 검색할 수 있습니다.
  • 메모리 효율성: 공통 접두사를 공유하여 메모리 사용을 줄일 수 있습니다.
  • 자동 완성 및 사전 기능: 접두사를 기준으로 문자열을 빠르게 찾을 수 있습니다.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search(self, word: str) -> bool:
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end_of_word

    def starts_with(self, prefix: str) -> bool:
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

# 테스트 코드
trie = Trie()
trie.insert("apple")
print(trie.search("apple"))  # 출력: True
print(trie.search("app"))    # 출력: False
print(trie.starts_with("app")) # 출력: True
trie.insert("app")
print(trie.search("app"))    # 출력: True
trie.delete("apple")
print(trie.search("apple"))  # 출력: False

KMP 알고리즘

• 패턴 매칭을 위한 효과적인 알고리즘
• 불필요한 비교를 줄여 패턴 검색을 빠르게 수행할 수 있음
• LPS 배열을 사용하여 다음 비교 위치를 결정함으로 불필요한 비교 제거 

※ LPS 배열 : 패턴 내 부분 문자열의 접두사와 접미사가 일치하는 최대길이 저장

def compute_lps_array(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0
    i = 1

    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    lps = compute_lps_array(pattern)

    i = 0  # text의 인덱스
    j = 0  # pattern의 인덱스

    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1

        if j == m:
            print(f"Found pattern at index {i - j}")
            j = lps[j - 1]
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1

if __name__ == "__main__":
    text = "ABABDABACDABABCABAB"
    pattern = "ABABCABAB"
    kmp_search(text, pattern)  # 출력: Found pattern at index 10

참고 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 )

https://github.com/ndb796/python-for-coding-test

GitHub - ndb796/python-for-coding-test: [한빛미디어] "이것이 취업을 위한 코딩 테스트다 with 파이썬" 전체