[알고리즘] 04. 구현 (Implementation)

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

흔히 문제 해결 분야에서 구현 유형의 문제는 '풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제'를 의미한다.
그렇다면 어떤 문제가 구현하기 어려운 문제일까?
- 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제
- 특정 소수점 자리까지 출력해야 하는 문제,
- 문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣어야 하는 문제 등

또한 프로그래밍 문법을 정확하게 숙지하지 못했거나, 라이브러리 사용 경험이 부족하면 구현 유형의 문제를 풀 때 불리하다.

---

📚  예제4-1 ) 상하좌우

여행가 A는 N * N 크기의 정사각형 공간 위에 서있다. 이공간은 1 * 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가 최종적으로 도착할 지점의 좌표를 출력하는 프로그램을 작성하시오.

📝 문제 해결

• 유형 : 시뮬레이션
• 시간 복잡도 : O(N) 연산 횟수 = 이동 횟수

 

💻 코드

package implementation;

import java.util.Scanner;

public class impl_0514_4_1 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        sc.nextLine(); // 버퍼 비우기
        String[] plans = sc.nextLine().split(" ");
        int x = 1, y = 1;

        int[] dx = {0, 0, -1, 1};
        int[] dy = {-1, 1, 0, 0};
        char[] move_type = {'L', 'R', 'U', 'D'};

        for (int i = 0; i < plans.length; i++) {
            char plan = plans[i].charAt(0);
            int nx = -1, ny = -1;
            for(int j = 0; j < move_type.length; j++){
                if (plan == move_type[j]){
                    nx = x + dx[j];
                    ny = y + dy[j];
                }

                if(nx < 1 || ny < 1 || nx > n || ny > n) continue;
                x = nx;
                y = ny;
            }
        }

        System.out.println(x + " " + y);
    }
}

 

 

📚  예제4-2 ) 시각

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

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

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

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

📝 문제 해결

• 유형 : 완전 탐색

💡 완전 탐색 : 가능한 경우의 수를 모두 검사해보는 탐색 방법
(일반적으로 비효율적인 시간복잡도를 가지고 있으므로 전체 데이터의 개수가 100만 개 이하일 때 적절)

 

💻 코드

package implementation;

import java.util.Scanner;

public class impl_0514_4_2 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int count = 0;

        for(int i = 0; i <= n; i++){
            for(int j = 0; j < 60; j++){
                for(int k = 0; k < 60; k++){
                    if (i/10 == 3 || i%10 == 3 || j/10 == 3 || j%10 == 3 || k/10 == 3 || k%10 == 3) {
                        count += 1;
                    }
                }
            }
        }

        System.out.println(count);
    }
}

 

+ 구글링으로 발견한 다른 사람의 코드
시, 분, 초를 문자열 자료형으로 변환하여 합친 다음 3이 포함되어 있는지 확인

String time = String.valueOf(i) + j + k;
if(time.contains("3")) answer++;

 

[출처] 나동빈, 『이것이 취업을 위한 코딩테스트다 with 파이썬』, 한빛미디어(주), 2020년