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.3

URL화 : 문자열에 들어 있는 모든 공백을 '%20'으로 바꿔 주는 메서드를 작성하라. 최종적으로 모든 문자를 다 담을 수 있을 만큼 충분한 공간이 이미 확보되어 있으며 문자열의 최종 길이가 함께 주어진다고 가정해도 된다.

풀어보기

1. 문자열 순회하면서 이어붙이기

단순하게 문자열을 하나씩 확인하며 공백일 때는 '%20', 공백이 아닐 때는 기존 문자열을 덧붙여서 새로운 결과 문자열을 만들어 리턴한다.

# 1.3 URL화
s = "Mr John Smith"

def toURL(str):
    newS = ""
    for x in s:
        if x == ' ':
            newS += "%20"
        else:
            newS += x
    return newS

print(toURL(s))

# -결과----------------------------------------------------------------------------------
# Mr%20John%20Smith

수정된 풀이(하나의 문자열로 편집하여 리턴)

# 1.3 URL화
s = "Mr John Smith"

def toURL(str):
    n = len(str)

    # 마지막 부터 첫번째까지 순회
    for i in range(len(str)-1, 0-1, -1):
        if str[i] == ' ':
            str = str[:i] + "%20" + str[i+1:]

    return str

print(toURL(s))
# -결과----------------------------------------------------------------------------------
# Mr%20John%20Smith

해답

문제에 정확히 나오지 않았지만 주의해야할 사항은 이 문제는 새로운 문자열을 만들어 변환 하는 것이 아니라, 기존의 문자열을 가지고 조작하여 풀어야 하는 문제!

따라서 문자열을 앞에서 부터 편집하는 것이 아니라, 뒤에서 부터 편집한다. 앞에서 부터 편집하면 아직 편집해야 할 문자가 덮어쓰여질 우려가 있기 때문이다.

1. 공백의 갯수를 세고, 문자열을 뒤에서부터 거꾸로 편집하며 복사해나간다. 

void replaceSpaces(char [] str, int trueLength){    // truelength는 주어진 문자열의 길이
    int spaceCount = 0, index, i = 0;
    for (i = 0; i < trueLength; i++){
        if (srt[i] == ' '){
            spaceCount++;        // 공백의 숫자를 센다
        }
    }

    index = trueLength + spaceCount * 2; // 문자열의 길이에다가 URL화로 인해 치환될 문자열의 길이를 더한 값이 index

    if (trueLength < str.length){ // 만약 주어진 문자열의 길이가 실제 문자열의 길이보다 작다면 중간에 종료
        str[trueLength] = '\0'
    }
    // str[trueLength] -> str[index] 로 문자열 복사
    for (i = trueLength - 1; i>=0; i--){
        if (str[i] == ' '){
            str[index - 1] == '0';
            str[index - 2] == '2';
            str[index - 3] == '%';
            index = index-3;
        }
        else{
            str[index - 1] = str[i];
            Index--;
        }
    }
}

01. 배열과 문자열

문제 1.2

순열 확인 : 문자열 두 개가 주어졌을 떄 이 둘이 서로 순열 관계에 있는지 확인하는 메서드를 작성하라.

풀어보기

순열 관계라는 것은 두 문자열에서 사용된 문자는 같은데 문자의 순서만 다른 형태라는 것을 의미한다.

1. 정렬 후 리스트 비교

먼저 두 문자열의 길이가 같은지 확인한다. 길이가 다르면 순열 관계가 아니라고 판단한다.

길이가 같다면 두 문자열을 정렬하여 두 개의 리스트가 같은지 비교연산자를 통해 비교한다.

# 1.2 순열 확인

def istnsduf(str1, str2):
    if len(str1) == len(str2):

        listStr1 = list(str1)
        listStr2 = list(str2)
        listStr1.sort()
        listStr2.sort()

        if listStr1 == listStr2:
            return True
    return False

print('ABC', 'AER', istnsduf('ABC', 'AER'))
print('CBS', 'SCB', istnsduf('CBS', 'SCB'))

# -결과----------------------------------------------------------------------------------
# ABC AER False
# CBS SCB True

모법답안

먼저 확인 해야 할 사항은. 대소문자는 구별할 것인지? 그리고 공백은 어떻게 볼 것인지?

여기서는 대소문자를 구별하고 공백을 하나의 문자열로 판단하기로 한다.

1. 정렬하여 비교하기

순열 관계의 문자열은 정렬하면 같은 문자열이 되기 때문에 정렬 후 두 문자열을 비교해주면 된다. 단순하고 이해하기 쉽다는 측면에서 좋은 풀이이지만, 효율성 측면에서는 최적은 아니다.

2. 문자열에 포함된 문자의 출현 횟수가 같은지 비교

순열 관계의 문자열은 동일한 문자가 동일한 횟수로 출현한다는 특징이 있다. 이를 각각 문자열에서 기록하고 이 횟수를 비교한다

1번 풀이는 O(NlogN) 의 시간 복잡도, 2번 풀이는 O(N)의 시간 복잡도가 걸릴 것 같다!