그냥 코딩하는 사람의 블로그

- get_distance로 현재 알파벳에서 얼마나 돌려야 목표 알파벳이 나오는지 최소 이동거리 구해 준다.

- get_next로 왼쪽/오른쪽 얼마나 이동해야하는지 구하는데.. 그리디를 사용해야 된다고 해서 0이 아닌 수까지의 거리가 짧은 방향으로 이동하게끔 구현을 하였음. 하지만 왼쪽-오른쪽 위치가 같은 경우를 따로 처리하지 않았음에도 정답이 나와서 이상함..

- 여튼, 매 순간 최소 이동거리와 돌려야 하는 횟수를 더해주면 된다.

def get_distance(c):
    p1 = abs(ord(c) - ord('A')) # 정방향
    p2 = abs(ord('Z') - ord(c) + 1) # 역방향
    return min(p1, p2)

def get_next(arr, idx):
    p = idx
    right_move = 0
    while True:
        p = (p + 1) % len(arr)
        right_move += 1
        if arr[p] != 0:
            break

    t = idx
    left_move = 0
    while True:
        t = (t - 1) % len(arr)
        left_move += 1
        if arr[t] != 0:
            break

    if right_move <= left_move:
        return (p, right_move)
    else:    
        return (t, left_move)



def solution(name):
    answer = 0

    distance = [0] * len(name)
    for i, p in enumerate(name):
        distance[i] = get_distance(p)

    answer = distance[0]
    distance[0] = 0
    idx = 0
    while sum(distance) != 0:
        idx, movement = get_next(distance, idx)
        answer += movement
        answer += distance[idx]
        distance[idx] = 0

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 1, 2, 3, 4, 5, 6, 7, 8을 예시로 들었을때, 다음 라운드에서는 (1, 2 승자), (3, 4 승자), (5, 6 승자), (7, 8 승자)가 도달한다.

- 즉, 본인의 위치가 큰 순서 // 2로 줄게 된다. 따라서 작은 순위인 경우에는 큰 순위로 맞춰준 다음(+1) 2로 나눈다.

- 진행하다가 a == b, 즉, 작은 순위 + 1 = 큰 순위가 될 때 맞붙게 되므로, 그때의 라운드를 리턴해주면 된다.

def solution(n,a,b):
    answer = 1

    while True:
        if a % 2 == 1:
            a = a + 1
        if b % 2 == 1:
            b = b + 1
        if a == b:
            break
        answer += 1
        a = a // 2
        b = b // 2


    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 전화번호 전체를 자릿수 기준으로 정렬

- 자릿수가 낮은 전화번호부터 자리수를 늘려가면서 딕셔너리에 있는지 없는지 조사

- 딕셔너리에 있다면 접두사가 있는것이므로 false로 바꾸고 리턴

- 모든 케이스에서 없다면 true 리턴

def solution(phone_book):
    answer = True
    dic = {}
    phone_book.sort(key=lambda x:len(x))
    for phone in phone_book:
        for i in range(len(phone)):
            if dic.get(phone[:i]) != None:
                answer = False
        if answer == False:
            break
        dic[phone] = 1

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 우선순위를 저장해둘 prior_copy를 만들어 둔 다음에 오름차순으로 정렬을 시킨다.

- 즉, prior_copy의 마지막 요소가 출력되어야 하는 요소의 우선순위

- queue를 돌면서 우선순위가 가장 높으면 출력하고, 아니라면 큐의 마지막에 넣어야 한다, 하지만 우선순위가 같은 케이스도 있으므로 우선순위와 인덱스를 같이 queue에 넣어둔다.

- 우선순위가 가장 높은걸 출력하되, 문제의 location을 프린터가 출력할 때, 해당 location이 몇번째로 출력되는지 나타내면 된다.

import copy
from collections import deque

