[쓰면서 익히는 알고리즘과 자료구조](2) 문자열(String)

 

파이썬에서 문자열은 처음 생성된 이후 변경 불가능한 불변(immutable) 객체이다.

string + string = 새로운 string 객체

2.3 회문(Palindrome) 확인

문자열 알고리즘 문제 중 빈번하게 등장하는 회문에 관한 간단한 문제를 풀어보자.

문자열이 회문인지 아닌지 확인하자, 알파벳과 숫자로 이루어져있으며, 알파벳은 대/소문자를 구분하지 않는다.

def is_palindrome(s: str) -> bool:
    i = 0
    j = len(s) - 1
    
    s = s.lower()
    
    while i < j:
        while i < j:
            if s[i].isalnum():
                break
            i += 1
        
        while i < j:
            if s[j].isalnum():
                break
            j -= 1
        
        if s[i] != s[j]:
            return False
        
        i += 1
        j -= 1
    
    return True

def is_palindrome(s: str) -> bool:
    s = "".join(list(filter(str.isalnum, s))).lower()
    
    return s == s[::-1]

2.4 그룹 애너그램(anagram)

애너그램은 단어의 문자들 위치를 변경하여 다른 단어를 만들어 내는 놀이에서 나온 개념이다.

문자열 리스트가 주어지는데 리스트에 있는 문자열을 검사해 서로 같은 애너그램을 가지는 문자열을 그룹으로 묶어보자

아이디어(Ideas)

일반적으로 애너그램을 확인하는 방법은 문자열을 정렬하여 비교하거나 문자열이 가지는 각 문자의 개수가 같은지 확인하는 방법을 사용한다. → 순서대로 뒤집는게 아니라 그냥, 같은 알파벳 구성만 가지고 있으면 되는구나..

import collections

def group_anagrams(strs: list[str]) -> list[list[str]]:
    hashmap = collections.defaultdict(list)

    for s in strs:
        # 키를 정렬된 문자열로 하고, s를 append 하는데 기본값이 list 이므로
        # 키가 없었을 경우에는 빈 배열이 생성되어 빈 배열에 append 하게 됨
        # defaultdict(int) 하게 되면 기본값이 0 으로 지정됨
        hashmap["".join(sorted(s))].append(s)

    return hashmap.values()

튜플을 키로 쓸 수 있음 👍

import collections

def group_anagrams(strs: list[str]) -> list[list[str]]:
    hashmap = collections.defaultdict(list)

    # 정렬을 할 필요가 없기 때문에 더 좋음
    for s in strs:
        count = [0] * 26

        for ch in s:
            count[ord(ch) - ord('a')] += 1

        hashmap[tuple(count)].append(s)

    return hashmap.values()

2.5 IPv4 / IPv6 검증 시스템

문자열을 파싱(분석)하고 유효한지 검사하는 경우가 있다.

입력받은 문자열이 유효한 IPv4 인지, IPv6 인지 확인하는 함수를 확인해보자.

IPv4 주소는 점(.) 으로 분리된 4개의 10진수로 구성되며 각 숫자들은 0에서 255까지의 범위를 가진다

IPv6 주소는 IPv4 보다 더 복잡한 구성으로 이루어진다. IPv4 에서는 점(.) 으로 구분되어 있는 숫자가 콜론(:) 으로 구분되며 숫자는 10진수가 아니라 16진수로 구성된다.

그리고 4자리 숫자 8개의 그룹으로 표시된다.

2020:0bc3:0000:0000:853e:0777:1234 는 유효한 IPv6 숫자

Constraints

IPv4

1. 점으로 숫자 구분
2. 점으로 구분된 숫자는 4개
3. 각 숫자의 범위는 0에서 255 - 10진수
4. 0을 제외하고 0으로 시작하는 숫자는 없다.
   1. 01, 00, 023 같은 숫자는 유효하지 않다.

IPv6

1. 콜론으로 숫자 구분
2. 콜론으로 구분된 숫자는 8개
3. 각 숫자는 16진수 000에서 FFFF 까지
4. 각 숫자는 4자리를 채우기 위해서 0으로 시작할 수 있음
5. 0000 의 경우에는 0으로 사용가능
6. 콜론 사이에 숫자가 없으면 유효한 IPv6 가 아님
7. 각 숫자는 4자리를 넘어서 사용할 수 없음

Ideas

• 일일이 조건을 확인
• 정규표현식으로 해결

import string

def check_ip_v4(ipv4: str) -> str:
    ip_nums = ipv4.split(".")
    
    for num in ip_nums:
        if len(num) == 0 or len(num)> 3:
            return 'Neither'

        if (len(num) != 1 and num[0] == '0') or not num.isdigit() or int (num) > 255:
            return 'Neither'

    return 'IPv4'

def check_ip_v6(ipv6: str) -> str:
    ip_nums = ipv6.split(":")
    
    for num in ip_nums:
        if len(num) == 0 or len(num) > 4 or not all(c in string.hexdigits for c in num):
            return 'Neither'
    
    return 'IPv6'

def valid_ip_address(ip: str) -> str:
    if ip.count('.') == 3:
        return check_ip_v4(ip)
    elif ip.count(':') == 7:
        return check_ip_v6(ip)
    
    return 'Neither'

import re

def valid_ip_address(ip: str) -> str:
    ipv4_pattern = r'(\\d|[1-9]\\d|1\\d\\d|2[0-4]\\d|25[0-5])'

    ipv4_re = re.compile(r'^({p}\\.){{3}}{p}$'.format(p=ipv4_pattern))

    if ipv4_re.match(ip):
        return "IPv4"

    ipv6_patter = r'([0-9a-f]{1,4})'

    ipv6_re = re.compile(r'^({p}:){{7}}{p}$'.format(p=ipv6_patter), re.IGNORECASE)

    if ipv6_re.match(ip):
        return "IPv6"

    return 'Neither'