[17회차] 괄호 회전하기, H-index, 예상 대진표, 순위 검색, 올바른 괄호

Programmers Level.2 괄호 회전하기

def correctstring(st):
    cnt = [0, 0, 0] # 소괄호, 중괄호, 대괄호
    for i in st:
        if i == '(':
            cnt[0] += 1
        if i == ')':
            cnt[0] -= 1
        if i == '{':
            cnt[1] += 1
        if i == '}':
            cnt[1] -= 1
        if i == '[':
            cnt[2] += 1
        if i == ']':
            cnt[2] -= 1
        if any(j < 0 for j in cnt):
            return False # 올바르지 않은 문자열이면 False
    if all(j == 0 for j in cnt):
        return True # 올바른 문자열이면 True
    return False

def solution(s):
    n = 0
    answer = 0
    while n < len(s):
        if correctstring(s):
            answer += 1
        s = s[1:] + s[0]
        n += 1
    return answer

 - 처음에 내가 푼 풀이.

 - '( { [' 기호는 +1, ') } ]' 기호는 -1씩 cnt에 더하면서 값이 음수가 되는 경우가 있다면 올바르지 않은 문자열이고, 혹은 연산 마지막에서 cnt 값이 0이 아니라면 올바르지 않은 문자열일 것이다.

 - 괄호를 하나씩 회전하면서 올바른 문자열인지 일일이 확인하면 될 것이다.

 - 그러나 테스트 케이스 중 하나가 실패했고 '( { ) }'와 같은 반례가 있음을 알게 되었다.

 - 이 아이디어로는 '( { } )'와 '( { ) }'를 구분하는 게 쉽지 않다고 생각한다.

 

def correctstring(st):
    stack = []
    for i in st:
        if i == '(':
            stack.append(')')
        elif i == '{':
            stack.append('}')
        elif i == '[':
            stack.append(']')
        else: # ')}]'일 경우
            if stack == []: # stack이 비어있으면 False 반환
                return False 
            else:
                a = stack.pop() # stack에서 마지막 원소를 추출하고 i와 다르다면 False
                if a != i:
                    return False
    if stack == []: # 모든 과정을 마치고 stack이 비어있다면 True
        return True
    return False # 모든 과정을 마치고 stack이 비어있지 않다면 False
            

def solution(s):
    n = 0
    answer = 0
    while n < len(s):
        if correctstring(s):
            answer += 1
        s = s[1:] + s[0]
        n += 1
    return answer

 - 앞선 문제를 해결하기 위해 stack을 활용했다.

 - 매번 stack에서 꺼낸 원소(a)가 현재의 원소(i)와 짝을 이루는지 확인하는 과정을 통해 앞에서 문제가 된 케이스를 걸러낼 수 있었다.

 

 

Programmers Level.2 H-index

def solution(citations):
    answer = 0
    citations = sorted(citations, reverse=True)
    for i, j in enumerate(citations, start=1):
        if i <= j:
            answer += 1
        else:
            break
    return answer

 - 내 풀이

def solution(citations):
    citations.sort(reverse=True)
    answer = max(map(min, enumerate(citations, start=1)))
    return answer

 - 다른 사람의 풀이. 이 문제를 이런 식으로 풀이할 수 있다는 게 놀라웠다. 오늘도 감탄하고 간다.

 

 

Programmers Level.2 예상 대진표

def solution(n,a,b):
    answer = 0
    while a != b:
        a = (a + 1) // 2
        b = (b + 1) // 2
        answer += 1
    return answer

 

 

Programmers Level.2 순위 검색

def cnt(information, a,b,c,d,e):
    count = 0
    if a == '-':
        return cnt(information,'cpp',b,c,d,e) + cnt(information,'java',b,c,d,e) + cnt(information,'python',b,c,d,e)
    if b == '-':
        return cnt(information,a,'backend',c,d,e) + cnt(information,a,'frontend',c,d,e)
    if c == '-':
        return cnt(information,a,b,'junior',d,e) +cnt(information,a,b,'senior',d,e)
    if d == '-':
        return cnt(information,a,b,c,'chicken',e) + cnt(information,a,b,c,'pizza',e)
    for i in information[a,b,c,d]:
        if i >= e:
            count += 1
    return count


