✔ 합승 택시 요금 [프로그래머스 72413] 문제 분석하기 시작 노드와 연결된 노드까지의 최단 거리와 A, B 노드와 연결된 노드끼리의 최단 거리를 찾은 후 i를 기준으로 합승을 멈추고 각각 택시를 이용해서 갈 때 가장 적은 값을 찾도록 함 이때 시작지점부터 모든 노드까지의 거리의 합이 필요하므로 다익스트라를 이용 또는 플로이셜 워셜을 통해 가는 최단 거리 구하기 손으로 풀어보기 시작 노드에서부터 모든 노드까지의 최단 거리 구하기 A 노드에서부터 모든 노드까지의 최단 거리 구하기 B 노드에서부터 모든 노드까지의 최단 거리 구하기 i를 기준으로 A, B, C를 합쳐서 합승을 멈추고 각각 택시를 이용했을 때 가장 짧은 최단 거리 구하기 슈도코드 작성하기 n(지점의 개수) s, a, b(출발지점, A의 도착..
✔ 스타 수열 [프로그래머스 70130] 문제 분석하기 교집합의 원소의 개수가 1개 이상이어야 하므로 전체 수열에서 각 인덱스에 따른 숫자의 개수를 저장한 후 각 숫자를 교집합으로 하는 스타 수열의 길이를 찾도록 함 손으로 풀어보기 전체 수열에서 각 인덱스에 따른 숫자의 개수를 저장 각 숫자를 교집합으로 하는 스타 수열의 길이를 찾도록 함 슈도코드 작성하기 a(1차원 정수 배열) count(각 원소의 개수를 담은 배열) for(num -> a만큼) { a 배열을 돌면서 각 원소에 따른 개수를 증가시킴 } answer(a의 모든 부분 수열 중에서 가장 길이가 긴 스타 수열의 집합 개수) for(i -> count의 길이만큼) { if(count[i]의 개수가 answer보다 작다면) { 더 긴 스타 수열이..
✔ 풍선 터트리기 [프로그래머스 68646] 문제 분석하기 규칙을 찾아서 이를 적용 풍선이 총 1개인 경우 [1] 1번 풍선이 남음 풍선이 총 1개일 경우 모든 풍선이 살아남을 수 있으므로 1을 반환 풍선이 총 2개인 경우 [1, 2] 2번 제거 → 최종 1번 남음 1번 제거 → 최종 2번 남음 풍선이 총 2개일 경우 모든 풍선이 살아남을 수 있으므로 2를 반환 풍선이 총 3개인 경우 양쪽 풍선이 가운데 풍선보다 크고, 작은 것이 각각 있을 때 [1, 2, 3] 1번 제거 → 3번 제거 → 최종 2번 남음 2번 제거 → 1번 제거 → 최종 3번 남음 2번 제거 → 3번 제거 → 최종 1번 남음 오름차순의 경우 모든 풍선이 살아남을 수 있으므로 3을 반환 양쪽 풍선이 가운데 풍선보다 크고, 작은 것이 각..
✔ 경주로 건설 [프로그래머스 67259] 문제 분석하기 BFS를 통해 상하좌우로 탐색을 하면서 이전과 같은 방향일 경우 비용을 100원, 그 외일 경우 비용을 600원으로 하여 계산하도록 함 이때 DP를 사용해 방문하지 않았거나 지나가는 길의 최소 비용을 갱신할 수 있다면 탐색하도록 함 손으로 풀어보기 BFS를 통해 상하좌우로 탐색을 하면서 이전과 같은 방향일 경우 비용을 100원, 그 외일 경우 비용을 600원으로 하여 계산 이때 DP를 사용해 방문하지 않았거나 지나가는 길의 최소 비용을 갱신할 수 있다면 탐색 슈도코드 작성하기 board(2차원 정사각 배열) N(board의 길이) visited(방문 유무 배열) bfs 반환 bfs { dx, dy(상하좌우 좌표) min(경주로를 건설하는데 필요한 ..
✔ 보석 쇼핑 [프로그래머스 67258] 문제 분석하기 보석의 종류 개수를 찾은 후, 투 포인터를 사용한 슬라이딩 윈도우로 가장 짧은 구간을 구하도록 함 손으로 풀어보기 보석의 종류 개수를 찾기 투 포인터를 사용한 슬라이딩 윈도우로 가장 짧은 구간을 구하기 슈도코드 작성하기 gems(진열대 번호 순서대로 보석들의 이름이 저장된 배열) answer(모든 보석을 하나 이상 포함하는 가장 짧은 구간) kind(진열된 모든 종류의 보석 개수) = gems를 집합에 담아 중복을 제거했을 때의 크기 map(보석에 따른 개수를 저장하는 HashMap) start(시작 인덱스) end(끝 인덱스) length(구간의 길이) while (end < gems.length) { map에 end의 보석 이름과 보석의 개수 저..
✔ 불량 사용자 [프로그래머스 64064] 문제 분석하기 정규 표현식을 사용해 해당 아이디가 불량 사용자가 동일한지 아닌지 확인하며 모든 경우의 수를 찾도록 함 손으로 풀어보기 정규 표현식을 사용하기 위해 불량 아이디의 *를 .로 변경 모든 아이디를 살펴가며 불량 사용자의 아이디에 대한 경우의 수 생성 경우의 수를 오름차순으로 정렬하고 집합을 이용해 중복 제거 집합의 개수를 반환 슈도코드 작성하기 user_id(이벤트 응모자 아이디 목록이 담긴 배열) banned_id(불량 사용자 아이디 목록이 담긴 배열) answer(당첨에서 제외되어야 할 제재 아이디 목록의 경우의 수) for(i -> banned_id만큼) { banned_id[i]에서 *를 .로 변경 } set(제재 아이디에 대한 경우의 수를 담..
✔ 징검다리 건너기 [프로그래머스 64062] 문제 분석하기 이진 탐색을 통해 건널 수 있는 프렌즈의 최대값을 구하도록 함 손으로 풀어보기 이진 탐색을 이용해 건널 수 있는 프렌즈의 최대값을 찾기 프렌즈의 값에 따라 건너 뛰어서도 갈 수 없다면 갈 수 없는 것 슈도코드 작성하기 stones(디딤돌에 적힌 숫자가 순서대로 담긴 배열) k(한 번에 건너뛸 수 있는 디딤돌의 최대 칸수) answer(징검다리를 건널 수 있는 최대 니니즈 친구들의 수) min(징검다리를 건널 수 있는 최소 니니즈 친구들의 수) = 0 max(징검다리를 건널 수 있는 최대 니니즈 친구들의 수) = Integer.MAX_VALUE while (min이 max보다 같거나 작을 동안) { mid(징검다리를 건널 수 있는 니니즈 친구들 ..
✔ 블록 이동하기 [프로그래머스 60063] 문제 분석하기 BFS를 이용해 상하좌우로 이동하며 도착점까지 가는지 살펴보면서 네 방향 뿐만이 아니라 회전한 후 이동도 가능한지 확인하도록 함 손으로 풀어보기 상하좌우를 BFS로 탐색하며 도착점까지 가는 최소 시간을 구하도록 함 이때 네 방향 뿐만 아니라 회전한 후 이동도 가능한지 확인하도록 함 슈도코드 작성하기 board(0과 1로 이루어진 지도) answer(로봇이 도착점까지 이동하는데 필요한 최소 시간) = bfs bfs { dx, dy(상하좌우 좌표) visited(방문 유무 배열) 큐 자료구조에 현재 노드 좌표 및 이동 시간 기록 while(큐가 빌 때까지) { 큐에서 노드 데이터 가져오기 if(도착점에 도착했다면) 이동 시간 반환 for(i -> 4..
