say repository

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://programmers.co.kr/learn/courses/30/lessons/17684

출처 : 프로그래머스

def solution(msg):
    answer = []
    dic = dict()
    for i in range(ord('A'), ord('Z')+1):
        dic[chr(i)] = i - ord('A') + 1
    start, end = 0, 1
    print(dic)
    idx = 27 # dic 처음의 다음 인덱스
    
    while end < len(msg)+1:
        w = msg[start:end]
        if w in dic:
            end += 1
        else:
            answer.append(dic[w[:-1]])
            dic[w] = idx # 인덱스 삽입
            idx += 1
            start = end -1   
    answer.append(dic[w])
    return answer

풀이

영어 대문자 문자열로 조건에 맞게 비교하며 슬라이싱하는 문제이다.

슬라이싱 인덱싱이 조금 헷갈린다..

알파벳에 맞는 색인 문자를 같이 입력해야하니까

알파벳 사전을 dict() 으로 구현한다.

   dic = dict()
    for i in range(ord('A'), ord('Z')+1):
        dic[chr(i)] = i - ord('A') + 1

이는 많이 나오니까 알아두자.

https://programmers.co.kr/learn/courses/30/lessons/12951#

출처 : 프로그래머스

출처 : 프로그래머스

def solution(s):
    answer = ''
    s = s.split(" ") # 공백이 연속해서 나올 수 있다.
    print(s)
    for ss in s:
        if ss == "": # 연속한 공백
            answer += " "
            continue # 다음 ss
            
        for i in range(len(ss)):
            if i == 0:
                a = ss[i].upper()
                answer += a
            else:
                b = ss[i].lower()
                answer += b
        answer += " " # 기존 단어 사이 띄어쓰기
        
    return answer[:-1] # 마지막 단어 뒤에도 공백 있어서 제거하기

풀이

공백이 연속해서 나올 수 있다는 조건 때문에 계속 틀렸다. 

조건을 반드시 확인하자.

그래서 s.split()으로 단어를 분리하지 않고, s.split(" ")으로 분리해서 공백도 리스트에 분리되어 넣어지게끔 했다.

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

출처 : 프로그래머스

from collections import defaultdict
def solution(tickets):
    answer = []
    dic = defaultdict(list) # 유사 딕셔너리 생성
    
    for a,b in tickets:
        dic[a].append(b)
    for k in dic.keys():
        dic[k].sort(reverse = True) # 위에 있는 걸 먼저 내보내야해서 reverse
    print(dic)
    
    #dfs
    stack = ['ICN']
    while stack:
        top = stack[-1]
        if not dic[top]: # dic에 없으면 pop
            answer.append(stack.pop())
        else:
            stack.append(dic[top].pop())
            
    return answer[::-1]

풀이

defaultdict(list) : list 타입의 유사 딕셔너리 생성됨.

출발지를 key로 하고 sort()에서 reverse = True을 한다.

이 이유는 stack에서 가장 top에 있는 것으로 비교를 해서 pop() 연산을 할 것인데 여기서 더 편하게 하기 위함이다.

dfs 진행은 첫 시작 stack에 'ICN' 을 넣어주고 시작한다.

stack은 가는 경로라고 생각하면 된다.

dic[top] 의 값이 모두 stack에 들어가서 없어졌을 때, 모든 경로를 다 돈 것이다.

이제 이 stack 경로에 있는 원소들을 pop() 해서 answer에 넣어준다.

이때, 원하는 답과 거꾸로 얻어지기 때문에 최종적으로 뒤집어줘야 한다. -> answer [::-1]

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

출처 : 프로그래머스

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort()
    q = deque(people)
    print(q)
    while q:
        if len(q) == 1: # 혼자면 끝
            answer += 1
            break
        elif q[0] + q[-1] <= limit: # 가장 작은 것, 큰 것을 제거하는게 효율적임
            answer += 1
            q.pop()
            q.popleft()
        else:
            q.pop() # 무거운 사람 먼저 나가기
            answer += 1
    return answer

풀이

어떻게 하면 최소의 보트에 두 명씩 구출할 수 있을지 생각했다.

우선 몸무게가 뒤죽박죽이니 오름차순으로 정렬해서 큐에 넣었다.

가벼운 사람부터 비교하는건 효율적이지 못하다.

가장 무거운 사람과 가장 가벼운 사람 두 명의 몸무게 합이 limit 이하면 최적의 조합이다.

이렇게 해서 큐에서 조건을 만족하면 pop() 한다.

2명의 조건이 맞지 않는다면 혼자라도 구명보트에 태워야 하는데,

이때, 무거운 사람부터 구출해야 탐욕적이다.