프로그래머스

[프로그래머스, Java] 합승 택시 요금

🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/72413 😮 문제 해결 방법 최단 거리 알고리즘을 적용하는 것이 문제의 키포인트이다. 모든 도시로부터 출발해 모든 도시로 도착하는 최단 거리를 구해준다. 최단 거리를 구하는 방식은 크게 두가지가 있다. (무방향 양수 그래프 기준) 하나의 정점 기준 최단 거리구하기 → 다익스트라 알고리즘 : 모든 도시에 대해 구해야하므로 for문을 통해 모든 최단 거리를 구한다. 모든 정점 기준 최단 거리 구하기 → 플로이드 워셜 알고리즘 모든 정점에 대한 최단거리를 구하는 알고리즘은 플로이드 워셜을 일반적으로 사용하기 때문에 플로이드 워셜 알고리즘을 통해 문제를 해결한다. (다익스트라 이용시 시간초과 ..

[프로그래머스, Java] 땅따먹기

🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12913 😮 문제 해결 방법 간단한 DP문제이다. 현재 스텝의 열에서 최대의 점수를 얻기 위해선 이전 스텝까지의 열 중에서 현재 내가 밟고 있지 않은 열의 최대 점수값을 더해준다. 만약 2번째 스텝의 1번째 열의 최대값을 구하고 싶다면, 1번째 스텝까지의 2,3,4열의 최대값에 현재 밟은 칸의 점수를 더해주면 최댓값이 된다. 이러한 방식을 통해 점화식을 세우면 dp[step][열] = arr[step][열] + max(dp[step-1][열에 해당하지 않는 열])이 된다. dp[step-1][열에 해당하지 않는 열]의 경우 열이 4개가 있기 때문에 max안에 들어가는 dp의 개수는 3개..

[프로그래머스, Java] 방문 길이

🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/49994 😮 문제 해결 방법 좌표를 하나의 행렬로 이용하기 위해서 10 * 10지도를 11 * 11 좌표로 변환해서 사용했다. 첫 시작 위치는 (5,5)에서 시작하고 상, 하, 좌, 우로 이동하는 경우에 해당 경로를 이용했음을 체크해주는 배열을 생성한다. 배열은 3차원 배열을 사용해 좌표의 행렬과 방향을 표시한다. 3차원 배열을 이용함으로 써 이미 방문한 좌표의 경우에도 방향이 다르면 새로운 경로임을 판단할 수 있다. 이 부분에서 키 포인트는 만약 A → B로 이동하는 경우가 새로운 경로라면, B → A로 이동하는 경로 또한 동일한 경로이기 때문에 체크를 해주어야 하는 것이다. 주어진 ..

[프로그래머스, Java] 주차 요금 계산

🔗 문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/92341 😮 문제 해결 방법 Map을 이용해서 자동차 번호별 자동차의 정보를 저장한다. 자동차는 차량번호, 주차시간 (주차장 이용시간), 입차 시간, 입/출차 상태를 갖도록 클래스를 만들었다. 먼저 record배열을 하나씩 보면서 자동차의 정보를 Map으로 관리한다. 자동차가 처음으로 입차하는 경우는 containsKey를 이용해 판단하고, 주차시간을 0으로 하고, 입/출차 상태를 false로 넣어준다. 자동차가 출차되는 경우는 출차 시간에서 입차 시간을 빼서 주차시간을 갱신한다. 자동차가 다시 입차되는 경우는 입차 시간을 갱신한다. 모든 이력을 이용해 저장했다면, Map정보를 이용해 ..

[프로그래머스, Java] 빛의 경로 사이클

🔗 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/86052 🤔 문제 각 칸마다 S, L, 또는 R가 써져 있는 격자가 있습니다. 당신은 이 격자에서 빛을 쏘고자 합니다. 이 격자의 각 칸에는 다음과 같은 특이한 성질이 있습니다. 빛이 "S"가 써진 칸에 도달한 경우, 직진합니다. 빛이 "L"이 써진 칸에 도달한 경우, 좌회전을 합니다. 빛이 "R"이 써진 칸에 도달한 경우, 우회전을 합니다. 빛이 격자의 끝을 넘어갈 경우, 반대쪽 끝으로 다시 돌아옵니다. 예를 들어, 빛이 1행에서 행이 줄어드는 방향으로 이동할 경우, 같은 열의 반대쪽 끝 행으로 다시 돌아옵니다. 당신은 이 격자 내에서 빛이 이동할 수 있는 경로 사이클이 몇 개 있고, 각 사이클의..