20200409 알고리즘

1. Valid Parentheses

괄호 쌍 맞추기 strict version

Solution1

class Solution:
    def isValid(self, s: str) -> bool:
        open_set = set(["(", "[", "{"])
        bracket_map = {"(":")","{":"}","[":"]"}
        stack = list()
        for v in s:
            if v in open_set:
                stack.append(v)
            elif stack and v == bracket_map[stack[-1]]:
                stack.pop()
            else:
                return False
        return stack == []

Solution2

class Solution:
    def isValid(self, s: str) -> bool:
        if  len(s) % 2 != 0:
            return False
        else:
            stack = list()
            for v in s:
                if v == '(' or v == '{' or v == '[':
                    stack.append(v)
                else:
                    if not stack:
                        return False
                    else:
                        if v == ')':
                            if stack.pop() != '(':
                                return False
                        elif v == ']':
                            if stack.pop() != '[':
                                return False
                        elif v == '}':
                            if stack.pop() != '{':
                                return False
            if stack:
                return False
            return True

2. 전화번호 목록

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요.

제한 사항

phone_book의 길이는 1 이상 1,000,000 이하입니다.
각 전화번호의 길이는 1 이상 20 이하입니다.

입출력 예제

phone_book	return
[119, 97674223, 1195524421]	false
[123,456,789]	true
[12,123,1235,567,88]	false

입출력 예 설명

입출력 예 #1 앞에서 설명한 예와 같습니다.

입출력 예 #2 한 번호가 다른 번호의 접두사인 경우가 없으므로, 답은 true입니다.

입출력 예 #3 첫 번째 전화번호, “12”가 두 번째 전화번호 “123”의 접두사입니다. 따라서 답은 false입니다.

알림

2019년 5월 13일, 테스트 케이스가 변경되었습니다. 이로 인해 이전에 통과하던 코드가 더 이상 통과하지 않을 수 있습니다.

Solution

def solution(pb):
    book = dict()
    for i in range(len(pb)):
        book[pb[i]] = i

    for i in range(len(pb)):
        for j in range(1, len(pb[i])):
            if pb[i][:j] in book and book[pb[i][:j]] != i:
                return False
    return True

O(n + n*k)

3. 조이스틱

문제 설명

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA

조이스틱을 각 방향으로 움직이면 아래와 같습니다.

▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동

예를 들어 아래의 방법으로 JAZ를 만들 수 있습니다.

- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.

만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.

제한 사항

name은 알파벳 대문자로만 이루어져 있습니다.
name의 길이는 1 이상 20 이하입니다.

입출력 예

name	return
JEROEN	56
JAN	23

Solution

def solution(name):
    size = len(name)
    ch = [0] * size
    cnt = 0
    for i in range(size):
        if name[i] != 'A':
            ch[i] = 1
            cnt += 1
            
    def verticalCheck(target):
        down = ord(target) - 65
        up = 26 - down
        return min(up, down)
    
    def horizonCheck(cur):
        cnt1 = 0
        left = cur
        while True:
            left -= 1
            cnt1 += 1
            if left < 0:
                left = size - 1
            if ch[left] == 1:
                break
                
        cnt2 = 0
        right = cur
        while True:
            right += 1
            cnt2 += 1
            if right >= size:
                right = 0
            if ch[right] == 1:
                break
        if cnt1 >= cnt2:
            return [right, cnt2]
        else:
            return [left, cnt1]
        
    cur = 0
    res = 0
    while True:
        if ch[cur] == 1:
            ch[cur] = 0
            res += verticalCheck(name[cur])
            cnt -= 1
            
        if cnt != 0:
            next_cur, step = horizonCheck(cur)
            res += step
            cur = next_cur
        else:
            break
    return res

Written by@[HongDongUk]

공부한 것을 소소하게 적는 블로그.

GitHub Facebook