프로그래머스(추석 트래픽, 2xn 타일링) - Java

[추석 트래픽]

https://programmers.co.kr/learn/courses/30/lessons/17676

코딩테스트 연습 - [1차] 추석 트래픽

 

* 조건

1. 응답 완료 시간(S)과 처리시간(T)가 입력으로 주어진다
2. 타임아웃 = 3s
3. 응답 완료 시간을 기준으로 오름차순 정렬되어있다
4. 처리 시간은 시작시간과 끝 시간을 포함
5. 동시에 끝나는 작업은 없다
6. 초당 최대 처리량을 구해야한다

* 알고리즘

- 1초 구간을 만들고 해당 구간에 들어가는지 탐색: for문으로 단순 비교

 

* 로직(Logic)

• 시간, 분, 초로 나눠져있는 단위를 하나의 단위로 통합 (초 단위)
• 초로 변환한 값과 처리시간(T) 세트를 list 배열에 담는다
• 작업이 완료된 구간에서 1초를 더해준 구간(section) 안에 다른 작업들의 처리 시작 구간이 들어간다면 count++
  • section = s + 1초
  • section - (완료시간 - 처리시간 + 0.001) > 0 이면 count++
• 완료된 구간에서 1초를 더해줬다는 말은 결국 해당 작업은 카운팅하고 이전의 작업은 고려할 필요가 없다는 말이다
• 최댓값을 출력한다

 

import java.util.ArrayList;
import java.util.StringTokenizer;

public class Problem_ThanksGivingTraffic {

    public static void main(String[] args) {
        //응답 완료시간(S: 년, 월, 일, 시간) + 처리시간(T: 초)
        //T의 타임아웃: 3초(0.001 <= <= 3.000)
        String[] lines = {"2016-09-15 01:00:04.001 2.0s", "2016-09-15 01:00:07.000 2s"};
        int result = solution(lines);

        System.out.println(result);
    }

    public static int solution(String[] lines){
        int answer = 0;
        StringTokenizer st;

        int logNum = lines.length;  //로그 개수
        String[] filterInput = new String[logNum];
        ArrayList<Double>[] convertData = new ArrayList[logNum]; //초로 변환한 값을 관리

        for(int i=0; i<logNum; ++i){
            st = new StringTokenizer(lines[i], " ");
            st.nextToken(); //날짜는 필요 x

            //시간 + 처리시간 담기
            filterInput[i] = st.nextToken().replace(":", "");
            String str = " " + st.nextToken().replace("s", "");
            filterInput[i] += str;
        }

        //초 + 처리시간을 담음
        for(int i=0; i<logNum; ++i){
            convertData[i] = new ArrayList<>();

            st = new StringTokenizer(filterInput[i], " ");
            String finishTime = st.nextToken();
            String doTime = st.nextToken();

            double convertTime = Integer.parseInt(finishTime.substring(0,2)) * 3600 +
                    Integer.parseInt(finishTime.substring(2,4)) * 60 +
                    Double.parseDouble(finishTime.substring(4));

            double convertDotime = Double.parseDouble(doTime);
            convertData[i].add(convertTime);
            convertData[i].add(convertDotime);
        }

        //측정 구간을 만들고 개수 카운팅
        for(int i=0; i<convertData.length; ++i){
            double s = convertData[i].get(0);
            double t;
            //구간 생성
            double section = s + 1;

            int cnt = 1;
            for(int j=i+1; j<convertData.length; ++j){
                s = convertData[j].get(0);
                t = convertData[j].get(1);

                //시작점 구하기
                double startTime = s - t + 0.001;
                if(section - startTime > 0) cnt++;
            }
            answer = Math.max(answer, cnt);
        }
        return answer;
    }
}

 

 

[2 x n 타일링]

https://programmers.co.kr/learn/courses/30/lessons/12900

코딩테스트 연습 - 2 x n 타일링

 

* 조건

