99코딩

문제 조건

• 같은 모양의 블록이 2x2 형태로 붙어있을 경우 지워진다.
• 한 블록이 여러 개의 2x2에 포함될 수 있다.
• 조건에 만족하는 2x2 모양이 여러 개 있다면 한 번에 지워진다.
• 조건에 만족하는 블록들이 한 차례 지워진 후 남은 블록들이 아래로 떨어져 빈 공간을 채우고 다시 위를 반복한다.
• 최종적으로 지워진 블록들의 개수를 반환한다.

풀이 방법

1. 제거될 블록이 있는지를 확인하기 위한 flag와 어느 위치의 블록이 제거될지를 체크 해놓을 bool형 2차원 벡터 check를 선언한다.

2. check와 flag를 false로 초기화한다.

3. 반복문을 통해 제거될 블록들을 체크한다.

4. check[i][j]가 true일 경우 board[i][j]에 공백을 대입하고 answer++한다.

5. 아래에 공백이 있을 경우 블록을 아래로 떨어뜨려준다.

6. flag가 true라면 2번으로 돌아간다.

7. answer 리턴

#include <string>
#include <vector>

using namespace std;

int solution(int m, int n, vector<string> board) {
    int answer = 0;
    bool flag = false;
    vector<vector<bool>> check(m, vector<bool>(n, false));
    
    do {
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++)
                check[i][j] = false;
        }
        
        flag = false;
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(i == 0 || j == 0 || board[i][j] == ' ')
                    continue;
                else if(board[i][j] == board[i - 1][j] && 
                        board[i - 1][j] == board[i - 1][j - 1] && 
                        board[i - 1][j - 1] == board[i][j - 1]) {
                    check[i][j] = true;
                    check[i - 1][j] = true;
                    check[i - 1][j - 1] = true;
                    check[i][j - 1] = true;
                    flag = true;
                }
            }    
        }
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(check[i][j] == true) {
                    board[i][j] = ' ';
                    answer++;
                }
            }
        }
        
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(board[i][j] == ' ') {
                    for(int k = i; k > 0; k--) {
                        if(board[k - 1][j] == ' ')
                            break;
                        board[k][j] = board[k - 1][j];
                        board[k - 1][j] = ' ';
                    }
                }
            }
        }
    } while(flag);
    
    return answer;
}

풀이 방법

map 자료구조를 이용하여 일단 m2에 topping의 데이터를 전부 담는다. 이후 m1[topping]에 더하고 m2[topping]에서 빼는 것을 반복하며 m1, m2의 크기를 비교해 크기가 같다면 롤케이크가 공평하게 잘린것이므로 answer++해준다.

#include <string>
#include <vector>
#include <map>

using namespace std;

int solution(vector<int> topping) {
    int answer = 0;
    
    map<int, int> m1;
    map<int, int> m2;
    
    for(int i = 0; i < topping.size(); i++)
        m2[topping[i]]++;
    
    for(int i = 0; i < topping.size(); i++) {
        m1[topping[i]]++;
        m2[topping[i]]--;
        
        if(!m2[topping[i]]) m2.erase(topping[i]);
        if(m1.size() == m2.size()) answer++;
    }
    
    return answer;
}

풀이방법

BFS(너비 우선 탐색) 알고리즘을 이용해서 최단거리를 구할 수 있다.

#include <vector>
#include <queue>

using namespace std;

bool check[101][101] = {0};
int board[101][101] = {0};

int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0 ,-1, 0};

queue<pair<int, int>> q;

int solution(vector<vector<int> > maps) {
    int answer = 0;
    
    int m = maps.size();
    int n = maps[0].size();
    
    q.push({0,0});
    check[0][0] = true;
    board[0][0] = 1;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int curX = dx[i] + x;
            int curY = dy[i] + y;
            
            if(curX < 0 || curX >= m || curY < 0 || curY >= n) continue;
            if(check[curX][curY]) continue;
            if(!maps[curX][curY]) continue;
            
            check[curX][curY] = true;
            q.push({curX, curY});
            board[curX][curY] = board[x][y] + 1;
        }
    }
    
    if(!board[m-1][n-1]) return -1;
    else return board[m-1][n-1];
}

조건

• 구해야 하는 수 f는 x보다 크고 x와 비트가 1~2개 다른 수 중 가장 작은 수이다.

풀이 방법

양의 정수 x가 짝수라면 비트가 무조건 0으로 끝나게 되므로 1만 더하면 간단하게 f를 구할 수 있다.

x가 홀수라면 최하위 비트에서 최상위 비트로 이동하며 0인 곳을 찾고 해당 부분이 1이 되게 값을 더한 결과가 f가 된다.

#include <string>
#include <vector>

using namespace std;

vector<long long> solution(vector<long long> numbers) {
    vector<long long> answer;
    
    for(int i = 0 ; i < numbers.size(); i++) {
        if(numbers[i] % 2 == 0)
            answer.push_back(numbers[i] + 1);
        else {
            long long bit = 1;
            
            while(true) {
                if(!(numbers[i] & bit)) break;
                bit *= 2;
            }
            bit /= 2;
            answer.push_back(numbers[i] + bit);
        }
    }
    
    return answer;
}

풀이방법

0부터 t x m까지의 숫자를 n진법으로 변환해서 temp에 더한다. 이후 temp에서 튜브가 말해야 하는 숫자들만 구해서 answer에 담아 리턴한다.

#include <string>
#include <vector>

using namespace std;

string convert(int n, int num) {
    char list[] = {'0', '1', '2', '3', '4', '5', '6', '7',
                   '8', '9', 'A', 'B', 'C', 'D', 'E', 'F'};
    
    string temp = "";
    
    while(num / n != 0) {
        temp = list[num % n] + temp;
        num /= n;
    }
    temp = list[num % n] + temp;
    
    return temp;
}

string solution(int n, int t, int m, int p) {
    string answer = "";
    string temp = "";
    int count = 0;
    
    for(int i = 0; i < t * m; i++) temp += convert(n, i);
    for(int i = p - 1; i < temp.length(), count < t; i += m, count++;)
        answer += temp[i];
    
    return answer;
}

문제 이해

• 문제에서 블록 번호에 따른 숫자 블록은 블록 번호의 가장 큰 약수이다.
• 10000000의 구간마다 0, 1, 1, 2, 1...의 규칙이 반복된다.

풀이방법

1-1. begin이 1이라면 answer에 0을 담고 continue

1-2. 약수를 체크해서 나머지가 0이고 몫이 10000000이하라면 i / j를 answer에 담고 flag = true를 해준 뒤 break

1-3. flag가 false라면 해당 번호는 소수이므로 1을 answer에 담는다

2. 위를 begin부터 end까지 반복 

#include <string>
#include <vector>

using namespace std;

vector<int> solution(long long begin, long long end) {
    vector<int> answer;
    
    for(int i = begin; i <= end; i++) {
        bool flag = false;
        if(i == 1) {
            answer.push_back(0);
            continue;
        }
        
        for(int j = 2; j*j <= i; j++) {
            if(!(i % j) && (i / j <= 10000000)) {
                answer.push_back(i / j);
                flag = true;
                break;
            }
        }
        
        if(!flag) answer.push_back(1);
    }
    
    return answer;
}

풀이방법

좌표평면에서 원의 1사분면에 점을 찍는 방법을 이용하였다.

#include <string>
#include <vector>
#include <cmath>

using namespace std;

long long solution(int k, int d) {
    long long answer = 0;
    long long y = 0;
    
    for(long long x = 0; x <= d; x += k) {
        y = sqrt((long long)d*d - x*x) / k;
        answer += y + 1;
    }    
    
    return answer;
}

풀이방법

record를 공백을 기준으로 3 단어로 잘라 string형 벡터 tmp에 담고 tmp[0]가 Enter, Leave, Change인지 판별한다.

맵 자료구조를 통해 유저 아이디를 Key, 닉네임을 Value로 하여 저장함으로써 Enter나 Change를 통해 유저 아이디에 따른 닉네임이 저장 및 수정될 수 있도록 하였다.

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<string> solution(vector<string> record) {
    vector<string> answer, userId;
    map<string, string> m;
    
    for(int i = 0; i < record.size(); i++) {
        vector<string> tmp;
        
        string stmp = "";
        for(int j = 0; j < record[i].length(); j++) {
            if(record[i][j] == ' ') {
                tmp.push_back(stmp);
                stmp = "";
            }
            else stmp += record[i][j];
        }
        tmp.push_back(stmp);
        
        if(tmp[0] == "Enter") {
            answer.push_back("님이 들어왔습니다.");
            userId.push_back(tmp[1]);
            m[tmp[1]] = tmp[2];
        }
        else if(tmp[0] == "Leave") {
            answer.push_back("님이 나갔습니다.");
            userId.push_back(tmp[1]);
        }   
        else m[tmp[1]] = tmp[2];
    }
    
    for(int i = 0; i < answer.size(); i++) {
        answer[i] = m[userId[i]] + answer[i];
    }
    
    return answer;
}