알고리즘을 위한 자료구조 - 실력 테스트

중복되지 않은 하나의 숫자 찾아내기

숫자들의 배열이 주어집니다. 이 배열은 길이 2n - 1을 가지며, 1부터 n까지의 숫자로 이루어져있습니다. 모든 숫자가 배열에 두번씩 나타납니다. 그런데, 딱 하나의 수가 배열에 단 한번 등장합니다. 이 중복되지 않는 숫자를 찾아내어 보세요.

예를 들어서, [1, 5, 3, 1, 2, 6, 4, 5, 2, 6, 3] 를 살펴봅시다. 배열의 길이는 11이며, 따라서 1~6까지의 숫자들이 두번씩 등장합니다. 그런데 4만 한번만 등장했네요.따라서 이 경우에는4를 찾아내면 됩니다.

def findSolo(nums):
    N = len(nums)//2
    arr = [0 for i in range(N+2)]
    
    for i in nums:
        arr[i] += 1
    
    for i in range(1,len(arr)):
        if arr[i] == 1:
            return i
    
    return 0

def main():
	print(findSolo([1, 5, 3, 1, 2, 6, 4, 5, 2, 6, 3]))

if __name__ == "__main__":
    main()

수의 종류 세기

배열 속에 수가 몇 종류 있는지 세어봅시다. 정수들이 중복되어 들어있는 배열이 들어옵니다. 이때 중복을 제외하면 수가 얼마나 있는지 세어봅시다.

예를 들어서, [1, 3, 1, 2, 5, 3, 1, 4, 2, 3]이 입력으로 주어졌을 경우 [1, 2, 3, 4, 5]의 다섯종류가 있으므로 5를 반환하면 됩니다.

# 이 함수를 수정 해 주세요.
def countNums(nums):
    nums.sort()
    
    num = nums[0]
    cnt = 1
    
    for i in nums:
        if num!=i:
            num = i
            cnt+=1
    
    return cnt

def main():
    print(countNums([1, 3, 1, 2, 5, 3, 1, 4, 2, 3])) # 5를 반환해야 합니다.
    
if __name__ == "__main__":
    main()

괄호의 점수

(, ) 의 두개의 문자로만 구성된 올바른 괄호문자열이 입력으로 주어진다고 해 봅시다.

이때, 이 문자열이 다음과 같은 규칙으로 계산했을때 몇점인지 계산해보세요.

올바르지 않은 괄호 문자열은 고려하지 않아도 됩니다.

“()” 은 1점입니다.

‘(‘과 ‘)’ 사이에 n점짜리 문자열이 있다면 2*n점으로 계산됩니다. 예를들어 “(())”은 2점입니다.

둘 이상의 괄호가 나란히 있다면 두 괄호의 점수를 합칩니다. 예를 들어 “()(())”은 3점입니다.

def getParenthesisScore(st):

    arr = []

    cnt = 0
    
    check = False
    for i in st:
        if i == '(':
            cnt += 1
            check =True
        else:
            cnt -= 1
            if len(arr) < cnt + 1:
                while len(arr) < cnt:
                    arr.append(0)
                arr.append(1)
                check = False
            elif check:
                arr[cnt] += 1
                check = False
            elif not check:
                arr[cnt] += 2*arr[cnt+1]
                arr[cnt+1] = 0
        print(cnt)
    print(arr)
    print()
    return arr[0]

def main():
    examples = ["()()(())","(()()())", "(()(()))", "((()())())", "()", "((()))()"] # 4, 6, 10, 1, 5 점이 나와야 합니다.
    for example in examples:
        print(example, getParenthesisScore(example))

    
if __name__ == "__main__":
    main()

하노이의 탑

재귀알고리즘을 이용해 풀 수 있는 문제로는 하노이의 탑 이라는 퍼즐이 있습니다.

3개의 막대가 있고 가장 왼쪽 막대에는 탑의 높이만큼의 원반이 가장큰것부터 차례로 쌓여있습니다.

이 하노이의 탑의 목표는 다음과 같은 조건을 지키면서 가장 왼쪽막대의 원반을 모두 가장 오른쪽으로 이동하는 것 입니다.

한번에는 하나의 원반만 이동할 수 있습니다.

가장위에있는 원반만 이동할 수 있으며 가장 위에만 내려놓을 수 있고 중간에 끼워넣을 수 없습니다.

큰 원반은 작은 원반 위로 갈 수 없습니다.

함수 hanoi에 탑의 높이가 입력으로 들어오면 3번으로 모든 원반을 옮기기 위해 몇번째 기둥의 원반을 몇번째 기둥으로 옮겨야 하는지에 대한 리스트를 반환하는 코드를 작성해 봅시다.

예를 들어 2가 입력으로 들어왔다면 [ (1, 2), (1, 3), (2, 3)]을, 3이 입력으로 들어왔다면 [ (1, 3), (1, 2), (3, 2), (1, 3), (2, 1), (2, 3), (1, 3)] 으로 이동해야 합니다.

def hanoi(height) :
    result = []
    def move(begin, end, height):
    # 여기에 재귀 알고리즘을 구현 해 봅시다.
        if height == 1:
            print(begin, end)
            result.append((begin,end))
            return
        
        move(begin, 6-begin-end, height-1)
        move(begin, end, 1)
        move(6-begin-end , end,  height-1)
        
    move(1, 3, height)
    
    return result
    
    
        
def main():
    print(hanoi(4))

if __name__ == "__main__":
    main()