def solution(info, query):
    answer = []
    information = dict()
    for i in ('cpp','java','python'):
        for j in ('backend','frontend'):
            for k in ('junior','senior'):
                for l in ('chicken','pizza'):
                    information[i,j,k,l] = []
    for inf in info:
        a, b, c, d, e = inf.split(' ')
        information[a,b,c,d].append(int(e))
    for que in query:
        a,b,c,d = que.split(' and ')
        d, e = d.split(' ')
        e = int(e)
        answer.append(cnt(information, a, b, c, d, e))
    return answer

 - 첫 번째 아이디어(실패)

 - "개발언어, 직군, 경력, 소울푸드"-"점수" 쌍으로 사전 자료형을 만든 뒤에 query에 적힌 정보대로 count하는 함수를 설계하면 되겠다고 생각. 사전 자료형에는 3 * 2^3 (=48)개의 키 값이 존재.

 - 그 다음에 문제였던 것은 query에서 요구하는 value를 어떻게 셀 것인가. 특히 key 값에 '-'를 어떻게 구현할지 고민했다.

 - 재귀함수를 이용해 '-' 일 때는 거기에 해당하는 모든 key값들에 해당하는 cnt 함수를 불러와 더했다

 - 효율성 테스트에서 실패

def cnt(information, a,b,c,d,e):
    count = 0
    for i in information[a,b,c,d]:
        if i >= e:
            count += 1
    return count


def solution(info, query):
    answer = []
    information = dict()
    for i in ('cpp','java','python','-'):
        for j in ('backend','frontend','-'):
            for k in ('junior','senior','-'):
                for l in ('chicken','pizza','-'):
                    information[i,j,k,l] = []
    for inf in info:
        a, b, c, d, e = inf.split(' ')
        information[a,b,c,d].append(int(e))
        information['-',b,c,d].append(int(e))
        information[a,'-',c,d].append(int(e))
        information[a,b,'-',d].append(int(e))
        information[a,b,c,'-'].append(int(e))
        information['-','-',c,d].append(int(e))
        information['-',b,'-',d].append(int(e))
        information['-',b,c,'-'].append(int(e))
        information[a,'-','-',d].append(int(e))
        information[a,'-',c,'-'].append(int(e))
        information[a,b,'-','-'].append(int(e))
        information['-','-','-',d].append(int(e))
        information['-','-',c,'-'].append(int(e))
        information['-',b,'-','-'].append(int(e))
        information[a,'-','-','-'].append(int(e))
        information['-','-','-','-'].append(int(e))
    for que in query:
        a,b,c,d = que.split(' and ')
        d, e = d.split(' ')
        e = int(e)
        answer.append(cnt(information, a, b, c, d, e))
    return answer

 - 두 번째 시도(실패)

 - 재귀함수를 호출했기 때문에 생기는 비효율이 아닐까 생각해서 재귀함수를 사용하지 않기 위해, 사전자료형을 만들 때 key값에 '-' 항목도 추가해서 만들었다.

 - count하기 위해 모든 value들을 하나씩 확인하면서 세는 방식을 채택.

def cnt(information, a,b,c,d,e):
    count = 0
    i = 0
    while i < len(information[a,b,c,d]):
        if information[a,b,c,d][i] >= e:
            count += 1
        else:
            break
        i += 1
    return count