def solution(priorities, location):
    prior_copy = copy.deepcopy(priorities)
    prior_copy.sort()
    queue = deque()
    for i, pr in enumerate(priorities):
        queue.append([pr, i]) # 우선순위랑 해당 인덱스 같이 삽입
    answer = 0

    while queue:
        pr, idx = queue.popleft()
        if pr == prior_copy[-1]:
            answer += 1
            if idx == location:
                break
            prior_copy.pop()
        else:
            queue.append([pr, idx])

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- main에 모두 사용하면 너무 복잡해질거 같아 rotate 함수 만들어 둠.

- 다음 예제에서는 먼저 왼쪽 위의 8을 따로 저장해둔 다음 반시계방향으로 한칸씩 밀리도록 구현한 뒤, 마지막 숫자인 8을 따로 [x1, y1+1]에 저장해두면 회전이 완료된다.

- 회전 과정에서는 매 순간 최솟값을 갱신해 주고, 회전이 종료되면 최솟값을 리턴한다.

def rotate(matrix, x1, y1, x2, y2):
    minvalue = 999999999
    last = matrix[x1][y1]

    for i in range(x1, x2):
        matrix[i][y1] = matrix[i+1][y1]
        minvalue = min(minvalue, matrix[i+1][y1])

    for j in range(y1, y2):
        matrix[x2][j] = matrix[x2][j+1]
        minvalue = min(minvalue, matrix[x2][j+1])

    for i in range(x2-1, x1-1, -1):
        matrix[i+1][y2] = matrix[i][y2]
        minvalue = min(minvalue, matrix[i][y2])

    for j in range(y2-1, y1, -1):
        matrix[x1][j+1] = matrix[x1][j]
        minvalue = min(minvalue, matrix[x1][j])

    matrix[x1][y1+1] = last
    minvalue = min(minvalue, last)
    return minvalue

def solution(rows, columns, queries):
    answer = []

    matrix = [[0] * (columns + 1) for _ in range(rows + 1)]
    for i in range(1, rows+1):
        for j in range(1, columns+1):
            matrix[i][j] = columns*(i-1)+j

    for query in queries:
        answer.append(rotate(matrix, query[0], query[1], query[2], query[3]))

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 처음 구현한 소스에서는 맨 앞자리 수를 반복해서 등장시켰더니 1~6번 케이스가 틀림.

- 이를 전체 자리수를 반복해서 등장시키니 맞게 나온다. sort에서는 값이 같다면 반복시킨 횟수가 많은 걸 먼저(짧은 것을 먼저) 나타나게 함.

- 000000 같은 케이스 방지를 위해 int형 변환 후 다시 str형으로 변환.

def solution(numbers):
    answer = ''

    num = list(map(str, numbers))
    temp = []
    for i in num:
        if len(i) <= 4:
            temp.append([i * 3, len(i * 3) - len(i)])

    temp.sort(key=lambda x:(x[0], -x[1]), reverse=True)
    for t in temp:
        answer += t[0][:(len(t[0]) - t[1])]

    answer = str(int(answer))
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 구현 문제

- 대/소 구분 없다 하였으므로 소문자로 모두 치환 및 두자리씩 끊어서 알파벳으로만 이루어진 경우 유사도 집합을 만들어 줌. 이 때 딕셔너리 타입으로 개수만 저장해 둔다. set1[두자리 문자]=나타난 개수

- 교집합의 경우는 하나의 딕셔너리를 잡고, 키들을 두 개의 딕셔너리에 따라 값을 비교한 뒤 최솟값을 더해주면 된다. 단, 키에 대응하는 값이 없는 경우는 0으로 간주

- 합집합의 경우는 두개의 딕셔너리를 모두 보면서, 최댓값을 더해주면 된다.

- 마지막으로 두 딕셔너리의 키가 모두 0인 경우는 유사도 1로 간주하라고 문제에서 나타났으므로, 1 * 65536 = 65536으로 써주고, 아닌 경우는 교집합의 수 / 합집합의 수 * 65536을 해준 뒤 int 함수를 사용해서 소숫점을 버리면 된다.

