프로그래머스 2차원 동전 뒤집기 (시간좀 줄여보기)

문제 URL : https://school.programmers.co.kr/learn/courses/30/lessons/131703

프로그래머스

 

문제접근법 :

해당문제는 모의고사 테스트때 문제풀이를 올렸으니 아래 링크를 참고 해주세요

https://congsoony.tistory.com/281

프로그래머스 코딩테스트 실전 대비 모의고사 1차 문제집 22년 07월 13일 10:00 ~ 08월 23일

 

이번엔 문제를 푸는방법이 아닌 알고리즘답게 시간을 줄여보는 방향을 생각해볼겁니다.

그때의 시간복잡도는 2^n * 2^m * 100(2차원 배열의 사이즈)정도의 시간이 걸린다고 얘기했습니다.

n과 m은 최대 10이니 2^(n+m)이기에 2^(20) = 약 100만 정도이고 거기에 또 100을곱해서 1억가까이 된다고했습니다.

 

모든 비트를 끄고 켜야하는 연산을 진행하기위해

2^(n+m)의 이중폴문안에서 beginning을 건드리지않고 새로운 temp 2차원배열 만들어서 복사하기때문에 느릴수밖에없었습니다.

 

그렇다면 다르게 생각해보세요

어차피 bit를 이용하는거니 열의개수는 최대 10개 밖에 되질않아 int형정수로 커버가 가능합니다.

이러면 최대 n*m의 2차원 배열이아닌 

n개의 1차원 배열을 이용해서 2^20 * 10 = 약 1천만정도의 연산이면 충분하겠죠?

 

 

소스코드 : 

#include <bits/stdc++.h>
using namespace std;
int n,m,bitm;
void rowreverse(vector<int> &data,int t){
    for(int i=0;i<n;i++){
        if(t&(1<<i)){
            data[i]^=-1; //-1은 모든비트가 1임 즉 모든비트가 반전이됨
            data[i]&=bitm;// m개의비트만 제외하고 나머지 앞에있는 비트를 전부꺼줘야함
        }
    }
}
void colreverse(vector<int> &data,int t){
    //열을 뒤집는건 행을 뒤집는것처럼 빠르게 -1을 xor하는것처럼 할수가없음 
    for(int i=0;i<m;i++){
        if(t&(1<<i)){
            for(int j=0;j<n;j++){
                data[j]^=(1<<i);
            }
        }
    }
}
vector<int> bitchange(vector<vector<int>> &data){
    vector<int> v;
    for(int i=0;i<data.size();i++){
        int sum=0;
        for(int j=0;j<data[i].size();j++){
            sum<<=1;
            sum|=data[i][j];
        }
        v.push_back(sum);
    }
    return v;
}
int solution(vector<vector<int>> beginning, vector<vector<int>> target) {
    int answer = 1e8;
    n=beginning.size();
    m=beginning[0].size();
    bitm=0;
    for(int i=0;i<m;i++)bitm|=(1<<i);//m개의 열만 1로 셋팅 나머지 왼쪽은 0임
    vector<int> b = bitchange(beginning);//1차원 배열로 n개의 정수로 표현
    vector<int> t = bitchange(target);
    for(int i=0;i<(1<<n);i++){
        for(int j=0;j<(1<<m);j++){
            vector<int> temp = b;
            rowreverse(temp,i);
            colreverse(temp,j);
            if(temp==t){
                answer=min(answer,__builtin_popcount(i)+__builtin_popcount(j));//__builtin_popcount는 비트의 개수를 빠르게 구하기위한 라이브러리
            }
        }
    }
    return answer==1e8?-1:answer;
}

현재 코드 시간

 

 

이전코드의 시간을 보여드릴께요 11~14번 테스트케이스를 잘보세요

 

 

시간을 줄이는 코드를짜보니 약 4배이상 빨라졌네요 ㅋㅋㅋㅋ

 

더빠른 방법같은거 알려주시면 감사하겠습니다.

궁금한점 혹은 모르는점 어떤질문이든  댓글은 언제나 환영입니다.