프로그래머스 문제 7, 8

괄호 회전하기

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

• (), [], {} 는 모두 올바른 괄호 문자열입니다.
• 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
• 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

입력: “{}”

출력: 3

내 풀이

def solution(s):
    
    par_dict = {')':'(', ']':'[', '}':'{'}
    def chk_valid(par_s):
        stack = []
        for par in par_s:
            if par not in par_dict:
                stack.append(par)
            elif stack and par_dict[par] == stack[-1]:
                stack.pop()
            else:
                return False
            
        return True if not stack else False
    
    count = 0
    
    for _ in range(len(s)):     
        count += chk_valid(s)
        s = s[1:] + s[0]
    
    return count

• chk_valid 함수는 회전한 괄호가 유효한지 아닌지 판단하는 함수이다. 이 함수의 판단 로직은 ‘유효한 괄호’ 문제에서 다루었으므로 자세한 내용은 생략한다.
• for문으로 제일 왼쪽의 문자를 나머지 문자열에 이어 붙여서 한칸씩 회전한 문자열의 유효한 괄호여부를 확인한다.

---

순위 검색

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 이때, 제한사항은 다음과 같습니다.

• info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 “개발언어 직군 경력 소울푸드 점수” 형식입니다.
• 개발언어는 cpp, java, python 중 하나입니다.
• 직군은 backend, frontend 중 하나입니다.
• 경력은 junior, senior 중 하나입니다.
• 소울푸드는 chicken, pizza 중 하나입니다.
• 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
• query의 각 문자열은 “[조건] X” 형식입니다.
• [조건]은 “개발언어 and 직군 and 경력 and 소울푸드” 형식의 문자열입니다.
• 언어는 cpp, java, python, - 중 하나입니다.
• 직군은 backend, frontend, - 중 하나입니다.
• 경력은 junior, senior, - 중 하나입니다.
• 소울푸드는 chicken, pizza, - 중 하나입니다.
• ’-‘ 표시는 해당 조건을 고려하지 않겠다는 의미입니다.

입력: info=[“java backend junior pizza 150”,”python frontend senior chicken 210”,”python frontend senior chicken 150”,”cpp backend senior pizza 260”,”java backend junior chicken 80”,”python backend senior chicken 50”] query=[“java and backend and junior and pizza 100”,”python and frontend and senior and chicken 200”,”cpp and - and senior and pizza 250”,”- and backend and senior and - 150”,”- and - and - and chicken 100”,”- and - and - and - 150”]

출력: [1,1,1,1,2,4]

내 풀이

def solution(info, query):
    
    answer = []

    info_list, query_list = [], []
    for i in info:
        split_i = i.split(' ')            
        info_list.append(split_i)
    
    for q in query:
        split_q = q.split(' and ')
        split_q.extend(split_q.pop().split(' '))
        while '-' in split_q:
            split_q.remove('-')            
        query_list.append(split_q)
    
    for q in query_list:
        corresponding_i = 0
        criteria = q.pop()
        for i in info_list:
            score = i[-1]
            if set(q) & set(i[:-1]) == set(q) and int(criteria) <= int(score):
                corresponding_i += 1
        answer.append(corresponding_i)
   
    return answer

• info의 지원서를 리스트로 만들고 query의 문의조건도 리스트로 만들어서 두 개의 리스트를 교집합 연산을 통해 지원서와 문의조건 일치 여부를 파악한다.
• 정확성 테스트는 통과했으나 효율성에서 문제가 생겼다.

풀이 1

import bisect, itertools, collections

def solution(info, query):
    infomap = collections.defaultdict(list)
    binarys = list(itertools.product((True, False), repeat=4))
    for inf in info:
        inf = inf.split()
        for binary in binarys:
            key = ''.join([inf[i] if binary[i] else '-' for i in range(4)]) 
            infomap[key].append(int(inf[4]))

    for k in infomap.keys():
        infomap[k].sort()

    answers = []
    for q in query:
        l,_,p,_,c,_,f, point = q.split()
        key = ''.join([l,p,c,f])
        # 1,2,3번째 조건에 맞는 key의 value를 찾고 그 중에서 문의 조건에서 설정한 점수보다 낮은 점수의 개수를 찾음
        i = bisect.bisect_left(infomap[key], int(point))
        answers.append(len(infomap[key]) - i)

    return answers

• 하나의 info에서 나올 수 있는 16가지의 key를 만들어서 infomap[key]에 값을 추가해준다.
• 이진 검색을 위해 infomap의 값들을 정렬한다.
• query의 값을 key로 만들고 이진 탐색으로 point 이상의 값 개수를 구한다.