코닥쿠 프로그래밍 배우기

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> answer;
vector<bool> used;

bool dfs(vector<vector<string>>& tickets, vector<string>& path, string current, int ticketCount)
{
    if(path.size() == ticketCount + 1)      // 모든 티켓을 사용했으면
    {
        answer = path;
        return true;
    }
    
    for(int i = 0; i < tickets.size(); ++i)
    {
        if(used[i]) continue;
        if(tickets[i][0] != current) continue;
        
        used[i] = true;
        path.push_back(tickets[i][1]);
        
        if(dfs(tickets, path, tickets[i][1], ticketCount)) return true;      // 성공하면 바로 종료
        
        path.pop_back();
        used[i] = false;
    }
    
    return false;
}

vector<string> solution(vector<vector<string>> tickets) 
{
    sort(tickets.begin(), tickets.end());
    
    used.assign(tickets.size(), false);
    vector<string> path;
    path.push_back("ICN");      // 항상 ICN에서 출발
    
    dfs(tickets, path, path[0], tickets.size());
    
    return answer;
}

해설:

dfs로 깊이 탐색.

#include <string>
#include <vector>
#include <stack>
using namespace std;

string solution(int n, int k, vector<string> cmd)
{
    vector<int> up(n + 2), down(n + 2);
    vector<bool> deleted(n, false);
    stack<int> deletedRows;
    
    // 실제 행은 1 ~ n, 0과 n+1은 더미 경계
    for(int i = 0; i <= n + 1; ++i)
    {
        up[i] = i - 1;
        down[i] = i + 1;
    }
    
    int cur = k + 1;   // k가 0-indexed였다면, 더미 때문에 +1 밀어줌
    
    for(string& command : cmd)
    {
        char op = command[0];
        int num = 0;
        if(op == 'U' || op == 'D')
            num = stoi(command.substr(2));
        
        if(op == 'U')
        {
            for(int i = 0; i < num; ++i)
                cur = up[cur];
        }
        else if(op == 'D')
        {
            for(int i = 0; i < num; ++i)
                cur = down[cur];
        }
        else if(op == 'C')
        {
            deleted[cur - 1] = true;   // deleted 배열은 원래 0-indexed 그대로 사용
            deletedRows.push(cur);
            
            up[down[cur]] = up[cur];
            down[up[cur]] = down[cur];
            
            // 삭제 후 커서: 아래가 진짜 행(더미가 아니면)이면 아래로, 아니면 위로
            if(down[cur] <= n)
                cur = down[cur];
            else
                cur = up[cur];
        }
        else if(op == 'Z')
        {
            int restore = deletedRows.top();
            deletedRows.pop();
            deleted[restore - 1] = false;
            
            up[down[restore]] = restore;
            down[up[restore]] = restore;
        }
    }
    
    string answer = "";
    for(int i = 0; i < n; ++i)
        answer += deleted[i] ? "X" : "O";
    return answer;
}

현재

행 번호:  0    1    2    3    4
up:      -1    0    1    2    3
down:     1    2    3    4    5

삭제

행 번호:  0    1    2(삭제됨)   3    4
up:      -1    0    1           1    3
down:     1    3    3           4    5

복구

up[down[restore]] = restore;    // 다시 원래대로 연결
down[up[restore]] = restore;

인덱싱이 깨지는 문제를 위해 더미를 추가.

배열 인덱스:   0(더미)   1    2    3    4    5    6(더미)
실제 의미:              행0  행1  행2  행3  행4

실제

인덱스:   0    1    2    3    4    5    6
up:      -1    0    1    2    3    4    5
down:     1    2    3    4    5    6    7

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

using namespace std;

void debugMatrix(vector<vector<int>>& key)
{
    for(int i = 0; i < 3; ++i)
    {    
        for(int j = 0; j < 3; ++j)
            cout << key[i][j] << " ";
        cout << endl;
    }
    
}

vector<vector<int>> rotate90(vector<vector<int>>& key)
{
    int n = key.size();
    vector<vector<int>> rotated(n, vector<int>(n));
    for(int row = 0; row < n; ++row)
        for(int col = 0; col < n; ++col)
            rotated[col][n - 1 - row] = key[row][col];
    return rotated;
}

bool check(vector<vector<int>>& board, int lockSize, int keySize)
{
    // board 전체 크기 중, 가운데 lock 영역만 확인
    for(int i = keySize; i < keySize + lockSize; ++i)
        for(int j = keySize; j < keySize + lockSize; ++j)
            if(board[i][j] != 1) return false;
    return true;
}

bool solution(vector<vector<int>> key, vector<vector<int>> lock) {

    int lockSize = lock.size();
    int keySize = key.size();
    int boardSize = lockSize + keySize * 2;
    
    
    for(int rotation = 0; rotation < 4; ++rotation)
    {
        key = rotate90(key);        // 매번 90도씩 회전
        
        for(int x = 0; x < boardSize - keySize; ++x)
        {
            for(int y = 0; y < boardSize - keySize; ++y)
            {
                // 큰 board 준비, 가운데에 lock 배치
                vector<vector<int>> board(boardSize, vector<int>(boardSize, 0));
                for(int i = 0; i < lockSize; ++i)
                    for(int j = 0; j < lockSize; ++j)
                        board[i + keySize][j + keySize] = lock[i][j];
                
                // key를 (x, y) 위치에 더하기
                for (int i =0; i < keySize; ++i)
                    for(int j = 0; j <keySize; ++j)
                        board[x+i][y+j] += key[i][j];
                
                
                // lock 영역이 전부 1인지 확인
                if(check(board, lockSize, keySize)) return true;
            }
        }
    }
    
    return false;
}

