📖 문제[프로그래머스] [2021 카카오 채용연계형 인턴십] 거리두기 확인하기 (파이썬/Python)난이도: Level 2유형: 완전탐색, BFS 문제 요약개발자를 희망하는 죠르디가 카카오에 면접을 보러 왔다. 코로나 바이러스 감염 예방을 위해, 응시자들은 대기실에서 일정한 거리를 두고 앉아야 한다. 각 대기실은 5x5 크기로, 총 5개의 대기실이 주어진다. 규칙 요약:응시자끼리는 맨해튼 거리 2 이하로 앉으면 안 된다.단, 거리 2 이내라도 파티션(X) 으로 막혀 있다면 예외적으로 허용한다. 문자 의미:`P`: 사람이 앉아있는 자리`O`: 빈 테이블`X`: 파티션 문제 요구사항:5개의 대기실이 2차원 문자열 배열 형태로 주어진다.각 대기실에 대해 거리두기를 지키고 있다면 `1`, 위반한 사람이 단 한..

📖 문제[프로그래머스] 게임 맵 최단거리 (파이썬/Python) (자바/Java)난이도: Level 2유형: BFS풀이 시간: 28분문제 요약캐릭터가 `(1,1)`에서 시작해 상대 팀 진영 `(n,m)`까지 이동해야 한다.이동할 수 있는 곳은 1, 이동할 수 없는 벽은 0으로 표시된다.최소 칸 수로 상대 진영에 도착하는 경우의 칸 수를 반환하라.도달할 수 없다면 -1을 반환한다.캐릭터는 상하좌우 네 방향으로 한 칸씩 이동 가능하다.맵 밖으로 나갈 수 없고, 벽(0)은 통과할 수 없다.🔍 문제 접근💡 문제 분석핵심 키워드: 최단거리, 동서남북으로 이동 ⇒ BFS 유형!동서남북으로 인접한 칸만 탐색할 수 있다.`maps`에는 0이 벽을 의미하고 1이 벽이 없는 자리를 의미한다.즉, 매번 이동할 때마다 ..

📖 문제[프로그래머스/PGS] 타겟 넘버 (파이썬/Python) (자바/Java)난이도: Level 2유형: DFS(백트래킹)풀이 시간: 30분문제 요약`n`개의 음이 아닌 정수들이 있을 때, 정수들의 순서 변화 없이 더하거나 빼서 `target`과 동일한 값을 만들고자 한다.숫자가 담긴 배열 `numbers`, 타겟 넘버 `target`이 주어질 때, 숫자를 적절히 더하고 빼서 타겟 넘버를 만들 수 있는 방법의 수를 구하라. [1, 1, 1, 1, 1]로 숫자 3을 만드는 방법은 아래와 같이 5가지 방법이 존재한다.-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3🔍 문제 접근💡 문제 분석이 문제는 각 숫자에 대해 더하거나..

📖 문제[프로그래머스] 점프와 순간이동 (파이썬/Python)난이도: Level 2유형: 그리디, 이진수 변환, 수학적 사고문제 요약아이언 슈트를 입고 거리가 `N`만큼 떨어진 목적지에 최소의 건전지 사용량으로 도달해야 한다.가능한 이동 방식은 '앞으로 `K`칸 점프(건전지 소비)' 또는 '순간이동(거리 × 2, 건전지 소모 없음)'이다.🔍 문제 접근💡 문제 분석`K`칸 앞으로 점프하면 점프하면 `K`만큼 건전지를 사용한다.순간이동은 거리를 2배로 늘리지만 건전지를 소모하지 않는다.결국 목적지 `N`까지 갈 때 점프를 최소화하는 것이 목표이다. 🧠 풀이 아이디어일반적으로 0부터 `N`까지 "가는" 방향으로 접근하면 경우의 수가 너무 많다.반대로 `N`에서 0으로 "되돌아오는" 방식으로 생각하면 단..

📖 문제[프로그래머스] 문자열 내 마음대로 정렬하기 (파이썬/Python) (자바/Java)난이도: Level1유형: 문자열, 구현, 정렬풀이 시간: 약 10분 (자바 개선 포함 30분)문제 요약문자열로 구성된 리스트 `strings`와 정수 `n`이 주어진다. 각 문자열의 `n`번째 인덱스 문자를 기준으로 오름차순 정렬하되, 해당 문자가 동일한 경우 사전순으로 정렬해야 한다.🔍 문제 접근🧠 풀이 아이디어문자열 정렬 기준이 `n`번째 문자이므로, 이 기준을 우선 정렬에 반영해야 한다.다만 동일한 문자일 경우 사전순으로 정렬해야 한다.이를 위해서먼저 오름차순으로 정렬한다.이후, n번째 글자를 기준으로 오름차순 정렬한다.파이썬의 경우 `lambda`로 정렬한다.자바의 경우 `Arrays.sort` + ..

