실습_2. 효율적인 프로그램이란?

실습

중복된 수 제거하기

0보다 큰 정수들이 있는 리스트가 주어집니다. 이 리스트는 작은것부터 큰 순서대로 오름차순 정렬이 되어있으며, 중복을 포함합니다. 이 리스트에서 중복된 수를 없애고 정렬되어있는 리스트를 출력해 봅시다.

예를 들어 [1, 1, 2, 2, 2, 2, 5, 7, 7, 8] 이 입력되었다면 중복되어있는 ‘1’ 1개, ‘2’ 3개, ‘7’ 1개를 제거하고 [1, 2, 5, 7, 8]을 출력하면 됩니다.

def removeDuplicate(nums):
    result = []
    a = 0
    for num in nums:
        if num > a:
            a = num
            result.append(a)
    
    return result
def main():
    print(removeDuplicate([1, 1, 2, 2, 2, 2, 5, 7, 7, 8]))

if __name__ == "__main__":
    main()

0 이동시키기

여러개의 0과 양의 정수들이 섞여 있는 배열이 주어졌다고 합시다. 이 배열에서 0들은 전부 뒤로 빼내고, 나머지 숫자들의 순서는 그대로 유지한 배열을 반환하는 함수를 만들어 봅시다.

예를 들어서, [0, 8, 0, 37, 4, 5, 0, 50, 0, 34, 0, 0] 가 입력으로 주어졌을 경우 [8, 37, 4, 5, 50, 34, 0, 0, 0, 0, 0, 0] 을 반환하면 됩니다.

이 문제는 공간 복잡도를 고려하면서 풀어 보도록 합시다. 공간 복잡도 O(1)으로 이 문제를 풀 수 있을까요?

def moveZerosToEnd(nums):
    currentPosition = 0
    for i in range(len(nums)):
        if nums[i] != 0:
            nums[currentPosition] = nums[i]
            nums[i] = 0
            currentPosition+=1
    return nums

def main():
    print(moveZerosToEnd([0, 8, 0, 37, 4, 5, 0, 50, 0, 34, 0, 0]))

if __name__ == "__main__":
    main()

배열의 회전

배열을 회전 시켜봅시다. 정수들이 포함되어 있는 배열과, 숫자 k가 입력으로 주어집니다. 이때 해당 배열을 k 만큼 회전 시켜 봅시다.

예를 들어서, [1, 2, 3, 4, 5, 6, 7, 8, 9] 와 4가 입력으로 주어졌을 경우 [6,7,8,9,1,2,3,4,5] 를 반환하면 됩니다.

• k 는 배열의 길이 n 보다 작다고 가정합시다.
• 다양한 방법으로 풀어 보도록 합시다.
• (추가) 공간 복잡도 O(1)으로 풀 수 있는 방법도 생각 해 봅시다. 이때 주어진 함수 partialReverse를 활용해도 됩니다.

def rotateArray(nums, k):

    nums = nums[len(nums) - k:] + nums[:len(nums) - k]
    return nums

    # partialReverse를 쓴다면 다음과 같이도 해결 가능
    # partialReverse(nums, 0, len(nums) - 1)
    # partialReverse(nums, 1, K-1)
    # partialReverse(nums, k, len(nums) - 1)

        
def partialReverse(nums, start, end):
    for i in range(0, int((end-start)/2) + 1):
        temp = nums[start + i]
        nums[start+i] = nums[end - i]
        nums[end -i] = temp


def main():
    nums = [1,2,3,4,5,6]
    partialReverse(nums, 1, 4) # [1, 4, 3, 2, 5] 를 반환
    print(nums)
    print(rotateArray([1,2,3,4,5,6,7,8,9], 4)) # [6,7,8,9,1,2,3,4,5] 를 반환
    

if __name__ == "__main__":
    main()

아나그램 탐지

아나그램(Anagram)은 한 문자열의 문자를 재배열해서 다른 뜻을 가지는 다른 단어로 바꾸는 것을 의미합니다.

두 개의 문자열이 주어졌을 때, 서로가 서로의 아나그램인지 아닌지의 여부를 탐지하는 함수를 만들어 보세요.

