✔ 당구 연습 [프로그래머스 169198] 문제 분석하기 원 쿠션이 될 수 있는 방향은 상하좌우 네 방향이며, 이 중 가장 짧은 이동 거리를 가져야 하므로 네 방향으로 대칭 이동 시켜 최소 직선 거리를 구하도록 함 이때 무조건 벽을 맞춰 원 쿠션 되어야 하므로 두 점이 평행한 경우, 벽보다 다른 공이 먼저 맞게 될 경우는 제외하도록 함 손으로 풀어보기 원 쿠션이 될 수 있는 방향은 상하좌우 네 방향으로 대칭 이동 시킨 후 직선 거리를 구하도록 함 이때 무조건 벽을 맞춰 원 쿠션 되어야 하므로 벽보다 다른 공이 먼저 맞게 될 경우는 제외 직선 거리 중 가장 최소 직선 거리를 반환 슈도코드 작성하기 m, n(당구대의 가로, 세로 길이) startX, startY(머쓱이가 쳐야 하는 공이 놓인 위치 좌표) b..
✔ 혼자서 하는 틱택토 [프로그래머스 160585] 문제 분석하기 O가 선공이므로 X의 개수가 O의 개수보다 많을 경우, 번갈아가며 진행해야 하므로 O가 X의 개수보다 1개 많을 경우, O가 완성되었을 때 X의 개수가 O의 개수와 같을 경우, X가 완성되었을 때 O의 개수가 X의 개수보다 1개 많을 경우 규칙 위반이므로 이를 검사하도록 함 손으로 풀어보기 O가 선공이므로 X의 개수가 O의 개수보다 많은지 확인 번갈아가며 진행해야 하므로 O가 X의 개수보다 1개 많은지 확인 O가 완성되었을 때 X의 개수가 O의 개수와 같은지 확인 X가 완성되었을 때 O의 개수가 X의 개수보다 1개 많은지 확인 넷 중 하나라도 위반하지 않을 경우에는 1, 위반했다면 0을 반환 슈도코드 작성하기 board(틱택토 게임판의 정..
✔ 미로 탈출 [프로그래머스 159993] 문제 분석하기 BFS로 상하좌우로 이동하며 E에 도착할 때까지 이동하도록 함. 이때 L을 지나갔으면서 E에 도착하는 가장 최소 시간을 반환하도록 함 손으로 풀어보기 상하좌우를 BFS를 하며 탐색하며 L에 도착할 때의 최소 시간과 E에 도착할 때까지의 최소 시간을 찾아 합을 구하도록 함 이때 만약 둘 중 하나라도 찾지 못할 경우 -1을 반환하도록 함 슈도코드 작성하기 maps(미로를 나타낸 문자열 배열) answer(미로를 탈출하는데 필요한 최소 시간) start(미로 시작 좌표) lever(레버 좌표) for(i -> maps의 길이만큼) { for(j -> maps[0]의 길이만큼) { if(maps[i].charAt[j]가 'S'라면) start에 좌표 저장..
✔ 호텔 대실 [프로그래머스 155651] 문제 분석하기 대실 시작 시간을 기준으로 정렬한 후 이후 우선순위 큐를 사용해 청소 시간을 포함해 가장 빨리 비는 객실을 할당해주고, 그렇지 못하다면 객실의 개수를 추가 예) (15:00-17:00), (16:40-18:20), (14:20-15:20), (14:10-19:20), (18:20-21:20) 정렬 후 예약 시간 = (14:10-19:20), (14:20-15:20), (15:00-17:00), (16:40-18:20), (18:20-21:20) 손으로 풀어보기 대실 시작 시간을 기준으로 예약 시간을 정렬 우선순위 큐를 사용해 청소 시간을 포함해 가장 빨리 비는 객실을 할당해주고, 그렇지 못하다면 객실의 개수를 추가 최종 우선순위 큐의 개수를 객실의..
✔ 무인도 여행 [프로그래머스 154540] 문제 분석하기 상하좌우를 BFS를 하며 탐색하여 최대 머물 수 있는 일수를 증가시키도록 함 손으로 풀어보기 상하좌우를 BFS를 하며 탐색하여 최대 머물 수 있는 일수를 증가 만약 머물 수 있는 섬이 없다면 -1을 담아 반환 슈도코드 작성하기 maps(지도를 나타내는 문자열 배열) answer(각 섬에서 최대 며칠씩 머무를 수 있는지 리스트) visited(방문 유무 배열) for(i -> maps의 길이만큼) { for(j -> maps[0]의 길이만큼) { if(visited[i][j]에 방문하지 않으면서 바다가 아니라면) answer에 bfs(maps, i, j) 저장 } } if(answer의 크기가 0이라면) answer에 -1 저장 answer 오름차..
✔ 뒤에 있는 큰 수 찾기 [프로그래머스 154539] 문제 분석하기 스택을 이용해 인덱스를 집어 넣으며 자신 보다 큰 값이 들어올 경우 이를 저장하며 빼도록 함 만약 끝까지 자신보다 큰 값이 없을 경우 -1을 반환하도록 함 예) [9, 1, 5, 3, 6, 2] i stack numbers[stack.peek()] < numbers[i] answer 1 0 9 < 1 (X) [0, 0, 0, 0, 0, 0] 2 1 0 1 < 5 (O) 9 < 5 (X) [0, 5, 0, 0, 0, 0] 3 2 0 5 < 3 (X) 9 < 3 (X) [0, 5, 0, 0, 0, 0] 4 3 2 0 3 < 6 (O) 5 < 6 (O) 9 < 6 (X) [0, 5, 6, 6, 0, 0] 5 4 0 6 < 2 (X) 9 < ..
✔ 숫자 변환하기 [프로그래머스 154538] 문제 분석하기 3가지 경우에 대해 다이나믹 프로그래밍을 구현 손으로 풀어보기 점화식의 형태와 의미를 도출 D[i]는 x를 i로 변환하기 위한 최소 연산 횟수 점화식을 구함 D[x] = 0 D[i + n] = Math.min(D[i + n], D[i] + 1) D[i * 2] = Math.min(D[i * 2], D[i] + 1) D[i * 3] = Math.min(D[i * 3], D[i] + 1) 이때 D[i]가 y + 1이라면 변환할 수 없는 값이므로 D[i] = -1 점화식으로 D 배열을 채운 후 D[y]의 값을 출력 슈도코드 작성하기 x, y, n(자연수) D[y + 1](x를 i로 변환하기 위한 최소 연산 횟수) D 배열을 y + 1로 모두 갱신 D..
✔ 시소 짝꿍 [프로그래머스 152996] 문제 분석하기 각각의 짝에 대해 평행 상태가 될 수 있는 경우의 수를 모두 구하도록 함 손으로 풀어보기 몸무게 목록을 오름차순 정렬 각각의 짝에 대해 평행 상태가 될 수 있다면 시소 짝꿍의 쌍을 증가 시소 짝꿍1과 시소 짝꿍2의 무게가 동일할 때 시소 짝꿍1 * 2와 시소 짝꿍2의 무게가 동일할 때 시소 짝꿍1 * 3과 시소 짝꿍2 * 2의 무게가 동일할 때 시소 짝꿍1 * 4와 시소 짝꿍2 * 3의 무게가 동일할 때 시소 짝꿍의 쌍 반환 슈도코드 작성하기 weights(사람들의 몸무게 목록) answer(시소 짝꿍 쌍의 개수) weights 오름차순 정렬 map(몸무게와 갯수를 담을 HashMap) for(w -> weights만큼) { couple1(w의 짝..