📖 문제[프로그래머스] 뉴스 클러스터링 (파이썬/Python)난이도: Level 3유형: 구현, 문자열, 다중집합문제 풀이 시간: 1시간 30분문제 요약두 문자열의 유사도를 자카드 유사도 방식으로 계산하는 문제이다.자카드 유사도J(A, B) = (A와 B의 교집합 크기) // (A와 B의 합집합 크기)이때 A, B가 모두 공집합일 경우, J(A, B) = 1문자열을 2글자씩 끊어 다중집합을 만든 후, `자카드 유사도 x 65536`을 한 후 소수점 아래를 버린 정수를 구해야 한다.여기서 다중 집합이란, 중복 원소를 허용하는 집합을 의미한다.이때 주의할 것은 합집합이 공집합일 경우 유사도는 1로 설정해야 한다.🔍 문제 접근🧠 풀이 아이디어다중집합 만들기문자열을 2글자씩 끊기두 글자가 모두 알파벳일 때..

📖 문제[프로그래머스] # 프렌즈4블록 (파이썬/Python)난이도: Level 3 같은 Level 2유형: 구현문제 요약같은 문자가 2×2 형태로 붙어 있으면 해당 블록들을 모두 지우고, 위에 있는 블록이 아래로 떨어지는 게임이다.이 과정을 반복하면서 최종적으로 지워진 블록의 총 개수를 구하는 문제이다.🔍 문제 접근💡 문제 분석꼭 해야 하는 부분을 정리하면 다음과 같다2×2 탐색: 모든 칸에 대해 2×2 범위의 블록이 같은지 확인한다.2x2 삭제 처리: 한 번에 지워질 블록들을 표시한 뒤 삭제한다.중력 처리: 삭제된 칸 위에 있는 블록들을 아래로 떨어뜨린다.반복: 지울 블록이 더 이상 없을 때까지 위 과정을 반복한다. 🧠 풀이 아이디어문자열로 된 입력을 2차원 리스트로 바꾼다.각 라운드마다 다음..

📖 문제[프로그래머스] #완주하지 못한 선수 (자바/Java)난이도: Level 1유형: 구현, 해시문제 요약마라톤에 참여한 선수들의 이름이 `participant` 배열에 주어진다.그 중 완주한 선수들의 이름은 `completion` 배열에 담겨 있다.단 한 명의 선수만 완주하지 못했으며, 해당 선수의 이름을 찾아서 반환해야 한다. 🔍 문제 접근💡 문제 분석`participant` 길이는 `completion`보다 1 크다.동명이인이 있을 수 있으므로 단순히 배열에 있는지 없는지를 비교하면 안 된다.정렬 후 비교하거나, `HashMap`을 이용한 카운팅 방식으로 문제를 해결할 수 있다. 🔍 문제 풀이1) 정렬을 이용한 풀이🧠 풀이 아이디어두 배열을 정렬한다.인덱스를 하나씩 순차적으로 비교하면서..

📖 문제[프로그래머스] #구명보트 (자바/Java)난이도: Level 2유형: 그리디, 투포인터문제 요약무인도에 갇힌 사람들을 구명보트를 이용해 구출해야 한다.구명보트는 최대 2명까지만 탈 수 있으며, 무게 제한이 있다.사람들의 몸무게가 담긴 배열 `people`과 보트의 무게 제한 `limit`가 주어진다.모든 사람을 구출하는 데 필요한 최소 보트 수를 구하라.🔍 문제 접근💡 문제 분석각 보트에는 최대 2명만 탈 수 있다.두 사람의 몸무게 합이 `limit`보다 작거나 같을 경우 같이 탈 수 있고, 그렇지 않으면 한 명만 태워야 한다.이 조건에 따라 최소 보트 수를 구하려면, 몸무게 순서대로 정렬한 후, 가벼운 사람과 무거운 사람을 짝지어 보는 전략이 필요하다.이러한 동작 방식은 “투포인터 알고리..