최근 취업 시장에서 알고리즘 문제는 중요한 요소 중 하나로 자리잡고 있습니다. 특히 소프트웨어 엔지니어링 직무를 위해서는 알고리즘과 자료구조에 대한 이해가 필수적입니다. 이번 강좌에서는 “DDR(Dance Dance Revolution)”이라는 주제로 알고리즘 문제를 다루어 보겠습니다. DDR은 춤을 추는 게임으로, 주어진 시간 안에 제시된 발판을 정확히 밟아야 합니다. 이를 프로그래밍 문제로 변환하여 알고리즘을 공부해 보겠습니다.
문제 설명
당신은 DDR의 챌린지에 참가했습니다. 화면에 나타나는 발판의 순서가 주어지면, 이를 정확히 따라 밟아야 합니다. 발판은 1부터 9까지의 정수로 표시되며, 1은 왼쪽 하단, 2는 가운데 하단, 3은 오른쪽 하단, 4는 왼쪽 중간, 5는 가운데, 6은 오른쪽 중간, 7은 왼쪽 상단, 8은 가운데 상단, 9는 오른쪽 상단을 의미합니다.
당신은 현재 상태에서 어디에 발을 놓고 있느냐에 따라 발판을 밟는 시간과 거리가 달라질 수 있습니다. 그러므로 최적의 경로를 찾아야 합니다.
입력 형식
첫 번째 줄에는 발판의 개수 N (1 ≤ N ≤ 1000)이 주어집니다. 두 번째 줄에는 N개의 발판이 주어지며, 각 발판은 1부터 9까지의 정수를 가집니다.
출력 형식
모든 발판을 밟기 위해 필요한 최소 시간을 출력합니다.
문제 예시
입력:
5
1 3 5 7 9
출력:
8
문제 풀이 과정
1단계: 발판의 좌표 정의
먼저 발판의 위치를 정의해야 합니다. 다음과 같이 2D 배열을 사용하여 발판 간의 거리를 계산할 수 있습니다.
// 발판 위치를 (행, 열)로 정의
int[][] position = {
{3, 1}, // 1
{2, 1}, // 2
{1, 1}, // 3
{3, 2}, // 4
{2, 2}, // 5
{1, 2}, // 6
{3, 3}, // 7
{2, 3}, // 8
{1, 3} // 9
};
2단계: 거리 계산 함수 구현
거리 계산에는 맨해튼 거리를 사용할 것입니다. 맨해튼 거리란 두 점 (x1, y1)과 (x2, y2) 간의 거리는 |x1 – x2| + |y1 – y2|로 정의됩니다. 이를 Java 함수로 구현해보겠습니다.
public int calculateDistance(int a, int b) {
int x1 = position[a - 1][0];
int y1 = position[a - 1][1];
int x2 = position[b - 1][0];
int y2 = position[b - 1][1];
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
3단계: 메인 로직 구현
이제 발판을 한 번씩 밟기 위한 최적의 경로를 계산하는 메인 로직을 구현합니다. 현재 위치와 밟아야 할 발판 위치 간의 거리를 계산하고, 최소 거리를 누적합니다.
public int minTime(int[] steps) {
int totalTime = 0;
int currentPosition = 5; // 처음 발판은 5의 위치(중앙)
for (int step : steps) {
totalTime += calculateDistance(currentPosition, step);
currentPosition = step; // 현재 위치 업데이트
}
return totalTime;
}
4단계: 전체 코드
최종적으로 발판 정보를 입력받아 최소 시간을 계산하는 전체 코드를 작성하겠습니다.
import java.util.Scanner;
public class Main {
static int[][] position = {
{3, 1}, // 1
{2, 1}, // 2
{1, 1}, // 3
{3, 2}, // 4
{2, 2}, // 5
{1, 2}, // 6
{3, 3}, // 7
{2, 3}, // 8
{1, 3} // 9
};
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] steps = new int[N];
for (int i = 0; i < N; i++) {
steps[i] = scanner.nextInt();
}
System.out.println(minTime(steps));
}
public static int minTime(int[] steps) {
int totalTime = 0;
int currentPosition = 5; // 처음 발판은 5의 위치(중앙)
for (int step : steps) {
totalTime += calculateDistance(currentPosition, step);
currentPosition = step; // 현재 위치 업데이트
}
return totalTime;
}
public static int calculateDistance(int a, int b) {
int x1 = position[a - 1][0];
int y1 = position[a - 1][1];
int x2 = position[b - 1][0];
int y2 = position[b - 1][1];
return Math.abs(x1 - x2) + Math.abs(y1 - y2);
}
}
결론
이번 강좌에서는 간단한 알고리즘 문제를 통해 발판의 위치와 거리 계산을 학습했습니다. 이 문제는 실제 코딩 테스트에서 자주 등장할 수 있는 유형의 문제입니다. 다양한 알고리즘 문제를 풀어보면 자연스럽게 자료구조와 알고리즘에 대한 이해도를 높일 수 있습니다. 계속해서 많은 문제를 풀며 경험치를 쌓아 가길 바랍니다!