01. 배열과 문자열

문제 1.5

하나 빼기 : 문자열을 편집하는 방법에는 세 가지 종류가 있다. 문자 삽입, 문자 삭제, 문자 교체. 문자열 두 개가 주어졌을 때, 문자열을 같게 만들기 위한 편집 횟수가 1회 이내인지 확인하는 함수를 작성하라.

풀어보기

문자열의 등장 횟수를 비교하는 방식으로 접근했지만, 생각해보니 그렇게 되면 등장횟수는 같은데 배열이 다른 문자열들을 고려할 수 없기 때문에 다른 방식으로 접근 해야한다.

1. 문자열의 길이를 비교하고, 각 케이스 별로 문자열을 순회하면서 비교하며 판단한다.

먼저 각 문자열의 길이를 비교한다.

두 문자열의 길이 차이가 2이상이면 1회의 편집으로는 절대 같아질 수 없다.

두 문자열의 길이 차이가 1이거나 0이면 서로 다른 문자가 1개만 존재해야한다.

길이가 1차이 나는 경우과 길이가 같은 경우를 나눠서 생각한다.

길이가 같은 경우는 문자열을 하나씩 순회하면서 같은 인덱스의 값을 비교하고 서로 다른 문자열의 개수를 센다.

길이가 1차이 나는 경우는 문자열을 하나씩 순회하면서 같은 인덱스의 값을 비교하고 서로 다른 문자열이 나왔을 경우

길이가 짧은 문자열의 i번째 문자와 길이가 긴 문자열의 i+1번째 문자열의 값을 비교한다. 이때 또 한번 다른 문자열이 등장하면 편집횟수가 1이상이다.

# 1.5 하나 빼기

from collections import Counter

s1 = "zale"
s2 = "plze"

def solution(s1, s2):
    longer = ""
    shorter = ""

    if len(s1) == len(s2):
        pass
    else:
        if len(s1) - len(s2) > 0:
            longer, shorter = s1, s2
        elif len(s1) - len(s2) < 0:
            longer, shorter = s2, s1

    if len(longer) - len(shorter) >= 2:
        return False
    else:
        cnt = 0
        if len(longer) == 0:
            for i in range(len(s1)):
                if s1[i] != s2[i]:
                    cnt += 1
                if cnt >=2:
                    return False
        else:

            for i in range(len(shorter)):
                if cnt == 1:
                    if longer[i+1] != shorter[i]:
                        print(longer[i+1], shorter[i])
                        return False

                if longer[i] != shorter[i]:
                    cnt += 1


    return True


solution("pale", "bake")

해답

1. 삽입과 삭제를 하나로 합치고, 교체연산을 확인한다.

한번의 교체연산으로 같게 만들 수 있다는 의미는 두 문자열이 하나의 문자열만 다르고 모두 같다는 것을 의미한다. 삽입 혹은 삭제 연산으로 같게 만들 수 있다는 의미는 짧은 문자열 특정 위치에 공백을 포함하면 나머지 문자들은 모두 같다는 것을 의미한다. 이 중 어떤 연산을 사용할 것인지는 두 문자열의 길이를 보고 판단 할 수 있다.

두 문자열의 길이가 같다면 교체 연산, 두 문자열의 길이가 다르면 삽입 혹은 삭제 연산을 통해 다른 문자가 몇번 등장하는지 확인한다.

01. 배열과 문자열

문제 1.1

중복이 없는가 : 문자열이 주어졌을 때, 이 문자열에 같은 문자가 중복되어 등장하는지 확인하는 알고리즘을 작성하라. 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘 또한 고민하라.

풀어보기

1. 집합(SET) 자료형을 사용한다.

집합 자료형의 특성은 중복을 허용하지 않는다. 따라서 주어진 문자열을 집합 자료형으로 변환하여 최초 문자열의 길이와 변환된 집합 자료형의 길이를 비교한다. 길이가 늘어나는 것은 불가능하고 길이가 같다면, 중복이 없는 것이고 길이가 줄어들었다면 중복된 문자열이 제거된 만큼 길이가 줄어든 것이므로 중복된 문자열이 등장한 것이다.

# python
str = 'absas'    # 문자열 선언
def isUniqueChar(str):    # 중복된 문자열이 있으면 False, 중복되지 않고 유니크하다면 True
    str_set = set(str)    # 문자열을 집합 자료형으로 변환
    if len(str) == len(str_set):
        return True
    else:
        return False

print('naver', isUniqueChar('naver'))
print('kakao', isUniqueChar('kakao'))

# ----------------------결과--------------------------------------------------------------
# naver True
# kakao False

2. 각 문자를 순차적으로 다른 문자들과 비교한다.

문자열의 0번째 문자를 1부터 n번째 문자열과 순차적으로 비교한다. 그리고 1번째 문자를 2부터 n번째 문자열과 비교한다. 이런식으로 (n-1)~n번째 까지 반복하여 같은 문자열이 나오는 즉시 중복이 있는 문자열로 판단한다. 시간 복잡도는 O(N^2). 문제에서 요구한 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘

# python
def isUniqueChar(str):     # 중복된 문자열이 있으면 False, 중복되지 않고 유니크하다면 True
    for i in range(len(str)):
        if str[i] in str[i+1:]:    # 중복된 것 있는지 확인
            return False
    return True
print('naver', isUniqueChar('naver'))
print('kakao', isUniqueChar('kakao'))

# ---------------------결과--------------------------------------------------------------
# naver True
# kakao False

모법답안

먼저 문자열이 ASCII 문자열인지 유니코드 문자열인지 확인 하는 센스. 이에 따라 저장 공간 크기가 달라질 수 있다. 일단 문자열이 아스키 코드 라고 가정했을 때 풀이. 아스키코드와 유니코드 이해

1. 표현 가능한 범위만큼 배열을 선언하여 배열의 인덱스에 접근하는 횟수를 통해 중복을 판단한다.

코드의 시간 복잡도는 O(N). N은 문자열의 길이. 하지만 아스키 코드가 표현 가능한 갯수를 초과하여 순회하지 않기 때문에 O(1)이라고 볼 수도 있다.

boolean isUniqueChars(String str) {
    if (str.length() > 128)
    {
        return false;    // 아스키 코드 문자의 개수 128. 이를 넘어가면 반드시 중복이 발생한다.
    }
    boolean[] char_set = new boolean[128];    // 128길이의 배열 선언

    for(int i = 0; i < str.length(); i++)    // 문자열의 길이만큼 반복
    {
        int val = str.charAt(i);    // i번째 문자열의 아스키 코드 값을 val변수에 저장
        if (char_set[val] == true)
        {
            return false;    // 현재 문자열과 같은 아스키코드를 가진 문자가 이미 존재했었다.
        }
    }
    return true;    // 겹친 것이 하나도 없다면 
    }

2. 비트벡터를 사용

비트벡터를 사용하여 문자열 중복 판단하기

3. 문자열을 정렬한 뒤 인접한 문자열을 비교하는 방식으로 판단한다.

정렬을 할 때 O(nlogn)의 시간이 소요된다. 정렬 할 때 많은 알고리즘이 공간을 추가로 사용한다는 것도 기억해라. 문제에서 요구한 자료구조를 추가로 사용하지 않고 풀 수 있는 알고리즘