99클럽 코테 스터디 1일차 TIL : n^2배열 자르기

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

프로그래머스

 

문제자체는 쉬웠다!

문제가 설명하는 2차원배열을 만들려고 생각하지말고, index와 data사이의 규칙을 찾아서 잘 넣어주면 되는 문제였다.

---

첫번째 접근법 : 문제가 설명한 2차원 배열 만들어주기

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    
    vector<vector<int>> n2array(n, vector<int>(n, 0));
    
    for(int i = 0; i<n; i++){
        for(int j = 0; j<n; j++){
            int max;
            if(i > j){
                max = i;
            }else{
                max = j;
            }
            n2array[i][j] = max+1;
        }
    }
    
    for(int i = left; i<=right; i++){
        int a = i/n;
        int b = i%n;
        answer.push_back(n2array[a][b]);
    }
    
    return answer;
}

시간초과가 나왔다!

 

---

두번째 방법 : 2차원 배열 만들지 말기

1. 2차원 배열을, 1차원으로 늘렸을 때 index는 어떻게 변할까? 를 잘 생각해야한다.

2차원배열의 index가 [i][j]라고 생각하면, 1차원으로 늘리면? i*n + j가 된다.

=> 즉 1차원 배열의 index가 k라고 생각하면, 반대로 [k/n][k%n]으로 2차원 index를 표현해줄 수 있다.

맨 처음 2차원배열을 만들때 들어가는 값은 index만을 가지고 생각해줄 수 있으므로, 2차원배열 생성 자체가 필요하지 않다

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    
    for(int i = left; i<=right; i++){
        int a = i/n;
        int b = i%n;
        int maxnum = a > b ? a : b;
        answer.push_back(maxnum+1);
    }
    
    return answer;
}

하지만 해당 코드도 시간초과가 나왔다.

왜...?싶었는데 함정이 있었다.

left와 right의 타입이 int가 아닌 long long이었다.

 

for문을 돌릴 때, i가 int인 경우, left의 값이 int범위를 넘어가면 overflow로 인해 조건에 걸려지지 못해 무한루프에 빠지게된다!

 

int는 4바이트로 표현되어, 숫자의 경우 -2,147,483,648 ~ 2,147,483,647 라는 범위를 가지게된다.

long long은 8바이트로 표현되어, -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 라는 범위를 가지게된다.

 

만약 i가 2,147,483,647 다음 숫자인 2,147,483,648 을 표현해야 하는 차례가 오면, i의 type이 int여서 overflow가 발생해, 실제로는 -2,147,483,648 로 표현되게 된다.

즉 저 범위만 빙글빙글 돌기때문에 i <= right 라는조건을 항상 만족하게 된다.

 

---

세번째 방법 : type 바꿔주기

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    
    for(long long i = left; i<=right; i++){
        long long a = i/n;
        long long b = i%n;
        long long maxnum = a > b ? a : b;
        answer.push_back(maxnum+1);
    }
    
    return answer;
}

다음과같이 i를 long long으로 바꿔주면, 코드가 잘 돌아간다!

 

---

흠,,, 작년에 컴파일러, 시프를 들으면서 이런 비슷한 상황을 배웠던 기억이 난다.

근데 바로 생각하지 못하고 좀 오래 생각했던것같다..

역시 공부랑 실제로 적용하는건 다르구나..ㅎㅎㅎ

이번에는 빠지는날 없이 올출에 도전하도록 하겠다!