해설:

key를 회전 시키고 lock에 맞춰야 하며 lock의 배열을 벗어나면 에러가 발생하기 때문에 boardSize = lockSize + keySize * 2로 크기를 늘려준다(board 중앙에 lock을 배치 후 key를 움직여야 하기 테두리*2라고 생각하면 편함)

이제 회전에 대해서는 

rotated[col][n - 1 - row] = key[row][col]; 으로 대입하는데 row = 0, col = 0이라고 대입했을때 이중for문으로 col이 먼저 증가 되기에 현재 row에 있는 값을 col -> [0 2], [1 2], [2 2]으로 옮기다고 생각하면 된다. 이렇게 4번 회전한다.

그리고 keysize만큼 lock을 가운데 배치. 그리고 x,y를 0에서부터 3까지 늘어나며 keysize가 3인 상태에서 board의 lefttop에서 rightbottom까지 점진적으로 전진하며 각과 위치를 늘려가면 0이 안나올때까지 돌려 봅니다.

#include <string>
#include <vector>

using namespace std;

int finalBalancedPoint(string w)
{
    int open = 0, close = 0;
    for (int i = 0; i < w.size(); ++i)
    {
        if(w[i] == '(') open++;
        else close++;
        
        if(open==close) return i + 1;
    }
    return w.size();
}

bool isCorrect(string u)
{
    int balance = 0;
    for(char c : u)
    {
        if(c == '(') balance++;
        else balance--;
        
        if (balance < 0) return false;
    }
    return true;
}

string solve(string w)
{
    if(w.empty()) return w;
    
    int idx = finalBalancedPoint(w);
    string u = w.substr(0, idx);
    string v = w.substr(idx);
    
    if(isCorrect(u))
    {
        return u + solve(v);
    }
    else
    {
        string result = "(" + solve(v) + ")";
        
        string middle = u.substr(1, u.size() - 2);
        for(char& c : middle)
        {
            c = (c == '(') ? ')' : '(';
        }
        
        result += middle;
        return result;
    }
}

string solution(string p) 
{
    return solve(p);
}

#include <string>
#include <vector>

using namespace std;

int compress(string s, int size)
{
    string result = "";
    string prev = s.substr(0, size);        // 첫 덩어리
    int count = 1;
    
    for(int i = size; i < s.size(); i+=size)
    {
        string cur = s.substr(i, size);     // size만큼 잘라서 현재 덩어리 확보
        if(cur == prev)
        {
            count++;        // 이전 덩어리와 같으면 카운트만 증가
        }
        else
        {
            // 다르면 지금까지 쌓이 prev를 결과에 반영
            if(count > 1) result += to_string(count);
            result += prev;
            
            prev = cur;         // 새로운 덩어리로 교체
            count = 1;
        }
    }
    
    // 마지막에 남은 덩어리 처리
    if(count > 1) result += to_string(count);
    result += prev;
    
    return result.size();
}

int solution(string s) 
{
    int size = s.size();
    for(int i = 1; i <= s.size() / 2; ++i)
    {
        int compresslength = compress(s, i);
        size = min(size, compresslength);
    }
    return size;
}

#include <vector>
#include <algorithm>
using namespace std;

int solution(vector<int> people, int limit)
{
    sort(people.begin(), people.end());
    
    int left = 0;                    // 가장 가벼운 사람
    int right = people.size() - 1;   // 가장 무거운 사람
    int boats = 0;
    
    while(left <= right)
    {
        if(people[left] + people[right] <= limit)
        {
            left++;    // 가벼운 사람도 같이 태움
        }
        right--;       // 무거운 사람은 무조건 보트 하나 씀 (같이 타든 혼자 타든)
        boats++;
    }
    
    return boats;
}

해설: limit라는 보트의 무게 제한이 주어지면 한 보트에 태울 수 있는 사람들은 최대 2명이다 만약 두명이 무게 제한을 초과하면 보트는 운영하지 못하며 최소한의 움직임으로 사람들을 옮겨야 함.

이 문제에 핵심은 탐욕법으로 최적의 상황을 만들어 내야 하는것이다. 문제의 제약에서 40~200kg까지 사람의 몸무게는 다양하다.

일반적으로 무거운 사람들은 못탈 수도 있다는 생각에 가벼운 사람들 먼저 빼놓고 무거운 사람들 한번씩 빼면 된다고 생각할 수도 있지만, 그게 아니다.

먼저 sort()를 이용하여 오름차순으로 정렬 후 이제 left = 0에서 right = people.size() - 1 으로 왼쪽과 오름쪽을 탐색하면서 가벼운 사람과 무거운 사람을 탐색하면서 최적의 상태를 만들 수 있는 사람을 찾는다.

요약하면 가벼운 사람은 제일 마지막에 보내고 비교군에서 통과하지 못한 무거운 사람을 먼저 보내는 것이다. 그렇기에 최적을 만나면 둘이 한 보트에 동승한채로 나갈 수 있는것이다.

실제 조건문에서도 left++은 limit 이하에 만족할때만 증가 되는것을 확인할 수 있다.