데린이 성장 일지

https://school.programmers.co.kr/learn/courses/30/lessons/72411

try1

orders에 존재하는 문자열들의 조합으로 딕셔너리를 만들어 풀고자 했음

※나의 코드 - 실패함

def solution(orders, course):
    answer = []
    from itertools import combinations
    from collections import defaultdict

    char = sorted(set(''.join(orders)))             # orders에 들어가 있는 문자들 추출

    for k in course:
        dic = defaultdict(int)
        menu = []
        menu += list(combinations(char, k))         # char에 대해 해당 course 값의 나올 수 있는 메뉴 만들기
        for name in menu:
            name = ''.join([n for n in name]) 
            for o in orders:
                if set(name).issubset(o):           # 나올 수 있는 메뉴가 order에 있다면 +1
                    dic[name] += 1

        for i, v in dic.items():                    # 2회 이상이고 가장 많이 시킨 조합 메뉴 찾기
            if v >= 2 and v == max(dic.values()):
                answer += [i]

    return sorted(answer)

문제 풀이)

orders에 들어가 있는 문자들을 list형태로 char에 넣음

course에 대해 for문이 돌 때,

1. 딕셔너리 기본값이 0인 dic을 만들고 char의 문자들로 나올 수 있는 모든 조합을 menu에 넣음

2. order에서 나올 수 있는 조합이라면 딕셔너리 값에 1을 더함

3. 2회 이상이고 가장 많이 시킨 조합이라면 answer에 추가

마지막 리턴할 때 오름차순으로 해줌

테스트 결과 - 실패(시간초과)

※ 참고한 다른 사람 코드

# 다른 사람 코드

from itertools import combinations
from collections import Counter


def solution(orders, course):
    answer = []
    for c in course:
        temp = []
        for order in orders:
            combi = combinations(sorted(order), c)
            temp += combi
        counter = Counter(temp)
        print(counter)
        if len(counter) != 0 and max(counter.values()) != 1:
            answer += [''.join(f) for f in counter if counter[f] == max(counter.values())]

    return sorted(answer)

다른 사람 코드 해석)

course에 대해 for문이 돌 때,

1. orders에 대해 for문이 돌고, 각 order에 대해 나올 수 있는 조합들을 temp에 넣음
    이 때, sorted를 하는 이유는 이 후에 Counter로 중복된 조합을 셀 때 문자의 순서도 같아야 같은 것으로 세기 때문

2. 키가 조합, 값이 중복된 수인 딕셔너리 counter를 만듦

3. if문들의 조건에 맞는 조합을 answer에 추가

테스트 결과 - 총합 411.52ms

https://school.programmers.co.kr/learn/courses/30/lessons/60058

try 1

1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다. 
2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다. 
3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다. 
  3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다. 
4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다. 
  4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다. 
  4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다. 
  4-3. ')'를 다시 붙입니다. 
  4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다. 
  4-5. 생성된 문자열을 반환합니다.

처음에는 문제에서 제시한 알고리즘 뒷부분이 한번에 이해가 안됐다.

그래서 1.부터 하나씩 구현했더니 이해가 됐다.

그리고나선 하나씩 구현한 것을 합쳤다.

※ 나의 코드

#나의 코드

def solution(p):
    answer = ''
    if p == '':
        return ''
  
    for length in range(2,len(p)+1,2):
        u = p[:length]
        if u.count('(') == u.count(')'):
            v = p[length:]
            break

    import re
    f = re.compile('\).*\(')
    if f.match(u):
        gen = '(' + solution(v) + ')' + u[1:-1].replace('(','*').replace(')','(').replace('*',')')
        answer += gen
    else:
        answer += u + solution(v)
    
    return answer

문제 풀이)

p가 ''이면 ''을리턴하도록 if문 구성

for문을 진행 할 수 록 p를 2의 배수로 잘라서 u에 넣은 다음 u가 균형잡힌 괄호 문자열이라면 나머지 길이는 v에 넣고 for문 중지

정규식을 이용하여 u가 올바른 괄호 문자열인지 아닌지 확인한 후 제시된 알고리즘대로 if문 구성

테스트 결과 - 총합 6.82ms

※ 더 좋은 다른 사람 코드

# 다른 사람 코드

def solution(p):
    if p=='': return p
    r=True; c=0
    for i in range(len(p)):
        if p[i]=='(': c-=1
        else: c+=1
        if c>0: r=False
        if c==0:
            if r:
                return p[:i+1]+solution(p[i+1:])
            else:
                return '('+solution(p[i+1:])+')'+''.join(list(map(lambda x:'(' if x==')' else ')',p[1:i]) ))

다른 사람 코드 해석)

6.82 -> 2.57

약 4.25ms(약 60퍼) 줄음 (약 2.5배 빠름)

저의 코드와 다른 점만 해석

다른 사람 코드는 p가 올바른 괄호 문자열인지 확인하는 r 변수과 r 변수가 판단하기 위해 필요한 c변수를 만듦

맨 처음에 '('로 시작한다면 올바른 괄호 문자열 -> c = -1 -> r = True -> 이후에 c가 0이 되면 값이 리턴이 되기 때문에 c는 양수가 나올 수 없기 때문에 r은 True만 나옴

맨 처음에 ')'로 시작한다면 올바른 괄호 문자열이 아님 -> c = 1 -> r = False

이부분이 테스트 시간에 가장 큰 영향을 준 것 같음

코드 마지막에  join(list(map(lambda x)))가 제가 짠 replace보다 더 빠름

이부분만 바꾸었더니 테스트 시간 총합이 약 20퍼 줄었음

테스트 결과 - 총합 2.57ms