Jang's coding blog

[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..

[LV2] 튜플 문제링크 셀수있는 수량의 순서있는 열거 또는 어떤 순서를 따르는 요소들의 모음을 튜플(tuple)이라고 합니다. n개의 요소를 가진 튜플을 n-튜플(n-tuple)이라고 하며, www.programmers.co.kr 문제해설 이번 문제는 설명이 조금은 부족하지만 간단하게 생각해보면 문자열 s에있는 숫자들중 반복되는 횟수가 가장 많은 숫자부터 리스트에 넣으면 되는 문제이다. 여기서 입력받은 s는 {} , 등 문자가 있기때문에 replace를 사용하여 미리 삭제 해주었다. 그후 딕셔너리를 사용해서 각각의 숫자가 나온 횟수를 정리하고 이것을 정렬하여 리스트에 넣었다. def solution(s): answer = [] hash={} #숫자의 반복횟수를 나타내는 딕셔너리 s=s.replace('..

[LV2]위장 문제링크 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입 www.programmer.co.kr 문제 해설 이 문제는 같은 종류의 물건들을 제외한 조합 경우의수를 생각해보면 되는데 우선 같은 종류의 옷을 딕셔너리에 정리한 후 경우의수 구하는 공식인 *(n+1)을 해주면 모든 경우의 수가 나오게 된다. 여기서 마지막 -1은 아무 옷도 안입고 있을때를 의미한다. def solution(clothes): answer = 1 match={} #옷의 종류와 이름을 저장할 딕셔너리 for value,key in clothes: #딕셔너리에 옷의 종류와 이름 정리 if key in match..