def solution(str1, str2):
    answer = 0
    str1 = str1.lower()
    str2 = str2.lower()

    set1 = {}
    set2 = {}

    # 유사도 집합 만드는 과정(str1, str2)
    for i in range(len(str1) - 1):
        if str1[i:i+2].isalpha():
            if set1.get(str1[i:i+2]) != None:
                set1[str1[i:i+2]] += 1
            else:
                set1[str1[i:i+2]] = 1

    for i in range(len(str2) - 1):
        if str2[i:i+2].isalpha():
            if set2.get(str2[i:i+2]) != None:
                set2[str2[i:i+2]] += 1
            else:
                set2[str2[i:i+2]] = 1

    intersects = 0
    union = 0
    visited = set()

    # 합집합, 교집합의 원소 개수 구하는 과정
    for k in set1.keys():
        if set2.get(k) != None:
            intersects += min(set1.get(k), set2.get(k))
        t1 = set1.get(k)
        t2 = 0 if set2.get(k) == None else set2.get(k)
        union += max(t1, t2)
        visited.add(k)


    for k in set2.keys():
        if k not in visited:
            visited.add(k)
            union += set2.get(k)

    # 유사도 계산
    if len(set1.keys()) == 0 and len(set2.keys()) == 0:
        answer = 65536
    else:
        answer = int(intersects * 65536 / union)  

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- bfs로 최단 경로를 찾아 준다.

- visited를 따로 두어 방문했던 정점을 다시 방문하지 않도록 함.

- bfs에서는 목적지에 처음 도달하였을 때가 최단 경로이므로 목적지에 도달하기만 하면 바로 return해주면 된다.

- queue가 비었을 때는 목적지로 갈수가 없는 케이스이므로 -1 리턴

from collections import deque

def bfs(maps):
    queue = deque()
    maxX = len(maps) - 1
    maxY = len(maps[0]) - 1
    visited = [[False] * (maxY + 1) for _ in range(maxX + 1)]
    queue.append([0, 0, 1])

    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    visited[0][0] = True

    while queue:
        cx, cy, c = queue.popleft()
        if cx == maxX and cy == maxY:
            return c

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx and nx <= maxX and 0 <= ny and ny <= maxY:
                if visited[nx][ny] == False and maps[nx][ny] == 1:
                    visited[nx][ny] = True
                    queue.append([nx, ny, c+1])

    return -1

def solution(maps):
    return bfs(maps)

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 한개~전체 고르는것 까지 모두 permutation으로 경우의 수 계산

- 이후 겹치는 경우들도 있으므로 방문한 케이스들을 visited에 저장 및 재방문 시 생략

- 소수 구할때는 2~n의 제곱근까지만 검사하여 시간 단축

from itertools import permutations
import math

def check_prime(n):
    if n <= 1:
        return False
    elif n == 2:
        return True
    for i in range(2, int(math.sqrt(n))+1):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    answer = 0
    visited = set()
    for i in range(1, len(numbers)+1):
        allcase = list(permutations(numbers, i))
        for case in allcase:
            temp = int("".join(case))
            if temp not in visited:
                visited.add(temp)
                if check_prime(temp):
                    answer += 1
    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges

- 우선 모든 요소를 최소 히프에 넣어 준다.

- 히프의 맨 앞 요소(최솟값)이 k 이상이라면 종료하고, heap의 크기가 한개이면서, k 이상도 아니라면 스코빌 지수를 k 이상으로 할 수 없는 것이므로 -1로 변경한다.

- 최소 히프에서 두개의 요소를 꺼낸다(최솟값, 그다음 최솟값)

- 공식에 따라 최솟값 + 그다음 최솟값 * 2 한 값을 최소 히프에 다시 넣는 과정을 최솟값이 k 이상이 될때까지 반복한다.

import heapq

def solution(scoville, K):
    answer = 0
    heap = []
    for s in scoville:
        heapq.heappush(heap, s)

    while True:
        if heap[0] >= K:
            break
        if len(heap) == 1:
            answer = -1
            break
        t1 = heapq.heappop(heap)
        t2 = heapq.heappop(heap)
        t = t1 + t2*2
        heapq.heappush(heap, t)
        answer += 1


    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges