수학과의 개발자 도전기

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

Lv2 문제이고, 스스로 푼 문제다!

그렇게 어려운 문제는 아닌 것 같은데 문자열을 내가 원하는 상태로 변경하는데 시간을 꽤 쓴 것 같다. 총 1시간 반 걸려서 푼 문제,,,ㅎ

빠르게 푸는 법을 공부해야할 것 같다 

문제 이해

s의 각 원소들 안에서 순서가 다르기 때문에 올바른 튜플을 구하기 위해선 

길이가 1인 원소부터 가장 긴 원소까지 진행하면서 누적된 수 중에서 겹치지 않는 숫자를 answer에 추가하면 된다고 생각했다

- 정답 풀이 :

1. 각각의 {}원소들을 배열 []로 바꾸고 싶어서 처음에 양끝에 있는 {,}를 없앤다

2. 그러면 원소들의 형태가 '{11,2,3,', ,,,, '{11,2,3,4,5}'의 형태가 되는데

각 원소에서 { 또는 }를 모두 제거한다(첫번째 반복문)

3. 그러면 '11,2,3', ,,, '11,2,3,4,5'의 형태가 되는데 여기서 ','를 기준으로 split하면 리스트가 되므로 이를 result에 넣어준다

* 더 간단한 방법이 있을텐데 일단 이 방법이 최선이었고, 무엇보다 원소들이 다 한자리 수가 아니라 2자리 수 이상인 수들도 있어서 원소 하나하나씩 구별할 경우 111이 1,1,1로 바뀌는 경우가 있어 이를 피하기 위해 each.split(',')한 것이기도 하다 

이렇게 하면 내가 원하는 [[11,2,3],,,,[11,2,3,4,5]]의 형태가 된다 

4. 원소 길이가 가장 작은 것부터 가장 큰 것까지 차례로 진행할 것이기 때문에 가장 큰 원소 길이가 필요해 max_len을 구하는 반복문을 추가했다

5. 길이가 1부터 max_len까지 진행하면서 길이가 i인 result의 원소 리스트(each)에 대하여 answer에 없는 each의 원소를 each에 추가해준다(이때 each의 원소를 모두 int()처리해주는 것 잊지말자!)

예시) answer = [2,1] 이고 each = [1,2,3] 인 경우에는 3만 answer에 없으므로 이를 추가하는 로직을 수행한다 

def solution(s):
    answer = []
    #원소 갯수 작은것부터 정렬한다음 없는 원소들 하나씩 추가하면 될 것 같은데 
    temp = s[1 : -1].split('},')
        
    result = []
    for each in temp:
        if each[0] == '{':
            each = each[1:]
        if each[-1] == '}':
            each = each[:-1]
        each = each.split(',')
        result.append(each)
  
    max_len = 0
    for each in result:
        max_len = max(max_len, len(each))
                        
    for i in range(1, max_len + 1):
        for each in result:
            if len(each) == i:
                for j in each:
                    if int(j) not in answer:
                        answer.append(int(j))
                        
    return answer

- 시도해본 풀이 :

이렇게 하면 {{123}}과 같이 두자리 이상의 수를 처리하는데 틀린 답을 출력한다

def solution(s):
    answer = []
    #원소 갯수 작은것부터 정렬한다음 없는 원소들 하나씩 추가하면 될 것 같은데 
    temp = list(s)[1 : -1]
    print(temp)
    sequence = []
    while temp:
        x = temp.pop(0)
        if x == '{':
            result = []
            while True:
                y = temp.pop(0)
                if y == '}':
                    break
                if y == ',':
                    continue
                result.append(int(y))
            sequence.append(result)
            
    print(sequence)        
    max_len = 0       
    for i in sequence:
        max_len = max(max_len, len(i))
        
    for i in range(1, max_len + 1):
        for each in sequence:
            if len(each) == i:
                for j in each:
                    if j not in answer:
                        answer.append(j)
                        
    return answer

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

처음 문제 보고 이게 무슨 얘기인가 싶었다 

cacheSize는 데이터를 저장할 수 있는 크기이고, 

cache hit은 cpu가 참조하고자 하는 메모리가 캐시에 존재하는 경우

cache miss는 cpu가 참조하고자 하는 메모리가 캐시에 존재하지 않는 경우를 

의미한다 

*LRU : 가장 오랫동안 참조되지 않은 데이터를 제거한다 

캐시가 LRU로 진행하기 때문에 제일 먼저 들어간 데이터가 가장 오래되었을 것이므로, 가장 먼저 나와야한다

주의해야할 게 Newyork과 newyork이 같은 취급을 받기 때문에 도시 이름들을 모두 소문자화 해야한다는 것이다. 

- 정답 풀이 :

cacheSize가 0이라면 모든 데이터들은 5의 시간으로 데이터 처리가 되므로 도시 갯수 * 5를 해주면 된다 

city들을 모두 소문자로 바꾼다음에 cache에 있는 도시라면 time += 1하고 기존에 있던 city를 cache에서 제거한 후 새로운 도시를 추가해준다  

city가 cache에 없다면 time += 5를 해주고 이미 cache가 cacheSize만큼 데이터를 가지고 있다면 왼쪽 값을 빼주고

해당 도시를 cache에 추가해준다

from collections import deque

def solution(cacheSize, cities):
    time = 0
    cache = deque()
    
    if cacheSize == 0:
        return len(cities) * 5
    
    for city in cities:
        city = city.lower()
        if city in cache:
            time += 1
            cache.remove(city)
        else:
            time += 5
            if len(cache) >= cacheSize:
                cache.popleft()
        cache.append(city)
        
    return time

- 시도해 본 풀이 

50 퍼센트에서 막혔다

쓸데없이 복잡하게 풀었다

모든 도시들 소문자로 변경하기, 초기 cache 세팅하기

city들 dictionary 설정하기 

흠,,,

def solution(cacheSize, cities):
    dic = {}
    cache = []
    
     #모든 도시 이름 소문자로 바꾸기 
    for i in range(len(cities)):
        cities[i] = cities[i].lower()
        
    time = 0
    for i in range(cacheSize):
        cache.append(cities[i])
        dic[cities[i]] = 1
        time += 5
    cities = cities[cacheSize : ]
    
    for city in cities:
        if city in cache : 
            dic[city] += 1 #사용횟수 하나 증가 
            time += 1
        #캐시에 없는 경우 lru로 최근에 사용되지 않은 거 없애고 재료 추가 
        elif city not in cache: 
            temp = sorted(dic.items(), key = lambda x : x[1])
            if len(temp) > 0:
                find = temp[0][0]
                cache.remove(temp[0][0])
                del dic[find]
            
            dic[city] = 1
            cache.append(city)
            time += 5
            
    return time

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

문제 이해 

stack으로 0번째 인덱스를 끝으로 옮기면서 만들어진 리스트에서 완전한 괄호의 갯수를 반환하는 것으로 이해했다. 

1. 괄호가 완전한지 알아야해서 check() 함수를 따로 만들었다 

2. 이는 스택을 이용해서 탐색하는 문자와 stack의 끝 문자가 올바른 괄호가 되면 스택에서 왼쪽 괄호를 없앤다 

3. 전체가 올바른 괄호가 된다면 스택에 더이상 원소가 없을 때 조건을 만족하므로 answer += 1 해준다 

4. 괄호를 회전한다(0번째 인덱스 오른쪽 끝으로 이동시키기)

참고한 블로그

- 정답 풀이 :

def solution(s):
    answer = 0
    temp = list(s)
    
    for _ in range(len(s)):
 
        st = []
        for i in range(len(temp)):
            if len(st) > 0:
                if st[-1] == '[' and temp[i] == ']':
                    st.pop()
                elif st[-1] == '(' and temp[i] == ')':
                    st.pop()
                elif st[-1] == '{' and temp[i] == '}':
                    st.pop()
                else:
                    st.append(temp[i])
            else:
                st.append(temp[i])
        if len(st) == 0:
            answer += 1
        temp.append(temp.pop(0))
 
    return answer

- 시도해본 풀이 :

테스트 14번 하나만 계속 틀렸던 풀이다. 한 문제때문에 삽질한거 스트레스 받네

특정 리스트에서 (), {}, [] 각각이 올바른 괄호를 만드는지 확인한다

count는 왼쪽의 갯수이고, 올바른 괄호가 만들어질 때마다 하나씩 줄어든다

각 경우에 왼쪽이 없을 때 오른쪽이 나오면 올바른 괄호가 아니니까 False로 만들고

왼쪽이 있을 때 오른쪽이 나오면 count를 줄인다 

def check(stack, left, right):
    flag = True
    count = 0
    for i in range(len(stack)):
        if stack[i] == left:
            count += 1
        elif stack[i] == right:
            if count == 0:
                flag = False
                break
            else:
                count -= 1
    return flag   

def solution(s):
    n = len(s)
    stack = list(s)    
    small_l, small_r = stack.count('('), stack.count(')')
    mid_l, mid_r = stack.count('{'), stack.count('}')
    big_l, big_r = stack.count('['), stack.count(']') 
    
    if (small_l != small_r) or (mid_l != mid_r) or (big_l != big_r):
        return 0
    else:    
        answer = 0
        while n > 0 :
            x = stack.pop(0)
            stack.append(x)
            #stack 올바른지 확인하는 함수 구현 
            if (check(stack, '(', ')')) and (check(stack, '{', '}')) and (check(stack, '[', ']')):
                answer += 1
            n -= 1      
            
        return answer

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

Lv2 문제다!

문제 이해

정답 행렬의 (i,j) 원소는 arr1[i][열] 와 arr2[행][j]의 곱의 합이다 

각 리스트를 곱하기도 해야하고, 그 값을 누적도 해야하기 때문에 3중 for문으로 진행한다 

이중 for문에 for k 문 추가해서 하는 거 생각했는데, 안될 것 같아서 다른 방법으로 푸느라 삽질 엄청 했다ㅠ

이차 행렬은 이렇게 진행하는 걸로 기억해둬야겠다 

- 정답 풀이: 

def solution(arr1, arr2):
    n = len(arr1)
    m = len(arr2[0])
    answer = [[0] * m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            for k in range(len(arr2)):
                answer[i][j] += arr1[i][k] * arr2[k][j]
                
    return answer

- 삽질한 풀이

이렇게 풀지 말자!!

def change(arr2, j, m):
    temp = []
    for i in range(m):
        temp.append(arr2[i][j])
        
    return temp 

def matrix(arr1, arr2):
    num = 0
    for i in range(len(arr1)):
        num += arr1[i] * arr2[i]
    return num
            
def solution(arr1, arr2):
    a, b = len(arr1), len(arr1[0])
    c, d = len(arr2), len(arr2[0])
    flag = True
    if b == c:
        n, m = a, d
    elif d == a:
        flag = False
        n, m = c, b
        
    answer = [[0] * m for _ in range(n)]
    
    if flag: 
        for i in range(n):
            for j in range(m):
                temp = change(arr2, j, m)
                answer[i][j] = matrix(arr1[i], temp)
    else:
        for i in range(n):
            for j in range(m):
                temp = change(arr1, j, m)
                answer[i][j] = matrix(arr2[i], temp)
            
    return answer