[1차] 프렌즈4블록

코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
bool compare(pair<char,bool> n, pair<char,bool> c){
    /* true, false 순서 -> false, true로 바꾸기 */
    if(!n.second and c.second) return true; // 변경
    return false;// 순서 유지 
}
int solution(int m, int n, vector<string> board) {
    int ans=0;
    vector<vector<pair<char,bool>>> v(n);
    for(int i=0;i < n;i++)
        for(int j=m-1;j>=0;j--)
            v[i].push_back({board[j][i], false});
    while(true)
    {
        int cnt=0;
         /* 4개 블럭 체크 */
        for(int i=0;i<n-1;i++)
        {
            for(int j=m-1;j>0;j--)
            {
                char c = v[i][j].first;
                if(c == ' ') continue;
                if(v[i+1][j].first==c and v[i][j-1].first==c and v[i+1][j-1].first==c){
                    v[i][j].second = true;
                    v[i+1][j].second = true;
                    v[i][j-1].second = true;
                    v[i+1][j-1].second = true;
                }
            }
        }
        /* 체크된 블럭 삭제 */
        for(int i=0;i<n;i++)
        {
            for(int j=m-1;j>=0;j--)
            {
                if(v[i][j].second and v[i][j].first != ' '){
                    v[i][j].first = ' ';
                    cnt++;
                }
            }
        }
        /* 블록 당기기 */
        for(int i=0;i<n;i++)
            stable_sort(v[i].begin(), v[i].end(), compare);
        if(cnt == 0) break;
        ans+=cnt;
    }
    return ans;
}

• key point
  1) board판에서 사라지는 블록을 sort로 해결하기 위해서
  vector<vector<pair<char,int>>> v;에 저장함
  2) sort() 대신 stable_sort()사용

• 깨달은 점
  1) sort()는 퀵정렬로 구현되어 있어서 가끔 불안정할 수도 있음
  --> stable_sort()로 안정적이게 사용(merge sort로 구현됨)
  2) sort()에 들어가는 compare함수 만들때 원리
  return true --> swap!
return false --> 그대로
첫번째 파라미터 --> next
두번째 파라미터 --> cur

bool compare(pair<int,bool> n, pair<int,bool> c)
{
    /* next의 bool값이 false이고, cur의 bool값이 true일 때 swap!
       --> bool값이 true인 값을 뒤로 보내기 위한 것 */
    if(!n.second and c.second) return true;
    return false;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    vector<pair<char,bool>> a;
    a.push_back({'A',true});
    a.push_back({'B',false});
    a.push_back({'C',false});
    a.push_back({'D',false});

    sort(a.begin(), a.end(), compare);
    for(int i=0;i<a.size();i++)
        cout << a[i].first << ' ';
    return 0;
}