Algorithm/Algorithm Test

[프로그래머스] 등굣길 (C++, Java, Python)

MarrRang 2020. 9. 15. 00:10

카테고리

동적계획법(Dynamic Programming)

나만의 카테고리

이차배열, 최단거리

문제 링크

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

요점

  • 재귀법, DP의 방법이 생각나지만 효율성 테스트를 통과하기 위해서는 DP를 택해야한다.
  • 1,000,000,007 정도로 나누는 문제는 long을 염두해야한다.

참고 지식

풀이 (C++)

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<vector<int>> puddles) {
    long root[101][101];
    long puddleMap[101][101]; // long을 이용해야 효율성 테스트를 실패하지 않는다.

    for (int i = 0; i < puddles.size(); i++) {
        if (puddles[i].size() == 0) break; // Test Case에서 [[]] 를 실패하지 않도록 추가

        puddleMap[puddles[i][0]][puddles[i][1]] = -1;
    }

    root[0][1] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (puddleMap[i][j] == -1) {
                root[i][j] = 0;
            } else {
                // 이 부분에서 나눠주면 효율이 떨어지지만 안하면 long long을 사용해도 실패
                root[i][j] = (root[i][j-1] + root[i-1][j]) % 1000000007;
            }
        }
    }

    return root[m][n];
}

풀이 (Java)

class Solution {
    public long solution(int m, int n, int[][] puddles) {
        long[][] root = new long[101][101];
        long[][] puddleMap = new long[101][101];

        for (int[] puddle : puddles) {
            if (puddle.length == 0) break;

            puddleMap[puddle[0]][puddle[1]] = -1;
        }

        root[0][1] = 1;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (puddleMap[i][j] == -1) {
                    root[i][j] = 0;
                } else {
                    root[i][j] = (root[i][j-1] + root[i-1][j]) % 1000000007;
                }
            }
        }

        return root[m][n];
    }
}

 풀이 1 (Python)

def solution(m, n, puddles):
    root = [[0 for i in range(101)] for j in range(101)]
    puddleMap = [[0 for i in range(101)] for j in range(101)]
    
    for puddle in puddles :
        if len(puddle) == 0 :
            break
        
        puddleMap[puddle[0]][puddle[1]] = -1
        
    root[0][1] = 1
    
    for i in range(1, m+1) :
        for j in range(1, n+1) :
            if puddleMap[i][j] == -1 :
                root[i][j] = 0
            else :
                root[i][j] = root[i][j-1] + root[i-1][j]
    
    
    return root[m][n] % 1000000007

자바 코드와 같이 % 연산을 for문 안에서 해주면 효율성 테스트를 통과하지 못합니다.

파이썬은 값의 형을 알아서 잘 결정해주니 % 연산을 줄여주는것이 효율성 테스트를 통과하는 방법이였습니다

 

풀이 2 (Python)

# https://www.hamadevelop.me/algorithm-wayhome/ 참고

def solution(m, n, puddles):
    puddleMap = [[0 for i in range(m+1)] for j in range(n+1)]
    
    puddleMap[1][1] = 1
    
    for i in range(1, n+1) :
        for j in range(1, m+1) :
            if [j, i] in puddles :
                puddleMap[i][j] = 0
            else :
                puddleMap[i][j] += puddleMap[i][j-1] + puddleMap[i-1][j]
    
    
    return puddleMap[-1][-1] % 1000000007

위의 파이썬 풀이 1은 효율성이 간당간당하게 나옵니다. 풀이 2가 훨씬 좋은 효율성을 보여줍니다. 풀이 1을 자바 코드를 그대로 옮기려다보니 좋은 코드가 안나와서 다른 분들의 답안을 참고해보니 파이썬을 좀 더 활용하는 방법이 있어서 풀이 2도 남깁니다.

알고리즘 초보가 정리한 글입니다
더 좋은 방법이나 코드에 대한 코멘트 언제나 환영합니다!
반응형