def solution(info, query):
    answer = []
    information = dict()
    for i in ('cpp','java','python','-'):
        for j in ('backend','frontend','-'):
            for k in ('junior','senior','-'):
                for l in ('chicken','pizza','-'):
                    information[i,j,k,l] = []
    for inf in info:
        a, b, c, d, e = inf.split(' ')
        information[a,b,c,d].append(int(e))
        information['-',b,c,d].append(int(e))
        information[a,'-',c,d].append(int(e))
        information[a,b,'-',d].append(int(e))
        information[a,b,c,'-'].append(int(e))
        information['-','-',c,d].append(int(e))
        information['-',b,'-',d].append(int(e))
        information['-',b,c,'-'].append(int(e))
        information[a,'-','-',d].append(int(e))
        information[a,'-',c,'-'].append(int(e))
        information[a,b,'-','-'].append(int(e))
        information['-','-','-',d].append(int(e))
        information['-','-',c,'-'].append(int(e))
        information['-',b,'-','-'].append(int(e))
        information[a,'-','-','-'].append(int(e))
        information['-','-','-','-'].append(int(e))
    for i in information:
        information[i] = sorted(information[i], reverse=True)
    for que in query:
        a,b,c,d = que.split(' and ')
        d, e = d.split(' ')
        e = int(e)
        answer.append(cnt(information, a, b, c, d, e))
    return answer

 - 세 번째 시도(실패)

 - 사전자료형 안에 자료들을 내림차순으로 정렬시키고 count를 하면 좀 더 빠르지 않을까 생각했다.

 - 내림차순으로 정렬되어 있으므로 요구하는 값보다 작은 value값이 나올 때 break하면 된다고 생각. 하지만 실패.

def cnt(information, a,b,c,d,e):
    if not information[a,b,c,d]:
        return 0
    count = 0
    start = 0
    end = len(information[a,b,c,d]) - 1
    while start <= end:
        mid = (start + end) // 2
        if information[a,b,c,d][mid] >= e:
            count = mid + 1
            start = mid + 1
        else:
            end = mid - 1
    return count


def solution(info, query):
    answer = []
    information = dict()
    for i in ('cpp','java','python','-'):
        for j in ('backend','frontend','-'):
            for k in ('junior','senior','-'):
                for l in ('chicken','pizza','-'):
                    information[i,j,k,l] = []
    for inf in info:
        a, b, c, d, e = inf.split(' ')
        information[a,b,c,d].append(int(e))
        information['-',b,c,d].append(int(e))
        information[a,'-',c,d].append(int(e))
        information[a,b,'-',d].append(int(e))
        information[a,b,c,'-'].append(int(e))
        information['-','-',c,d].append(int(e))
        information['-',b,'-',d].append(int(e))
        information['-',b,c,'-'].append(int(e))
        information[a,'-','-',d].append(int(e))
        information[a,'-',c,'-'].append(int(e))
        information[a,b,'-','-'].append(int(e))
        information['-','-','-',d].append(int(e))
        information['-','-',c,'-'].append(int(e))
        information['-',b,'-','-'].append(int(e))
        information[a,'-','-','-'].append(int(e))
        information['-','-','-','-'].append(int(e))
    for i in information:
        information[i] = sorted(information[i], reverse=True)
    for que in query:
        a,b,c,d = que.split(' and ')
        d, e = d.split(' ')
        e = int(e)
        answer.append(cnt(information, a, b, c, d, e))
    return answer

 - 성공 케이스

 - 좀 더 효율적으로 세기 위해 정렬된 자료를 이진탐색을 이용해 count하는 방식으로 변경.

 

 

Programmers Level.2 올바른 괄호

def solution(s):
    cnt = 0
    for i in s:
        if i == '(':
            cnt += 1
        elif i == ')':
            cnt -= 1
        if cnt < 0:
            return False
    return cnt == 0

 - 가장 먼저 떠오른 방식

def solution(s):
    stack = []
    for i in s:
        if i == '(':
            stack.append(i)
        elif i == ')':
            try:
                stack.pop()
            except IndexError:
                return False
    return stack == []

 - 괄호 회전하기 처럼 stack을 활용해서 문제를 풀이해봤다.