본문 바로가기
728x90

프로그래머스(Java)/Level 2

 (51)
[프로그래머스] 124 나라의 숫자 코드 힌트3진법과의 차이점124 나라의 숫자는 일반적인 3진법과 다르게 0 대신 4를 사용합니다.따라서, 나머지가 0일 때 몫에서 1을 빼는 것이 중요합니다. 이를 통해 1, 2, 4 세 숫자만 사용됩니다.StringBuilder 활용숫자를 계산한 후 바로 문자열에 추가하지만, 추가되는 순서는 뒤집힌 상태이기 때문에 마지막에 reverse()로 순서를 반전해야 합니다.몫과 나머지의 조정나머지가 0인 경우, 몫에서 1을 빼는 이유는 4를 0처럼 처리하기 위해서입니다.예를 들어, n = 3인 경우 '4'가 나와야 하는데, 이때 몫에서 1을 빼서 올바른 계산이 됩니다.예시n = 1 → "1"n = 2 → "2"n = 3 → "4"n = 4 → "11"이 문제의 핵심3진법을 변형하여 1, 2, 4만 사용하기 때..
[프로그래머스] 전력망을 둘로 나누기 코드 힌트인접 행렬 사용:map 배열은 전선의 연결 상태를 기록하는 인접 행렬로, 두 노드가 연결되면 map[i][j] = 1로 설정합니다.전선 끊기:모든 전선을 하나씩 끊어보고 각 경우에 대해 두 네트워크로 나누어진 후, 그 크기 차이를 계산합니다.cutWire() 함수에서 끊은 전선은 다시 복구됩니다.DFS(깊이 우선 탐색):DFS를 이용하여 한 네트워크의 노드 개수를 계산합니다. 한쪽 네트워크를 탐색한 후, 나머지 네트워크의 크기는 전체에서 빼는 대신 다시 탐색합니다.최솟값 계산:각 전선을 끊었을 때 두 네트워크의 크기 차이를 계산하고, 그 차이의 최솟값을 갱신합니다. 정답은 더보기 클릭더보기import java.util.*;class Solution { // 방문 여부를 체크하는 배열..
[프로그래머스] [PCCP 기출문제] 3번 / 충돌위험 찾기 코드 힌트큐(Queue)를 활용한 경로 추적:각 로봇의 이동 경로는 Queue 형태로 기록되며, 큐에 기록된 좌표를 순차적으로 꺼내어 로봇의 이동을 추적합니다.각 로봇이 특정 좌표에 도착하면, 그 좌표를 맵에 기록하고, 두 로봇 이상이 동일한 좌표를 지나간 경우를 찾아내는 방식입니다.위험 구역 계산:각 로봇의 다음 이동 위치를 확인하고, 101x101 크기의 이차원 배열을 사용해 해당 위치에 몇 개의 로봇이 지나갔는지 기록합니다.만약 두 개 이상의 로봇이 같은 위치를 지나가면 그 좌표는 위험 구역으로 간주되며, result 값을 증가시킵니다.경로 기록:각 로봇의 시작 좌표와 경로를 큐에 기록합니다.좌표 이동 방식은 먼저 y 좌표를 맞추고, 그 다음에 x 좌표를 맞추는 방식입니다. 이를 통해 로봇이 직선 ..
[프로그래머스] 호텔 대실 코드 힌트1. 예약 시간 변환입력으로 받은 예약 시간을 분 단위로 변환해요.종료 시간에는 10분의 추가 시간을 더해 방 정리 시간을 고려합니다.2. 시간 정렬예약 시간을 시작 시간을 기준으로 오름차순 정렬하여 처리 순서를 쉽게 만듭니다.3. 방 배정각 예약 시간을 기존의 방에 할당할 수 있는지 확인합니다.방이 겹치지 않으면 기존 방에 예약을 추가하고, 겹치면 새로운 방을 생성합니다.4. 최종 결과모든 예약을 방에 할당한 후 필요한 방의 개수를 반환합니다.  정답은 더보기 클릭더보기import java.util.*;class Solution implements Comparator { // 주어진 예약 시간을 기준으로 필요한 방 개수를 계산하는 메소드 public int solution(S..
[프로그래머스] 시소 짝꿍 코드 힌트1. 빠르게 탐색할 수 있는 자료구조처음 문제를 풀었을 때는 2중 for문을 사용하여 풀었지만, 시간이 많이 소요되어 시간 복잡도 문제가 발생했습니다.빠르게 요소를 찾기 위해 이진 탐색을 사용하는 방법을 고려했습니다.여기서는 HashMap을 사용하여 key는 요소(무게), value는 해당 요소의 빈도로 활용하여 문제를 풀었습니다.2. 짝꿍 맞추기시소 짝꿍이 되는 조건은 두 무게가 같은 비율일 때입니다.예를 들어, 무게가 2(m), 3(m), 4(m)인 지점에 좌석이 있을 때, 두 좌석 간의 비율이 같으면 짝꿍이 됩니다.즉, w1 * {2, 3, 4} == w2 * {2, 3, 4} 조건 중 하나라도 만족하면 짝꿍을 찾을 수 있습니다.3. 중복 허용만약 같은 무게를 가진 사람이 여러 명 있으면,..
[프로그래머스] 마법의 엘리베이터 코드 힌트문제의 핵심: 최소한의 조작으로 층수를 0으로 만들기이 문제는 각 자리 숫자를 더하거나 빼서 전체 storey 값을 0으로 만드는 과정에서, 최소한의 조작 횟수를 구하는 문제입니다. 한 자리씩 차례대로 내려가면서, 그 자리 숫자가 5보다 크거나 작을 경우에 따라 올리거나 내립니다.각 자리 숫자 처리 방식올림(UP): 만약 현재 자리 숫자가 5보다 크다면, 그 숫자를 올리는 것이 더 유리합니다. 예를 들어, 8인 경우 2를 더해서 올림 처리합니다. 이때 상위 자리 숫자가 하나 증가합니다.내림(DOWN): 현재 자리 숫자가 5보다 작으면 내리는 것이 더 유리합니다. 예를 들어, 3인 경우 3만큼 내려서 0으로 만듭니다.5일 경우현재 자리 숫자가 정확히 5일 때는 다음 자리 숫자를 확인합니다. 만약 ..
[프로그래머스] [PCCP 기출문제] 2번 / 퍼즐 게임 챌린지 코드 힌트이진 탐색을 통한 레벨 탐색목표는 작업을 완료하는 데 필요한 시간(curTime)이 제한 시간(limit)을 넘지 않도록 레벨을 찾아내는 것입니다.이진 탐색은 레벨(level)을 조정해가며 가장 낮은 가능한 레벨을 찾습니다.left는 1에서 시작하고, right는 주어진 작업의 최대 난이도로 설정됩니다. mid는 left와 right의 중간값으로, 작업을 완료할 수 있는지 여부를 확인하기 위한 임시 레벨로 사용됩니다.계산 로직주어진 레벨 mid보다 난이도가 높은 작업들은 해당 레벨로 난이도를 줄여야 하므로 추가적인 시간을 소모하게 됩니다.이때, 이전 작업(times[i-1])과 현재 작업(times[i])의 소요 시간이 더해져야 합니다.모든 작업을 완료한 시간이 제한 시간을 초과하면, 현재 레벨..
[프로그래머스] 연속된 부분 수열의 합 힌트목표 합을 찾기:주어진 배열에서 연속된 부분 배열의 합이 k가 되는 구간을 찾아야 합니다.시작점과 끝점 두 개의 포인터를 사용하여 배열을 탐색하며, 포인터 사이의 값들의 합이 k와 같은지 확인합니다.이동 방식:초기에는 배열의 시작에서 끝까지 포인터를 이동하면서 합계를 계산합니다.만약 현재 합이 k보다 크다면 시작 포인터를 앞으로 이동시켜 구간을 줄입니다.합이 정확히 k가 되면 해당 구간을 기록하고, 더 짧은 구간이 있을 경우 그것으로 업데이트합니다.최적화 방법:각 구간에서의 합을 실시간으로 유지하며, 불필요한 연산을 줄이기 위해 더 짧은 구간이 발견될 때만 결과를 업데이트합니다.탐색이 끝날 때까지 가장 짧은 구간을 찾아냅니다. 정답은 더보기 클릭더보기class Solution { public i..
728x90

티스토리툴바