수학과의 개발자 도전기

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

문제 이해 

어피치의 과녁 정보는 info에 담겨있고, 라이언이 n개의 화살을 쏴서 어피치를 최대 점수 차로 이기는 경우의 과녁 정보를 반환하는 문제다. 

어피치와 비기거나 지게되었을 땐 [-1]을 반환한다.

10 - i 점수에서 이겼을때(맞힌 화살의 수가 상대방보다 더 클 때) 10 - i 점수만 받게 된다. 

이렇게 라이언이 어피치를 이기는 경우 중에 최대 점수 차가 나는 경우, 그 경우가 여러개일 경우 낮은 점수를 가장 많이 쏜 경우를 반환하면 된다. 

어려웠던 점 

점수 계산하는 건 이해가 갔지만 라이언이 화살을 쏘는 경우를 어떻게 만들어야할지 몰랐다. 

배운 점 

구글링해보니 라이언이 이기려면 어피치의 과녁에 있는 갯수보다 +1을 하거나, 해당 과녁은 0개를 맞추고 다른 곳에서 더 많은 점수를 얻는 경우 두가지가 있다고 한다. 그래서 이걸 bfs로 구현하면 된다는 걸 배웠다. 

- 정답 풀이 :

풀이는 크게 4가지 경우로 나뉘어서 진행된다.

focus, arrow = arrow의 인덱스(10 - 현재 맞추고 있는 과녁의 번호), 화살의 현재 상태 

1. 라이언이 화살 n 개를 모두 쏜 경우 : 어피치와 라이언의 점수를 비교해서 최대 점수차 정보를 res에 추가해간다.

2. 라이언이 화살 n개 초과를 쏜 경우 : continue한다 

3. 라이언이 화살을 덜 쐈는데, 0점을 가리키고 있는 경우 : 0점 인덱스(10)에 남은 화살을 모두 쏘고 (-1, temp)를 q에 추가한다.

4. 라이언이 화살 n개 미만으로 쏜 경우  : 어피치보다 1점 더 큰 값을 추가하거나 0점으로 처리한 화살 정보를 q에 추가한 뒤 bfs를 이어나간다. 

1. 화살을 n개 다 쏜 경우는 

i 인덱스에서 어피치나 라이언의 점수가 있다면 누가 더 많이 맞혔나 비교한 뒤 apeach와 lion의 점수의 차이를 구한다. (gap)

lion이 apeach보다 점수가 더 높다면, 그 차이를 계산한 뒤 maxGap을 비교한다. 이때 3가지 경우에 대해 모두 생각해야한다. 

• maxGap이 gap과 같다면 화살 상태를 그대로 추가하고
• maxGap < gap이라면 기존에 있던 res를 초기화한 뒤 해당 화살 상태를 추가한다.
• maxGap > gap이라면 업데이트할 필요가 없으므로 continue한다 

        if sum(arrow) == n:  # 종료조건 1) 화살 다 쏜 경우
            apeach, lion = 0, 0
            for i in range(11):
                if not (info[i] == 0 and arrow[i] == 0):
                    if info[i] >= arrow[i]:
                        apeach += 10 - i
                    else:
                        lion += 10 - i
            if apeach < lion:  # 라이언이 이기면
                gap = lion - apeach
                if maxGap > gap:
                    continue
                if maxGap < gap:
                    maxGap = gap  # 최대점수차 갱신
                    res.clear()
                res.append(arrow)  # 최대점수차를 내는 화살상황 저장

2. 화살을 n개 초과로 쏜 경우 -> 넘어간다 

        elif sum(arrow) > n:  # 종료조건 2) 화살 더 쏜 경우
            continue

3. focus == 10 인 경우, 즉 화살 n개를 다 쏘지 못한 상태로 0점 과녁으로 온 경우. (focus 값은 10 - focus 과녁을 가리키고 있으므로)

arrow를 복사한 temp를 만들어 0점에 남은 화살을 몰아준 뒤 (-1, temp)를 q에 추가해서 끝낸다. (temp를 복사 안하고 바로 arrow를 사용할 수 있지 않나?)

        elif focus == 10:  # 종료조건 3) 화살 덜 쏜 경우
            tmp = arrow.copy()
            tmp[focus] = n - sum(tmp)
            q.append((-1, tmp))

4. 화살 쏘는 경우 

- 어피치 점수 + 1을 한 뒤 진행하는 경우

- 해당 과녁에 0점 처리를 한 뒤 진행하는 경우

두 가지 경우로 나눠서 bfs를 진행한다. 

         else:  # 화살 쏘기
            tmp = arrow.copy()
            tmp[focus] = info[focus] + 1 
            q.append((focus + 1, tmp))  # 어피치보다 1발 많이 쏘기
            tmp2 = arrow.copy()
            tmp2[focus] = 0
            q.append((focus + 1, tmp2))  # 0발 쏘기

참고한 블로그

from collections import deque

def bfs(n, info):    
    res = []
    q = deque([(0, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0])])
    maxGap = 0
    
    while q:
        focus, arrow = q.popleft()
        
        if sum(arrow) == n:  # 종료조건 1) 화살 다 쏜 경우
            apeach, lion = 0, 0
            for i in range(11):
                if not (info[i] == 0 and arrow[i] == 0):
                    if info[i] >= arrow[i]:
                        apeach += 10 - i
                    else:
                        lion += 10 - i
            if apeach < lion:  # 라이언이 이기면
                gap = lion - apeach
                if maxGap > gap:
                    continue
                if maxGap < gap:
                    maxGap = gap  # 최대점수차 갱신
                    res.clear()
                res.append(arrow)  # 최대점수차를 내는 화살상황 저장
        
        elif sum(arrow) > n:  # 종료조건 2) 화살 더 쏜 경우
            continue
        
        elif focus == 10:  # 종료조건 3) 화살 덜 쏜 경우
            tmp = arrow.copy()
            tmp[focus] = n - sum(tmp)
            q.append((-1, tmp))
        
        else:  # 화살 쏘기
            tmp = arrow.copy()
            tmp[focus] = info[focus] + 1 
            q.append((focus + 1, tmp))  # 어피치보다 1발 많이 쏘기
            tmp2 = arrow.copy()
            tmp2[focus] = 0
            q.append((focus + 1, tmp2))  # 0발 쏘기
    return res

def solution(n, info):
    winList = bfs(n, info)
    
    if not winList:
        return [-1]
    elif len(winList) == 1:
        return winList[0]
    else:
        return winList[-1]

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

문제 이해 

각 query의 조건을 만족하는 info에서의 지원자 수를 각각 담아서 출력하는 문제다.

이해를 바탕으로 매 query에 대해서 모든 info를 탐색하면서 맞는 지원자 수를 세는 로직으로 했는데 모든 효율성 테스트에서 실패했다. 

그래서 구글링을 해봤더니 딕셔너리와 이진탐색을 이용하면 된다. 

풀이 이해

• java backend junior pizza 150의 경우 해당되는 조건은 각 (단어 + '-', 총 두 개)로 언어, 직무, 경력, 음식 총 4번 카운트하면 16개의 경우의 수가 있다. (예 : 조건이 - backend - pizza 100인 경우도 해당 지원자가 만족하는 조건이다.)
• 그렇기에 지원자의 정보에 해당하는 경우들을 key로 만든다음 그 조건을 만족하는 지원자들의 코테 점수를 value에 리스트로 저장하면 된다. 
• query에 해당하는 조건이 딕셔너리 키에 있을 때, 해당 조건의 점수 리스트에서 타겟 점수 이상인 인덱스를 이진탐색으로 구하면 해당 인덱스부터 끝까지의 원소 개수가 해당 query 조건을 모두 만족하는 지원자 수이므로 그를 answer에 추가하면 된다. 
  • 풀이에서 bisect_left를 사용하는 이유 : value를 오름차순 정렬하므로 조건을 만족하는 점수가 처음 나오면 그 값의 인덱스부터 마지막 인덱스까지는 모두 타겟 점수를 만족하는 숫자들이다. 그렇기에 왼쪽 인덱스가 오른쪽으로 움직이면서(인덱스가 작은 값이 큰 값으로) 진행돼야하기 때문이라고 생각한다. 

- 정답 풀이 :

풀이에서 배운 것들 

• 지원자 정보로 만들 수 있는 모든 경우 구하기 위해서 combinations이용해서 '-' 추가할 위치 임의로 구한다
• 기존의 condition을 copy()한 temp를 만들어서 조합 위치에 '-'로 바꾼다 
• key에는 리스트 대신 문자열을 위치시킬 것이므로 ''.join(temp)를 한다 
• 각 query의 and를 ' '로 대체한 뒤, 모든 ' '(띄어쓰기)를 기준으로 단어를 분리한다
• 분리한 단어들로 다시 하나의 문자열로 변경한다  

참고한 블로그

from itertools import combinations
from collections import defaultdict
from bisect import bisect_left

def solution(information, queries):
    answer = []
    dic = defaultdict(list)
    for info in information:
        info = info.split()
        condition = info[:-1]  
        score = int(info[-1])
        for i in range(5):
            case = list(combinations([0,1,2,3], i))
            for c in case:
                tmp = condition.copy()
                for idx in c:
                    tmp[idx] = "-"
                key = ''.join(tmp)
                dic[key].append(score) 

    for value in dic.values():
        value.sort()   

    for query in queries:
        query = query.replace("and ", "")
        query = query.split()
        target_key = ''.join(query[:-1])
        target_score = int(query[-1])
        count = 0
        if target_key in dic:
            target_list = dic[target_key]
            idx = bisect_left(target_list, target_score)
            count = len(target_list) - idx
        answer.append(count)     
        
    return answer

- 시도해본 풀이 :

정확성은 다 맞았는데 효율성 테스트는 통과하지 못했다.

query가 최대 5만이고, info가 최대 10만이라서 최대 시간 복잡도가 50억이라서 이를 고려한 코드를 짜지 않아서 그런 것 같다 

빠르게 조회할 수 있도록 최적화가 필요한 것 같다 

def solution(info, query):
    people = []
    for i in info:
        people.append(i.split(' '))
        
    for i in range(len(query)):
        query[i] = query[i].split(' ')  
        query[i].append(i)
       
    people.sort()
    query.sort()
    answer = [0] * len(query)
    for i in range(len(query)):
        number = 0
        temp = [query[i][0], query[i][2], query[i][4], query[i][6], query[i][7]]
        for j in range(len(people)):
            count = 0
            for k in range(5):
                if temp[k] == '-':
                    count += 1
                else:
                    if k == 4:
                        if int(temp[k]) > int(people[j][k]):
                            continue
                    elif temp[k] != people[j][k]:
                        continue
                    count += 1
            if count == 5:
                number += 1
                                  
        answer[query[i][-1]] = number 
        
    return answer

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

Lv2, 백트래킹 문제다!

얼마전에 n - queen으로 백트래킹을 공부했지만, 아직 와닿지 않았는데 이 문제를 통해 확실히 알아둬야겠다

백트래킹이란?

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법을 말한다. 

문제 이해

퀸은 자신이 위치한 행, 열, 대각선에 위치한 퀸을 제거할 수 있다.

그렇기에 처음에 모든 퀸이 공격받지 않고 자리를 차지하려면 임의의 위치의 퀸에 대해 가로, 세로, 대각선에는 퀸이 없어야 한다. 

퀸을 놓았다가 다른 퀸이 공격할 수 있는 위치라면 철수하고 이전 단계로 가므로 백트래킹 문제다 

풀이 이해 

• queen에는 n개의 퀸 위치가 있고 단일 리스트이다.  인덱스는 행을 의미하고 원소는 열을 의미한다 (queen[1] = 2 -> 1행 2열에 퀸이 있음)
• n개의 퀸이 필요하므로 길이 n의 queen 리스트를 생성한 뒤, (0, 0)에 퀸을 넣고 n_queen(dfs)를 시작한다. 
• n_queen 함수()
  • x행의 0열부터 n - 1열까지 퀸을 위치시킨 뒤 해당 위치가 조건을 만족하는지 check()함수로 확인한다.
  • 조건(같은 행,  같은 열, 대각선에 퀸 없음)을 만족하는 퀸이라면 행 + 1한 후 재귀함수를 돌린다 
  • x 가 n이라면 이전에 멈추지 않고 끝까지 왔다는 뜻이므로 1을 반환한 후 result에 누적해 간다 
• check() 함수
  • 반복문의 범위가 0 ~ x - 1이므로 해당 퀸보다 안쪽에 있는 퀸 중에 같은 열에 있거나 대각선에 있는 퀸이 있다면 해당 퀸은 넘긴다 
  • 위에 해당하지 않는다면 조건을 만족하는 퀸이므로 반복문을 계속 진행한다.
  • 반복문이 끝날 때까지 False를 만나지 않았다면 해당 퀸은 위치해도 되는 퀸이므로 True를 반환한다 

- 정답 풀이 : 

참고한 블로그

def n_queen(n, x, queen):
    result = 0
    
    if x == n:
        return 1
        
    for i in range(n):
        queen[x] = i      
        if check(x, queen):
            result += n_queen(n, x + 1, queen)
            
    return result

def check(x, queen):
    for i in range(x):
        # x행의 퀸과 i행의 퀸의 열이 같다 or 두 퀸이 대각선에 위치해있다 
        if queen[x] == queen[i] or abs(x - i) == abs(queen[x] - queen[i]):
            return False
        
    return True

def solution(n):
    queen = [0] * n
    answer = n_queen(n, 0, queen)
    
    return answer

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

Lv2 문제다!

문제 이해

예제를 자세히 보니 약수관련 문제라고 생각했다.

소수 인덱스에서는 값이 모두 1이고, 합성수 인덱스에서는 자기보다 작은 약수 중 최대 약수가 값이었다.

그래서 begin에서 end까지 진행하면서 소수인지 합성수인지에 따라 분기문을 다르게 해서 진행하면 되겠다 싶었다. 

풀이 이해 

• 합성수에서 가장 큰 약수는 (합성수 // 가장 작은 약수)의 값이다.
• 그래서 작은 수부터 순차적으로 가다가 약수이고, 그 수로 나눈 몫이 1000만 이하인 수일 때의 값을 k에 저장한 뒤 j 반복문을 break 한다. (이러면 시간을 많이 아낄 수 있다)
• 1000만 이하인 걸 확인해야하는 이유 : 숫자 블럭의 최대는 1000만이지만 도로의 최대는 10억이기 때문이다
• 위의 과정을 거치지 않았다면 소수나 1인 경우이므로 따로 소수인 경우를 처리하지 않아도 된다.
• k값을 answer에 추가한 뒤 결과를 반환한다

- 정답 풀이 

참고한 블로그

import math

def solution(begin, end):
    answer = []
    for i in range(begin, end + 1):
        if i == 1:
            k = 0
        else:
            k = 1
        for j in range(2, int(math.sqrt(i)) + 1):
            if i % j == 0 and i // j <= 10000000:
                k = i // j
                break
        answer.append(k)
        
        
    return answer

- 시도해본 풀이 

문제 이해한 걸로 풀이를 작성했다.

정확성에서는 다 맞았는데, 효율성에서는 모두 통과하지 못했다.

아무래도 end가 최대 10억인 수라서 아래 연산으로는 시간이 많이 걸리는 것 같다 

효율성에서 시간초과는 이해하는데 실패는 어떤 의미일까?? 

import math

def isPrime(num):
    if num == 1:
        return False
    
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0:
            return False
        
    return True

def findFactor(num):
    factor = 0
    for i in range(2, int(math.sqrt(num)) + 1):
        if num % i == 0 and num // i <= 10000000:
            factor = num // i
            break
    
    return factor

def solution(begin, end):
    # 소수는 약수가 없으므로 무조건 1, 합성수는 자기보다 작은 최대 약수 
    answer = [0] * (end - begin + 1)
    
    for i in range(begin, end + 1):
        if isPrime(i):
            answer[i - begin] = 1
            
        else:
            answer[i - begin] = findFactor(i)

    return answer