• elice 와 leice 는 아나그램입니다. True를 리턴해야 합니다.
• cat 과 cap 는 아나그램이 아닙니다. False 를 리턴해야 합니다.
• iamlordvoldemort 와 tommarvoloriddle 은 아나그램입니다. True를 리턴해야 합니다.
• 문자열의 모든 문자는 영어 소문자라고 가정합시다.

def isAnagram(str1, str2):
    dict1 = {}
    dict2 = {}
    
    for i in str1:
        if i in dict1:
            dict1[i]+=1
        else:
            dict1[i]=1
            
    for i in str2:
        if i in dict2:
            dict2[i]+=1
        else:
            dict2[i]=1
   
    if dict1 == dict2:
        return True
    else:
        return False
    
def main():
    print(isAnagram('iamlordvoldemort', 'tommarvoloriddle')) # should return True
    print(isAnagram('cat', 'cap')) #should return False
    
if __name__ == "__main__":
    main()

미션

틀린 문자 찾기

두 개의 문자열이 주어집니다. 이때 두번째 문자열은 첫번째 문자열에 하나의 문자를 추가 한 후, 그 순서를 랜덤하게 뒤섞은 문자입니다. 이때 추가된 문자를 찾아 보도록 합시다.

예를 들어서, apple 과 azlppe 가 주어졌을 경우 추가된 문자는 z입니다.

• 추가된 문자는 하나라고 가정해도 좋습니다.
• 추가된 문자가 이미 리스트에 존재하던 문자 일 수도 있습니다.

def findDifference(str1, str2):
    str1 = list(str1)
    str2 = list(str2)
    str1.sort()
    str2.sort()
    
    for i in range(len(str1)):
        if str1[i] != str2[i]:
            return str2[i]
    return str2[-1]

def main():
    print(findDifference("apple", "azlppe"))
    

if __name__ == "__main__":
    main()

세번째로 큰 숫자 찾아내기

0보다 큰 정수들의 배열이 주어졌다고 합시다. 이 배열에서 세번째로 큰 수를 찾아 내 봅시다.

예를 들어서, [2, 8, 19, 37, 4, 5, 12, 50, 1, 34, 23] 가 입력으로 주어졌을 경우 가장 큰 수는 50, 두번째로 큰 수는 37, 세번째로 큰 수는 34입니다. 따라서 34를 반환해야 합니다.

시간 복잡도를 고려하면서 여러가지 방법으로 문제를 풀어 봅시다.

def thirdMax(nums):
    
    max_1 = 0
    max_2 = 0
    max_3 = 0
    
    for num in nums:
        if max_1 < num:
            max_3 = max_2
            max_2 = max_1
            max_1 = num
        elif max_2 < num:
            max_3 = max_2
            max_2 = num
        elif max_3< num:
            max_3 = num
    
    return max_3

def main():
    print(thirdMax([2, 8, 19, 37, 4, 5, 12, 50, 1, 34, 23])) 
   
    # should return 34

if __name__ == "__main__":
    main()

단어 패턴

문자열(패턴) 하나와 문자열의 배열 하나가 주어집니다.

패턴 문자열의 각각의 문자 하나는, 두번째 문자열 배열의 각각의 문자열 하나에 대응 될 수 있습니다.

해당 배열이 해당 패턴으로 표현 되는지 아닌지의 여부를 확인하는 함수를 만들어 보세요.

예를 들어서, aabb 와 [‘elice’, ‘elice’, ‘alice’, ‘alice’] 가 주어졌을 경우에는 함수가 True를 반환해야 합니다. 이 경우에는 a가 elice에, b가 alice에 대응되도록 하면 배열을 해당 패턴으로 표현 하는 것이 가능하기 때문이죠.

반면, aabb 와 [‘elice’, ‘alice’, ‘elice’, ‘alice’] 가 주어졌을 경우에는 함수가 False를 반환해야 합니다.

• 모든 문자는 영어 소문자라고 가정합니다.

def wordPattern(pattern, strList):
    dicts = {}
    
    for i in range(len(pattern)):
        if pattern[i] in dicts:
            if dicts[pattern[i]] != strList[i]:
                return False
        else:
            dicts[pattern[i]] = strList[i]
        print(dicts)
    return True

def main():
    print(wordPattern("acb", ["x",'x','y'])) # should return True
    print(wordPattern("abcbc", ["x", "z", "y", "z","y"])) # should return False
    

if __name__ == "__main__":
    main()