구현(Implementation Algorithm)

1. 구현 알고리즘이란?

코딩 테스트에서 구현이란 “머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정”이다.

구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이라고 할 수 있기 때문에 대부분 별도의 유형으로 분류하지 않는다.

하지만 구현이 중심이 되는 문제가 자주 출제되기에 다른 알고리즘보다 먼저 다루고자 한다.

 

2. 예제

💡 모든 문제는 나동빈 저자의 “이것이 코딩테스트다”에 수록되어 있으며 작성한 코드는 오류가 있을 수도 있음을 미리 밝힙니다.

 

2-1. 상하좌우

문제

여행가 A는 N X N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 X 1 크기의 정사각형으로 나누어져 있다. .가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.

계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다. 각 문자의 의미는 다음과 같다.

• L: 왼쪽으로 한 칸 이동
• R: 오른쪽으로 한 칸 이동
• U: 위로 한 칸 이동
• D: 아래로 한 칸 이동

이 때 여행가 A가 N X N 크기의 정사각형 공간을 벗어나는 움직임은 무시된다. 예를 들어 (1, 1)의 위치에서 L 혹은 U를 만나면 무시된다. 다음은 N = 5인 지도와 계획서이다.

이 경우 6개의 명령에 따라서 여행가가 움직이게 되는 위치는 순서대로 (1, 2), (1, 3), (1, 4), (1, 4), (2, 4), (3, 4)이므로, 최종적으로 여행가 A가 도착하게 되는 곳의 좌표는 (3, 4)이다. 다시 말해 3행 4열의 위치에 해당하므로 (3, 4)라고 적는다. 계획서가 주어졌을 때 여행가 A가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

 

입력

• 첫째 줄에 공간의 크기를 나타내는 N이 주어진다. (1 ≤ N ≤ 100)
• 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다 (1 ≤ 이동 횟수 ≤ 100)

출력

• 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력한다.

 

입력 예시

5
R R R U D D

출력 예시

3 4

 

풀이

바뀌는 위치가 배열의 크기를 벗어나지 않는다면 이동한다.

문제의 시작 위치는 (1, 1)인데 코드의 시작 위치는 (0, 0)으로 지정했기 때문에 마지막의 위치에 1씩 더해서 출력해준다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] maps = new int[N][N];

        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        String[] move = {"L", "R", "U", "D"};
        StringTokenizer st = new StringTokenizer(br.readLine());

        int currentX = 0;
        int currentY = 0;
        while(st.hasMoreTokens()) {
            String s = st.nextToken();
            for(int i=0; i<move.length; i++) {
                if(s.equals(move[i])) {
                    int nextX = currentX + dx[i];
                    int nextY = currentY + dy[i];
                    if(nextX<0||nextY<0||nextX>=N||nextY>=N) {
                        break;
                    }
                    currentX = nextX;
                    currentY = nextY;
                }

            }
        }
        System.out.println((currentX+1) + " " + (currentY+1));
    }
}

 

2-2. 시각

문제

정수 N이 입력되면 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.

• 00시 00분 03초
• 00시 13분 30초

반면에 다음은 3이 하나도 포함되어 있지 않으므로 세면 안 되는 시각이다.

• 00시 02분 55초
• 01시 27분 45초

 

입력

• 첫째 줄에 정수 N이 입력된다. (0 ≤ N ≤ 23)

출력

• 00시 00분 00초부터 N시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.

 

입력 예시

5

출력 예시

11475

 

풀이

1초씩 증가시키며 3이 들어가는지 확인한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int count = 0;
        for(int hour = 0; hour<=N; hour++) {
            for(int minute = 0; minute<60; minute++) {
                for(int second = 0; second<60; second++) {
                    StringBuilder sb = new StringBuilder();
                    sb.append(hour).append(minute).append(second);
                    if(sb.toString().contains("3")) count++;
                }
            }
        }
        System.out.println(count);
    }
}

 

2-3. 왕실의 나이트

문제

행복 왕국의 왕실 정원은 체스판과 같은 8 X 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다.

나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다. 나이트는 특정한 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.

1. 수평으로 두 칸 이동한 뒤에 수직으로 한 칸 이동하기
2. 수직으로 두 칸 이동한 뒤에 수평으로 한 칸 이동하기

이처럼 8 X 8 좌표 평면 상에서 나이트의 위치가 주어졌을 때 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 이 때 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.

예를 들어 만약 나이트가 a1에 있을 때 이동할 수 있는 경우의 수는 다음 2가지이다. a1의 위치는 좌표 평면에서 구석의 위치에 해당하며 나이트는 정원의 밖으로는 나갈 수 없기 때문이다.

1. 오른쪽으로 두 칸 이동 후 아래로 한 칸 이동하기(c2)
2. 아래로 두 칸 이동 후 오른쪽으로 한 칸 이동하기(b3)

또 다른 예로 나이트가 c2에 위치해 있다면 나이트가 이동할 수 있는 경우의 수는 6가지이다. 이건 직접 계산해보시오.

 

입력

• 첫째 줄에 8 X 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이뤄진다.

출력

• 첫째 줄에 나이트가 이동할 수 있는 경우의 수를 출력하시오.

 

입력 예시

a1

출력 예시

2

 

풀이

만약 ‘c5’라면 시작 좌표는 8 X 8 배열 상에서 (4, 2)가 된다.

말이 움직일 수 있는 최대의 경우는 8번이므로 8번을 다 움직여보고 가능하면 count한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String start = br.readLine();
        int x = start.charAt(1)-49;
        int y = start.charAt(0)-97;

        int count = 0;
        int[] dx = {-1, 1, -2, -2, -1, 1, 2, 2};
        int[] dy = {2, 2, -1, 1, -2, -2, -1, 1};

        for(int i=0; i<8; i++) {
            int nextX = x + dx[i];
            int nextY = y + dy[i];
            if(nextX<0||nextY<0||nextX>=8||nextY>=8) continue;
            count++;
        }

        System.out.println(count);

    }
}