Jang's coding blog

[LV2] 두 큐 합 같게 만들기 길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다 www.programmers.co.kr 문제 해설 이번 문제는 문제에서 설명하는 것처럼 큐를 사용해서 서로의 크기가 같아질 때까지 삽입과 추출하는 반복문을 돌려서 두 큐의 합이 같아질지 판별하면 되는데 여기서 중요한 점은 판별을 할 때의 범위를 정해야 한다. 이때 이 범위는 큐의 길이의 3배만큼 돌리게 되면 모든 경우의 수를 반복해볼 수 있기 때문에 ..

[LV2] 더 맵게 문제링크 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 www.programmers.co.kr 문제 해설 이번 문제는 heapq을 사용하여 최솟값을 항상 인덱스 0번에 위치시켜 조건에 맞는 식에 대입하여 다시 heapq에 넣어준 후 비교하면 되는 문제이다. import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) # 주어지는 맵기 리스트 heapq형태로 변환 while scoville[0] < K: tmp= heapq.heappop(scoville)+heapq.heappop(s..

[LV2] 거리두기 확인하기 문제링크 개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼 아래와 같은 규칙으로 대기실에 거리를 www.programmers.co.kr 문제 해설 이 문제는 전형적인 탐색문제이며 bfs를 활용하면 풀 수 있는 문제이다. 다만 여기서 조건은 사람이 있는 위치에서 +2칸 이내에 사람이 있으면 안된다는 것이다 이것을 활용한 코드는 다음과 같다. from collections import deque dx=[-1,1,0,0] dy=[0,0,-1,1] def bfs(loc,place): que=deque([loc]) #초기값 visited=[[False]*5 for _ in rang..

[LV2] 게임 맵 최단거리 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. www.programmers.co.kr 문제해설 이번문제는 최단거리를 구하는 문제이며 이런 문제의 경우가 대표적인 BFS 문제라고 볼 수 있다. bfs로 풀기 위해서는 각각의 위치를 좌표화 하여 움직일 수 있는부분의 시작지점에서 부터의 거리를 현재 위치 거리의 +1을 해주면 풀 수 있고 deque를 사용하여 현재 움직일 수 있는 위치를 확인하면 된다. from collections import deque def solution(maps): answer = 0 n=len(maps) #맵의 세로길이 확인 m=len..

[LV2] 프린터 문제링크 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했 www.programmers.co.kr 문제해설 이번 문제는 1번 조건을 보면 가장앞에 있는 문서를 뽑으라고 되어 있는데 이것을 보면 deque의 popleft를 떠올릴 수 있다. 시간복잡도 또한 O(1)이기 때문에 효율적인 방법이라고 생각이 되었고 각각의 중요도에 enumerate()를 사용하여 순번을 매겨주고 최대값과 비교하면서 반복문을 돌려주면 쉽게 풀 수 있다. from collections import deque def solution(priorities, location): ..

> [LV2] 뉴스 클러스터링 문제링크 여러 언론사에서 쏟아지는 뉴스, 특히 속보성 뉴스를 보면 비슷비슷한 제목의 기사가 많아 정작 필요한 기사를 찾기가 어렵다. Daum 뉴스의 개발 업무를 맡게 된 신입사원 튜브는 사용자들이 편리하게 다양한 뉴스를 찾아볼 수 있도록 www.programmers.co.kr #예제 입출력 str1 str2 answer FRANCE french 16384 handshake shake hands 65536 aa1+aa2 AAAA12 43690 E=M*C^2 e=m*c^2 65536 문제 해설 이번 문제는 자카드 유사도를 구현하는 문제이며 자카드 유사도를 모르더라도 문제에 설명되어 있는 것처럼 문자열을 2개씩 나눈 후 유사도=다중집합의 교집합/ 다중집합의 합집합 이 공식을 사용..

[LV2] 행렬 테두리 회전하기 문제링크 rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, www.programmers.co.kr 문제해설 이 문제는 단순하게 문제에서 요구하는 배열 회전을 통해서 풀면 되는 문제이며 침착하게 다음 단계를 이용하면 어렵지 않게 문제를 해결할 수 있다. 왼쪽테두리에 가장 위에 있는 숫자를 따로 저장한 후 나머지 숫자를 밑에서 부터 한칸씩 올리고 이 숫자들을 비교하여 작은 숫자를 저장한다. 아래테두리에 숫자들을 오른쪽에서 왼쪽으로 이동시키며 1단계와 같이 지금까지 중 제일 작은 숫자를 저장한다 오른쪽 테두리를 위에서 아래로 이동시키고 ..

[LV2] 메뉴 리뉴얼 문제링크 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. www.programmers.co.kr 문제해설 이번 문제는 각각의 주문들의 조합을 combinations 함수를 사용하여 구한뒤 Counter 를 사용하여 각각의 중복된 조합의 개수를 딕셔너리 형태로 저장하여 코스 구성에 필요한 메뉴수에 따라서 최대한의 수요를 파악한 후 이를 출력하면 되는 문제이다. from itertools import combinations from collections import Counter def solution(orders, course): answer = [] for c in course: comb=[] for order in or..

[LV2] 소수 찾기 문제링크 한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. www.programmers.co.kr 문제 해설 이 문제는 우선 문자열을 각각의 숫자로 자른 후 순열을 통해 숫자를 만들고 각각의 숫자가 소수인지 아닌지를 판단하면 되는 문제이며 소수 판별시에는 효율적인 코드를 작성하기 위해서 에라토스테네스의 체 알고리즘을 사용 하였다. from itertools import permutations import math def isprime(num): #에라토스테네스의 체 알고리즘을 사용한 소수판별 함수 if num

[LV2] 카펫 문제링크 셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, www.programmers.co.kr 문제해설 기본적으로 예시에서 알 수있듯이 노란블럭의 가로, 세로에 +2해준값이 전체블럭의 가로세로임을 알 수 있다. 또한 갈색 블록과 노란블럭의 관계식을 보면 갈색블럭=2*(노란블럭 가로 + 노란블럭 세로)+4임을 알 수 있음으로 이것을 구현하면 된다. def solution(brown, yellow): answer = [] tmp=[] width,height=1,1 #노란 블럭 가로세로의 최소값 선언 for i in range(yellow//2,0,-1): #만약 yello..