say repository

https://programmers.co.kr/learn/courses/30/lessons/72412?language=python3 

출처 : 프로그래머스

https://tech.kakao.com/2021/01/25/2021-kakao-recruitment-round-1/

코드

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

def solution(info, query):
    answer = []
    dic = defaultdict(list)
    for i in info:
        i = i.split()
        cond = i[:-1]
        score = int(i[-1])
        for i in range(5):
            cases = list(combinations([0,1,2,3],i))
            # print(cases)
            for case in cases:
                tmp = cond.copy()
                for c in case:
                    tmp[c] = '-'
                key = ''.join(tmp)
                dic[key].append(score)
    # print(dic)
    
    for val in dic.values():
        val.sort()
    
    for q in query:
        q = q.replace("and ", "")
        q = q.split()
        target_cond = ''.join(q[:-1])
        target_score = int(q[-1])
        cnt = 0
        if target_cond in dic:
            target_list = dic[target_cond]
            # print(target_list)
            idx = bisect_left(target_list, target_score)
            cnt = len(target_list) - idx
        answer.append(cnt)
    return answer

풀이

query 문과 info의 조건을 모두 비교해서 풀면 효율성에서 합격하지 못한다.

효율성에서 통과되지 못해서 카카오 풀이를 참고했다.

1) info 에 있는 조건으로 만들 수 있는 모든 경우의 수를 key로 갖고있는 defaultdict를 생성해야한다.

key는 모든 조건, 값은 score 로 갖는 defaultdict 를 생성한다.

2) 이렇게 생성된 dic는 score 값을 기준으로 오름차순 정렬한다.

3) 이제 query와 비교하여 찾는다.

query에 조건이 info의 key로 있다면 score 값들을 target_list 로 가져온다.

4) 여기서 또, 하나하나 찾는다면 효율성에 문제가 생긴다.

빠르게 탐색하기 위해 순차탐색 보다는 이진탐색을 활용하자.

bisect_left 를 이용하여 target_list 에서 target_score 가 있는 인덱스를 구하고

이 인덱스를 전체 target_list 에서 빼준다면 정답에 추가할 cnt 가 된다.

https://programmers.co.kr/learn/courses/30/lessons/42860

출처 : 프로그래머스

코드

def solution(name):
    answer = 0
    # 최소 이동은 문자열 길이 -1
    move = len(name)-1
    
    # 조이스틱 상하 이동으로 알파벳 최소 차이
    for i, alp in enumerate(name):
        answer += min(ord(alp)-ord('A'), ord('Z')-ord(alp)+1)
        
        # 연속된 'A' 발견하면 넘어가기
        moving_idx = i + 1
        while moving_idx < len(name) and name[moving_idx] == 'A':
            moving_idx += 1
            
        # 현재 최소 이동과 조이스틱 좌로 움직이거나 우로 움직이는 것 간의 최소 이동 횟수 구하기
        move = min([move, i*2 + (len(name)-moving_idx), i + 2*(len(name)-moving_idx)])
        
    answer += move
    return answer

풀이

그리디 알고리즘이라기보다는 부르트포스 알고리즘이다.

가능한 경우는 모두 탐색한다.

최소 이동은 처음부터 -> 로 계속 이동하는 경우로 문자열 길이 -1 이다.

이제는 조이스틱을 상하 로 이동하는 알파벳 이동의 개수를 구해보자.

A~Z 사이에 있는 알파벳은 A 부터의 조이스틱 이동 횟수와 Z 에서 시작한 조이스틱 이동 횟수의 최소값으로 구한다.

        answer += min(ord(alp)-ord('A'), ord('Z')-ord(alp)+1)

그리고 다시 조이스틱 좌우 이동횟수를 구해야한다.

이 때, A가 있으면 넘어가야한다.

그리고 현재 최소 이동 ( 문자열 길이 -1) 와 

A 기준으로 왼쪽에서 움직이거나 A 기준 오른쪽에서 움직이는 이동 횟수 중 가장 최소 값을 구해서

최종 answer에 더해준다.

        # 현재 최소 이동과 조이스틱 좌로 움직이거나 우로 움직이는 것 간의 최소 이동 횟수 구하기
        move = min([move, i*2 + (len(name)-moving_idx), i + 2*(len(name)-moving_idx)])

https://programmers.co.kr/learn/courses/30/lessons/77485

출처 : 프로그래머스

풀이

matrix을 초기화 한다.

초기화 하는 방법은 어렵지 않다.

위의 그림은 회전 그림이다.

(x1, y1, x2, y2) 기준으로 회전을 한다.

처음에 노랗게 칠한 (2,2)을 tmp_min 변수에 저장한다. 

왼쪽부터 아래에 있는 것을 하나씩 위로 올린다.

왼쪽, 아래, 오른쪽, 위 순서대로 회전 코드를 썼다.

하나씩 밀다보면 matrix[x1][y1+1] 가 비어서 여기에 처음에 저장한 tmp_min을 넣어준다.

또, 주의할 점은 오른쪽과 위의 요소를 밀 때, 포문을 역순으로 돌아야 한다.

코드

def solution(rows, columns, queries):
    answer = []
    matrix = [[0 for c in range(columns + 1)] for r in range(rows + 1)]  # 초기화
    # 아무 회전도 안했을 때
    n = 1
    for i in range(1, rows + 1):
        for j in range(1, columns + 1):
            matrix[i][j] = n
            n += 1

    for x1, y1, x2, y2 in queries:
        tmp_min = matrix[x1][y1]
        tmp_copy = tmp_min

        # 회전
        for k in range(x1, x2):  # 왼쪽
            tmp = matrix[k+1][y1]
            matrix[k][y1] = tmp
            tmp_copy = min(tmp_copy, tmp)

        for k in range(y1, y2):  # 아래
            tmp = matrix[x2][k+1]
            matrix[x2][k] = tmp
            tmp_copy = min(tmp_copy, tmp)

        for k in range(x2, x1, -1):  # 오른쪽
            tmp = matrix[k-1][y2]
            matrix[k][y2] = tmp
            tmp_copy = min(tmp_copy, tmp)

        for k in range(y2, y1, -1):  # 위
            tmp = matrix[x1][k-1]
            matrix[x1][k] = tmp
            tmp_copy = min(tmp_copy, tmp)

        # 회전 마치고 바꾸기
        matrix[x1][y1+1] = tmp_min
        answer.append(tmp_copy)

    return answer

https://programmers.co.kr/learn/courses/30/lessons/87946

출처 : 프로그래머스

코드

from itertools import permutations
def solution(k, dungeons):
    answer = 0
    max_len = len(dungeons) # 던전 길이로 순열 만들어야함
    
    #순열
    for dungeon in permutations(dungeons,max_len):
        tmp = 0 # 정답 관리
        tmp_k = k # 피로도 k 복사
        
        for d1,d2 in dungeon:
            if tmp_k >= d1:
                tmp_k -= d2
                tmp += 1
        if tmp > answer:
            answer = tmp
    return answer

풀이

순열 리스트로 모든 경우의 수를 만든다.

이 모든 경우의 수를 완전 탐색하여 정답을 구한다.

https://programmers.co.kr/learn/courses/30/lessons/42839?language=python3 

출처 : 프로그래머스

코드

from itertools import permutations
import math as m

def isPrime(n):
    if n<2:
        return False
    for i in range(2,int(m.sqrt(n))+1):
        if n%i == 0:
            return False
    return True
    
def solution(numbers):
    answer = 0
    numbs = [n for n in numbers]
    permu = [] # 순열리스트
    
    for i in range(1, len(numbs)+1):
        permu += list(permutations(numbs,i))
    
    permu1 = [int(''.join(p)) for p in permu]
    permu1 = list(set(permu1))

    for p in permu1:
        if isPrime(p):
            answer += 1
    return answer

풀이

소수판별은 에라토스테네스의 체 알고리즘으로 풀이했다.

하지만 이 문제에서는 numbers에 있는 문자열로 이루어질 수 있는 모든 숫자 조합이 소수인지 아닌지를 판별하는 것이 문제이다.

이를 해결하기 위해, 순열의 방법을 사용했다.

python 에서의 순열은 permutations이다.

길이가 0인 순열은 관련이 없으니, 1부터 numbers의 길이만큼 순열리스트를 만들었다.

또한, 순열 리스트에 있는 문자열을 숫자로 바꿔줬고, 중복을 제거하기 위해 set()을 적용하고 다시 list()로 바꾸었다.

이제 이 순열 리스트에 있는 것이 소수 판별 함수를 통해 소수를 판별했다.

https://www.acmicpc.net/problem/15685

출처 : 백준

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

1. 시작 점
2. 시작 방향
3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

1세대 드래곤 커브는 0세대 드래곤 커브를 끝 점을 기준으로 시계 방향으로 90도 회전시킨 다음 0세대 드래곤 커브의 끝 점에 붙인 것이다. 끝 점이란 시작 점에서 선분을 타고 이동했을 때, 가장 먼 거리에 있는 점을 의미한다.

2세대 드래곤 커브도 1세대를 만든 방법을 이용해서 만들 수 있다. (파란색 선분은 새로 추가된 선분을 나타낸다)

3세대 드래곤 커브도 2세대 드래곤 커브를 이용해 만들 수 있다. 아래 그림은 3세대 드래곤 커브이다.

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

import sys
n = int(sys.stdin.readline())
dx = [1, 0, -1, 0]
dy = [0, -1, 0, 1]
graph = [[0]*101 for _ in range(101)]

for i in range(n):
    x, y, d, g = map(int,sys.stdin.readline().split())
    graph[x][y] = 1

# 커브 변화 배열 만들기
    curv = [d]
    for ge in range(g):
        for c in range(len(curv)-1, -1, -1):
            curv.append((curv[c]+1) % 4)
            
# 드래곤 커브 돌면서 방문 표시
    for i in range(len(curv)):
        x += dx[curv[i]]
        y += dy[curv[i]]
        if 0 <= x <= 100 and 0 <= y <= 100:
            graph[x][y] = 1

# 1x1인 정사각형의 네 꼭짓점이 모두 드래곤 커브인 경우 개수
answer = 0
for i in range(100):
    for j in range(100):
        if graph[i][j] == 1 and graph[i+1][j] == 1 and graph[i][j+1]==1 and graph[i+1][j+1]==1:
            answer += 1
print(answer)

풀이

시작 방향 d를 보면

0 (1, 0)

1 (0, -1)

2 (-1, 0)

3 (0, 1)

다음과 같다.

세대 별로 방향의 변동의 규칙을 찾아보면 위의 그림과 같다.

인접한 방향 배열에서 1을 더하는 것이다.

npm ERR! A complete log of this run can be found in:

npm cache clean --force 

rm -rf node_modules
npm install

---

error:

Attempted import error: 'Outlet' is not exported from 'react-router-dom' (imported as 'Outlet').

npm install react-router-dom@v6