오늘의 키워드

사전캠프에 늦게 참여하게 돼서 본캠프 시작 전까지 알고리즘 공부를 하기로 했다.
오늘 문제를 풀면서 알게된 사실 2가지를 정리해 보려고 한다.

bit 연산

사실 bit 연산은 c언어 초창기에나 몇 번 해보고 말았다. 오늘 푼 문제 중에 bit 연산을 사용하는 문제가 있었는데, 처음에 잘못된 접근을 해서 시간초과가 났다. 방법을 모르겠어서 결국 해답을 봄.

프로그래머스 - 2개 이하로 다른 비트 (Lv.2)

문제 설명

양의 정수 x에 대한 함수 f(x)를 다음과 같이 정의합니다.

x보다 크고 x와 비트가 1~2개 다른 수들 중에서 제일 작은 수
예를 들어,

f(2) = 3 입니다. 다음 표와 같이 2보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 3이기 때문입니다.

f(7) = 11 입니다. 다음 표와 같이 7보다 큰 수들 중에서 비트가 다른 지점이 2개 이하이면서 제일 작은 수가 11이기 때문입니다.

정수들이 담긴 배열 numbers가 매개변수로 주어집니다. numbers의 모든 수들에 대하여 각 수의 f 값을 배열에 차례대로 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ numbers의 길이 ≤ 100,000
• 0 ≤ numbers의 모든 수 ≤ 10^15

입출력 예

해결방안

처음엔 무작정 numbers[i]를 c++의 bitset 클래스를 이용해서 bit로 변환하고 xor 연산으로 비교해가면서 수를 찾았더니 마지막 두개의 케이스에서 시간초과가 났다. 그도 그럴게 배열 안에 있는 수의 범위가 10의 15제곱..

다른 사람들이 올솔한 코드를 찾아보니 굳이 이진 코드로 변환하지 않고 bit연산을 하더라.
규칙을 찾는게 중요했다. numbers[i]가 짝수면 정답은 numbers[i] + 1이었고, 홀수면 비트로 변환 했을 때 1의 자리부터 연속된 1의 개수와 정답에 상관 관계가 있었다.
(연속된 1의 개수 -1)개 만큼의 비트를 같게 만들어 줘야 하는데 그만큼의 bit값을 누적해서 더해주면 된다 !

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<long long> solution(vector<long long> numbers)
{
    vector<long long> answer;

    for (auto e : numbers)
    {
        if (e % 2 == 0)
            answer.push_back(e + 1);
        else
        {
            long long bit = 1;
            long long cnt = -1;
            while (e & bit)
            {
                cnt++;
                bit = bit << 1;
            }
            bit = 1;
            long long sum = 0;
            for (int i = 0; i < cnt; i++)
            {
                sum += bit;
                bit = bit << 1;
            }
            answer.push_back(e + sum + 1);
        }
    }

    return answer;
}

while (e & bit)으로 bit가 몇 개 다른지 계산하고, bit << 1로 bit 칸을 넘기며 sum으로 몇을 더해야 하는지 계산한다.
bit 연산은 개념은 어렵지 않은데 이걸 알고리즘에 적용하는게 정말 어려운거 같다..

stable_sort()

sort()와의 차이점은 c++ 내부적으로 sort()는 quick sort로 구현되어 있고, stable_sort()는 merge sort로 구현되어 있다고 한다. 따라서 sort() 사용 시에는 정렬이 필요하지 않은 경우의 인덱스들이 서로 순서가 바뀔 수 있다는 것. 하지만 stable_sort()는 그런 경우가 없다고 한다.

프로그래머스 - 프렌즈 4블록 (Lv.2)

문제 설명

프렌즈4블록
블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

RRFACC
RRRFCC
TRRRAA
TTMMMF
TMMTTJ

각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라

입력 형식

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
  2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력 형식

입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.

입출력 예제

예제에 대한 설명

• 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
• 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.

해결방안

블록이 터진 칸을 탐색해서 해당 칸의 값을 ' ' (공백) 값으로 바꿔놓고 세로 열 row를 string으로 만들고 정렬을 위한 함수인 compare를 따로 작성하여 문자열인 경우엔 정렬하지 않고, 공백인 경우에만 맨 뒤로 미는 식으로 블록이 아래로 떨어지는 처리를 했다.
근데 맞게 해도 오답이 막 나오는것. 로직엔 문제가 없는 것 같은데 말이다.
sort()를 사용해서 그런 것이었다. 이 부분만 stable_sort()로 바꾸니까 바로 올솔이 나왔다.

#include <string>
#include <vector>
#include <algorithm>
#include <cctype>
#include <iostream>

using namespace std;

bool compare(char c1, char c2)
{
    if (c1 == ' ')
        return true;
    else if (c2 == ' ')
        return false;
}

int solution(int m, int n, vector<string> board)
{
    int answer = 0;
    vector<pair<int, int>> eraseBlocks;
    bool isContinue = true;
    while (isContinue)
    {
        for (int i = 0; i < m - 1; i++)
        {
            for (int j = 0; j < n - 1; j++)
            {
                if (isupper(board[i][j]) && board[i][j] == board[i][j + 1] && board[i][j] == board[i + 1][j] && board[i][j] == board[i + 1][j + 1])
                {
                    eraseBlocks.push_back({ i, j });
                    eraseBlocks.push_back({ i, j + 1 });
                    eraseBlocks.push_back({ i + 1, j });
                    eraseBlocks.push_back({ i + 1, j + 1 });
                }
            }
        }
        if (eraseBlocks.empty())
        {
            isContinue = false;
            break;
        }
        stable_sort(eraseBlocks.begin(), eraseBlocks.end());
        eraseBlocks.erase(unique(eraseBlocks.begin(), eraseBlocks.end()), eraseBlocks.end());
        while (!eraseBlocks.empty())
        {
            auto top = eraseBlocks.back();
            eraseBlocks.pop_back();
            board[top.first][top.second] = ' ';
            answer++;
        }

        for (int i = 0; i < n; i++)
        {
            string r = "";
            for (int j = 0; j < m; j++)
                r += board[j][i];
            stable_sort(r.begin(), r.end(), compare);
            for (int j = 0; j < m; j++)
                board[j][i] = r[j];
        }
    }

    return answer;
}

만약에 AB CD가 정렬된다 치면, 문자열끼리는 정렬 할 필요가 없는데도 sort()를 이용하면 ACBD 와 같은 식으로 문자열의 순서가 바뀔 수도 있다는 것이다. 하지만 stable_sort()는 안정적 (정렬 이전의 순서를 보장해준다) 이라서 ABCD끼리의 순서는 바뀌지 않는다 !
앞으로는 이런 라이브러리 함수도 잘 알아둬야겠다.