수학과의 개발자 도전기

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/67257

Lv2 문제다!

참고한 블로그

문제 이해 

최대 3개의 연산자(*, +, -)의 우선순위를 매겨서 계산한 결과 중 절댓값의 최대를 구하는 문제다

연산자의 개수가 몇개 안되므로 이는 permutations을 통해 정하면 된다고 생각했다

문제는 우선순위에 따라 식을 계산하는 건데, 여기에서 막혔었다 

각 순열에 대해서 우선순위에 따른 값을 abs로 절댓값으로 바꾼다음 그 중 최댓값을 반환하면 된다

풀이 이해 

• expression에서 숫자와 연산자를 따로 분리하기 위해 li 스택을 이용한다 ('100', '+', '200) 
• 3개의 연산자 중 식에 없는 연산자는 제거한다 
• permutations 함수를 이용해 임의의 연산자 우선순위를 구한다 
• 우선순위에 맞춰서 식을 계산한다(여기가 가장 어렵다)
• 계산한 결과를 abs로 절댓값으로 바꿔준다
• answer와 result 중 최댓값을 누적한 후 반복문이 끝나면 해당 answer를 반환한다 

- 정답 풀이 : 

from itertools import permutations
from collections import deque

def solution(expression):
    answer = 0
    ops = ["*", "+", "-"]
    
    # 스택 생성
    li = []
    s = 0
    for i, v in enumerate(expression):
        if v in ["*", "+", "-"]:
            li.append(expression[s:i])
            li.append(v)
            s = i + 1
    else:
        li.append(expression[s:])
    
    # expression에 없는 연산자는 ops에서 제거
    for op in ops:
        if op not in expression:
            ops.remove(op)
            
    # ops에 있는 연산자로 구성할 수 있는 모든 우선순위 생성
    primarity = permutations(ops)
    
    for case in primarity: # 최대 6가지의 연산자 우선순위 조합
        stacks = [deque(li), deque()]
        t1 = 1
        for c in case: # 각 경우에서 연산자 처리
            t1 = (t1+1) % 2 # 스택 토글 변수
            t2 = (t1+1) % 2
            while len(stacks[t1]):
                item = stacks[t1].popleft()
                if len(stacks[t2]) and stacks[t2][-1] == c:
                    c = stacks[t2].pop()
                    n = stacks[t2].pop()
                    item = str(eval(str(n)+c+str(item)))
                stacks[t2].append(item)
            
        result = stacks[len(ops)%2].pop()
        result = abs(int(result))
        answer = max(answer, result)
            
    return answer

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12936

Lv2 문제다!

(n - 1)!만큼 i번째 수가 각 인덱스에 있는 걸 발견했지만, 이를 어떻게 구현해야할지 몰랐던 문제다.

이번 기회를 통해서 이 부분 공부해야겠다 

참고한 블로그

문제 이해 

• permutation으로 구하면 시간이 오래 걸리므로, 다른 방법을 사용해야한다 
• 문제를 보면 1부터 n으로 시작하는 배열이 각각 n! // n == (n - 1)! 개씩 있다 
• k 를 (n - 1)!로 나눈 몫(k // (n - 1)!)이 정답 배열에 추가되는 수이므로 answer에 추가한다 
• temp에서는 해당 수를 사용했으므로 pop해준다 
• k를 (n - 1)!로 나눈 나머지, n은 -1 해준다
• 위의 연산을 총 n번 반복한다 

- 정답 풀이 : 

import math

def solution(n, k):
    temp = [x for x in range(1, n + 1)]
    answer = []
    k -= 1
    
    # n번 반복 
    for _ in range(n, 0, -1):
        max_num = math.factorial(n)
        split_num = max_num // n
        
        answer.append(temp[k // split_num])
        temp.pop(k//split_num)
        
        k %= split_num
        n -= 1
        
    return answer

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/17683

Lv2 문제다!

구현문제인데 단순하게 생각하면 안되는 문제인 것 같다. 

풀이 이해 

• 재생된 시간을 분으로 변경한다(12:00 ~ 12: 05를 5분으로 변경)
• 각 노래마다 재생된 시간만큼 길이를 설정한다 
  • 재생된 시간 == 노래 길이 : 노래 한번 반복
  • 재생된 시간 < 노래 길이 : 노래 길이 일부만 재생됨
  • 재생된 시간 > 노래 길이 : 노래 길이 배수만큼 반복되고, 남은 시간은 노래 일부만 재생 
• 노래 멜로디 중에 m을 포함하는 노래의 제목을 반환한다 (checkSubArray() 함수)
• m을 포함하는 노래가 2개 이상인 경우 노래 재생시간 순으로한다 
  • 노래 재생시간이 같으면 먼저 재생된 노래를 반환한다 

주의할 점 

• 음정에 #을 포함하는 경우를 잘 생각해야한다. 
• m이 ABC이고, 노래 음정이 ABC#라면 ABC가 포함되는데, 일치하는 음정이 아니다.
• 그래서 #이 있는 경우 이것까지 같이 담아야한다
  • 각 음정을 배열의 한 원소로 만드는 함수 getMusicArr()를 이용한다 (m과 각 노래들에 대해 변경해야하므로 함수로 변경하는 것이 용이하다)
  • getMusicArr에서 time == 0이라면 temp의 길이가 0이므로 분기문으로 따로 구현한다 
• 해당하지 않는 경우는 None이 아닌 문자열 "(None)"을 반환해야한다 

- 정답 풀이 :

참고한 블로그

def getMusicArr(melody, time):
    temp = []
    for c in melody:
        if c == '#':
            temp[-1] += '#'
        else:
            temp.append(c)  
        
    if time == 0:
        return temp
            
    if time // len(temp) == 0:
        temp = temp[:time]
    else:
        temp = temp * (time // len(temp)) + temp[: time % len(temp)]
            
    return temp 

def checkSubArray(sub, arr):
    length = len(sub)
    for i in range(len(arr)):
        if sub == arr[i : i + length]:
            return True
    return False
    
def solution(m, musicinfos):
    answer = "(None)"
    answerTime = 0
    
    musics = []
    for i in range(len(musicinfos)):
        start, end, title, melody = musicinfos[i].split(',')
        # 재생 시간 구하기 
        s1, s2 = int(start[0 : 2]), int(start[3 : 5])
        e1, e2 = int(end[0 : 2]), int(end[3 : 5])
        hour, minute = e1 - s1, e2 - s2
        time = hour * 60 + minute
        # 음정 분리하기                 
        musicArr = getMusicArr(melody, time)
        m = getMusicArr(m, 0)
    	# m에 해당하는 문자열을 musicArr가 포함하는지 확인
        if checkSubArray(m, musicArr):
            if answerTime < time:
                answer = title
                answerTime = time
    return answer

- 시도해본 풀이 : 

50 퍼센트까지 맞았던 문제다

시간에 따른 멜로디를 확보한 뒤, m을 포함하는 걸 모두 담아서 조건에 맞춰서 반환하려했다 

def solution(m, musicinfos):
    
    musics = []
    for i in range(len(musicinfos)):
        start, end, title, melody = musicinfos[i].split(',')
        
        n = len(melody)
        s1, s2 = int(start[0 : 2]), int(start[3 : 5])
        e1, e2 = int(end[0 : 2]), int(end[3 : 5])
        hour, minute = e1 - s1, e2 - s2
        time = hour * 60 + minute
        
        temp = ''
        if time // n == 0:
            temp = melody[:time]
        else:
            temp = melody * (time // n ) + melody[: time % n]
            
        musics.append([title, temp])
        
    answer = []
    length = len(m)
    for i in range(len(musics)):
        if m in musics[i][1] and m + '#' not in musics[i][1]:           
            # 재생 시간, 재생 순서, 곡 제목 
            answer.append([length, i, musics[i][0]])

    if len(answer) == 0:
        return "(None)"
    elif len(answer) == 1:
        return answer[0][2]
    else :     
        result = []
        answer.sort(key = lambda x : x[0], reverse = True)
        temp = answer[0][0]
        for i in range(len(answer)):
            if answer[i][0] == temp:
                result.append([answer[i][1], answer[i][2]])
                
        result.sort()
        return result[0][1]

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/68936

Lv2 문제다!

크기가 절반씩 줄어들면서 같은 로직을 반복해서 재귀함수로 풀어야겠다는 건 알았는데, 이게 바로 손이 가지 않았다. 

시작점의 위치를 기준으로 n 크기 만큼의 정사각형들을 탐색하면된다 

풀이 로직

• 리스트를 실제 자르지 말고 나뉘는 인덱스만 구해서 해결하는 것이 좋다.
• 인덱스를 구할 때는 네모의 시작점의 위치만 구한다. 거기에서 네모의 길이만큼 더해주면 네모를 완성시킨다.
• 재귀함수는 시작 지점의 위치와 각 네모의 길이를 매개변수로 넘기면 된다.
• 네모 내부에서 시작점의 값과 다른 값이 있다면 바로 작은 단위로 넘어간다
• 압축에 성공했다면 네모의 시작값의 위치에 + 1 해준다

- 정답 풀이 :

return을 안 하면 함수가 제때 종료가 되지 않아 틀린 답을 출력한다

이 과정이 이해가 가지 않아 python tutor를 돌렸더니,

comp 과정 중에 answer[init] += 1까지 간 함수들이 None을 반환하고,(?)

각각의 comp가 실행되다가 마지막 comp가 나오면 return을 통해 해당 깊이의 재귀를 빠져나온다 (?) 

def solution(arr):
    answer = [0, 0]
    N = len(arr)
    
    def comp(x, y, n):
        init = arr[x][y]
        for i in range(x, x + n):
            for j in range(y, y + n):
                if arr[i][j] != init:
                    m = n // 2
                    comp(x, y, m)
                    comp(x, y + m, m)
                    comp(x + m, y, m)
                    comp(x + m, y + m, m)
                    return
                
        #무사히 다 통과했다면 압축가능         
        answer[init] += 1
        
    comp(0, 0, N)
    
    return answer