(프로그래머스 c++) 이차원 배열 대각선 순회하기

https://school.programmers.co.kr/learn/courses/30/lessons/181829

프로그래머스

 

처음 문제를 접했을 때는 단순하게 모든 배열을 순회하면서 조건에 부합하면 값을 더해주는 걸 떠올렸다.

chat gpt 역시 이 방법을 사용했다.

 

문제에서는 아래와 같은 제한사항이 있기 때문에, '굳이 모든 배열을 순회하지 않고 loop의 범위를 제한할 수 있겠다' 라는 생각이 들었다.

1 ≤ board의 길이 ≤ 100
1 ≤ board[i]의 길이 ≤ 100
1 ≤ board[i][j] ≤ 10,000
모든 board[i]의 길이는 같습니다.
0 ≤ k < board의 길이 + board[i]의 길이

 

가독성이 좋지는 않지만, 시간 복잡도는 조금이라도 줄일 수 있을 것 같다.

 

풀이) 이중 loop 범위 제한

#include <string>
#include <vector>

using namespace std;

int solution(vector<vector<int>> board, int k) {
    int answer = 0;
    
    for (int i = 0; i <= k && i < board.size(); ++i) {
        for (int j = 0; j <= k && i + j <= k && j < board[0].size(); ++j) {
            answer += board[i][j];
        }
    }
    return answer;
}

테스트 1 〉	통과 (0.01ms, 4.28MB)
테스트 2 〉	통과 (0.01ms, 4.14MB)
테스트 3 〉	통과 (0.01ms, 4.14MB)
테스트 4 〉	통과 (0.01ms, 3.6MB)
테스트 5 〉	통과 (0.01ms, 4.16MB)
테스트 6 〉	통과 (0.01ms, 4.14MB)
테스트 7 〉	통과 (0.02ms, 4.15MB)
테스트 8 〉	통과 (0.01ms, 3.68MB)
테스트 9 〉	통과 (0.01ms, 4.14MB)

 

Chat GPT 풀이

#include <vector>

using namespace std;

int solution(vector<vector<int>> board, int k) {
    int sum = 0;

    for (int i = 0; i < board.size(); ++i) {
        for (int j = 0; j < board[i].size(); ++j) {
            if (i + j <= k) {
                sum += board[i][j];
            }
        }
    }

    return sum;
}

테스트 1 〉	통과 (0.01ms, 3.67MB)
테스트 2 〉	통과 (0.01ms, 4.2MB)
테스트 3 〉	통과 (0.01ms, 4.15MB)
테스트 4 〉	통과 (0.01ms, 4.21MB)
테스트 5 〉	통과 (0.01ms, 4.13MB)
테스트 6 〉	통과 (0.01ms, 4.02MB)
테스트 7 〉	통과 (0.02ms, 4.2MB)
테스트 8 〉	통과 (0.01ms, 4.21MB)
테스트 9 〉	통과 (0.01ms, 4.21MB)

 

 

두 개의 풀이 비교

 

AI의 힘을 빌려 두 풀이를 비교해보자.

1번 코드(내 풀이)

2번 코드(gpt 풀이)

가독성	❌ 낮음	✅ 높음
안전성 (ragged vector 대응)	❌ 낮음	✅ 높음
성능 (특수 경우)	✅ 약간 높을 수 있음	❌ 전체 순회
유지보수	❌ 어려움	✅ 쉬움

 

음..

 

gpt의 뻔한 풀이는 재미없다.

나 win.

 

현재까지 2승 0패.