1. 직사각형은 가로(1*2), 세로 방향(2*1)으로 만들 수 있다
2. 가로의 길이 n이 주어진다
3. 만들 수 있는 직사각형의 개수를 출력한다

* 알고리즘

- 처음엔 재귀를 돌려서 만들 수 있는 모든 경우의 수를 구했다: 브루트포스 (하지만 시간초과..)

- n 값에 따라 만들어지는 경우의 수를 구하다보니 규칙이 나왔다: 동적계획법

 

* 로직(Logic)

• n=1 -> 1개
• n=2 -> 2개 (1 + 1)
• n=3 -> 3개 (1 + 2)
• n=4 -> 5개 (2 + 3)
  
  
• 이러한 규칙성을 기반으로 dp[i] = dp[i-2] + dp[i-1]의 식을 세울 수 있다

 

<처음 재귀로 풀었을 때 코드 - 시간초과>

public class Problem_2nTiling {

    static boolean[][] checked;
    static int[][] tiles;
    static int size;
    static int makeCnt;

    //아래, 오른쪽
    static int[] dy = {1, 0};
    static int[] dx = {0, 1};
    static int ans = 0;

    public static void main(String[] args) {
        int n = 5;
        int answer = solution(n);
        System.out.println(answer);
    }

    //재귀 방식
    public static int solution(int n){
        int answer = 0;
        makeCnt = (n * 2) / 2;
        size = n;
        tiles = new int[2][size];
        checked = new boolean[2][size];

        int i=0, j=0;
        int count = 0;
        doProcess(i, j, count);
        answer = ans;

        return answer;
    }

    private static void doProcess(int y, int x, int count) {
        if(x >= size) {
            if(count == makeCnt){
                ans++;
                return;
            }
            doProcess(1, 0, count);
            return;
        }
        if(checked[y][x]) {
            doProcess(y, x+1, count);
            return;
        }

        for(int i=0; i<2; ++i){
            checked[y][x] = true;
            int moveY = y + dy[i];
            int moveX = x + dx[i];

            if(isRanged(moveY, moveX) && !checked[moveY][moveX]){
                checked[moveY][moveX] = true;
                doProcess(y, x+1, count + 1);
                checked[moveY][moveX] = false;
            }
            checked[y][x] = false;
        }
    }

    private static boolean isRanged(int y, int x) {
        if(y >=0 && y<2 && x>=0 && x<size) return true;
        return false;
    }
}

 

<DP를 적용한 코드>

public class Problem_2nTiling {
    public static void main(String[] args) {
        int n = 5;
        int answer = solution(n);
        System.out.println(answer);
    }

    public static int solution(int n){
        int answer = 0;
        int s = 1000000007;
        int[] dp = new int[n+1];

        dp[0] = 1;
        dp[1] = 1;
        for(int i=2; i<=n; ++i){
            dp[i] = (dp[i-2] + dp[i-1]) % s;
        }
        answer = dp[n];

        return answer;
    }
}

 

위 문제들을 풀면서 크게 3가지를 느꼈다. 첫 번째로는 단위가 여러개라면 하나로 통합시키는 아이디어다. 발생하는 예외 가능성을 훨씬 낮출 수 있다. 두 번째로는 처음과 끝과 같은 경계값들을 알 수 있다면, 이를 활용해 문제를 푸는 아이디어를 먼저 생각해보는 것이다. [추석 트래픽]의 경우도 만약 일일이 매초 구간을 비교한다면 분명히 시간초과가 발생할 것이다. 항상 경계값들을 비교해보는 습관을 길러야겠다.

마지막으로, 경우의 수를 구할 때 무작정 재귀부터 접근하지 말고 DP의 가능성을 염두해야한다는 것이다. 타일 문제처럼 내가 몇 가지 경우에 대해 답을 구할 수 있다면 답이 구해지는 규칙을 찾으려는 시도가 필요하다는 것을 느꼈다.

 

브루트포스를 구할 때는 재귀, DP와 같은 방식을 모두 염두해가며 로직을 짜야되는 중요성을 경험했다. 습관부터 들이자