1.

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
 
vector<vector<string>> relations;
vector<int> ans;
int row;
int col;
 
int check_min(int bit)
{
    // 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어있지 않다면, 최소성 만족 X
    for(int i = 0; i < ans.size(); i++)
    {
        if((ans[i] & bit) == ans[i])
        {
            return 0;
        }
    }
 
    // 최소성 만족 O
    return 1;
}
 
int solution(vector<vector<string>> relation) 
{
    relations = relation;
    row = relation.size();
    col = relation[0].size();
    
    // 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다 -> 유일성 만족 O
    for(int i = 1; i < (1 << col); i++)
    {
        map<stringint> check;
        
        for(int j = 0; j < row; j++)
        {
            string now;
            
            for(int k = 0; k < col; k++)
            {
                if(i & (1 << k))
                {
                    now += relation[j][k];        
                }
            }
            
            check[now] = 1;
        }
        
        if(check.size() == row && check_min(i) == 1)
        {
            ans.push_back(i);
        }
    }
    
    return ans.size();
}
 
cs

 

2.

#include <string>
#include <vector>
#include <iostream>
#include <map>
using namespace std;
 
vector<vector<string>> relations;
vector<int> ans;
int row;
int col;
 
int check_min(int bit)
{
    // 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어있지 않다면, 최소성 만족 X
    for(int i = 0; i < ans.size(); i++)
    {
        if((ans[i] & bit) == ans[i])
        {
            return 0;
        }
    }
 
    // 최소성 만족 O
    return 1;
}
 
int solution(vector<vector<string>> relation) 
{
    relations = relation;
    row = relation.size();
    col = relation[0].size();
    
    // 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다 -> 유일성 만족 O
    for(int i = 1; i < (1 << col); i++)
    {
        map<stringint> check;
        
        for(int j = 0; j < row; j++)
        {
            string now;
            
            for(int k = 0; k < col; k++)
            {
                if(i & (1 << k))
                {
                    now += relation[j][k];        
                }
            }
            
            check[now] = 1;
        }
        
        if(check.size() == row && check_min(i) == 1)
        {
            ans.push_back(i);
        }
    }
    
    return ans.size();
}
 
cs

1.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
vector<int> s;
vector<int> e;
vector<string> name;
vector<string> content;
 
// 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환
bool cmp(pair<stringint> a, pair<stringint> b)
{
    if(a.second < b.second)
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
string solution(string m, vector<string> musicinfos) 
{
    string answer = "";
    
    // C# -> c, D# -> d, F# -> f, G# -> g, A#-> a 변환
    for(int i = 0; i < m.size(); i++)
    {
        int idx = 0;
        
        while(m.find("#", idx) != string::npos)
        {
            idx = m.find("#", idx);
            char lower_alphabet = m[idx-1]-'A'+'a';
            string alphabet;
            alphabet += lower_alphabet;
            m.replace(idx-12, alphabet);
        }
    }
    
    for(int i = 0; i < musicinfos.size(); i++)
    {
        int idx = 0;
        
        while(musicinfos[i].find("#", idx) != string::npos)
        {
            idx = musicinfos[i].find("#", idx);
            char lower_alphabet = musicinfos[i][idx-1]-'A'+'a';
            string alphabet;
            alphabet += lower_alphabet;
            musicinfos[i].replace(idx-12, alphabet);
        }
    }
    
    // 시작시각, 끝난시각, 제목, 악보별 정리
    for(int i = 0; i < musicinfos.size(); i++)
    {
        int temp_start = 0;  // 시작시각을 분으로 저장
        int temp_arrive = 0// 도착시각을 분으로 저장
        
        string hour = musicinfos[i].substr(0,2); // 시
        string minute = musicinfos[i].substr(3,2); // 분
        
        temp_start = stoi(hour)*60 + stoi(minute);
        
        hour = musicinfos[i].substr(6,2);
        minute = musicinfos[i].substr(9,2);
        
        temp_arrive = stoi(hour)*60 + stoi(minute);
        
        s.push_back(temp_start);
        e.push_back(temp_arrive);
        
        int j;
        string temp_name;
        for(j = 12; musicinfos[i][j] != ','; j++)
        {
            temp_name += musicinfos[i][j];
        }
        name.push_back(temp_name);
        
        j++;
        string temp_content;
        for(int k = j; k < musicinfos[i].size(); k++)
        {
            temp_content += musicinfos[i][k];
        }
        content.push_back(temp_content);
    }
    
    int max_play = 0// 제일 긴 재생 시간 저장
    vector<pair<stringint>> reserve; // 음악 제목, 인덱스 저장
    
    // 시작입력의 갯수 = 음악의 갯수만큼 반복
    for(int i = 0; i < s.size(); i++)
    {
        int diff = e[i]-s[i];
        string total_content;
        
        for(int j = 0; j < diff; j++)
        {
            total_content += content[i][j % content[i].size()];
        }
        
        if(total_content.find(m) != string::npos)
        {
            // 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환
            if(diff > max_play)
            {
                reserve.clear();
                
                max_play = diff;
                reserve.push_back({name[i], i});
            }
            else if(diff == max_play)
            {
                reserve.push_back({name[i], i});
            }
        }
    }
    
    if(reserve.size() == 0)
    {
        answer = "(None)";
    }
    else if(reserve.size() == 1)
    {
        answer = reserve[0].first;
    }
    else
    {
        sort(reserve.begin(), reserve.end(), cmp);   
        answer = reserve[0].first;
    }
    
    return answer;
}
cs

 

2.

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
vector<int> s;
vector<int> e;
vector<string> name;
vector<string> content[110];
 
// 재생된 시간도 같을 경우 먼저 입력된 음악 제목을 반환
bool cmp(pair<stringint> a, pair<stringint> b)
{
    if(a.second < b.second)
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
string solution(string m, vector<string> musicinfos) 
{
    string answer = "";
    
    // 시작시각, 끝난시각, 제목, 악보별 정리
    for(int i = 0; i < musicinfos.size(); i++)
    {
        int temp_start = 0;  // 시작시각을 분으로 저장
        int temp_arrive = 0// 도착시각을 분으로 저장
        
        string hour = musicinfos[i].substr(0,2); // 시
        string minute = musicinfos[i].substr(3,2); // 분
        
        temp_start = stoi(hour)*60 + stoi(minute);
        
        hour = musicinfos[i].substr(6,2);
        minute = musicinfos[i].substr(9,2);
        
        temp_arrive = stoi(hour)*60 + stoi(minute);
        
        s.push_back(temp_start);
        e.push_back(temp_arrive);
        
        int j;
        string temp_name;
        for(j = 12; musicinfos[i][j] != ','; j++)
        {
            temp_name += musicinfos[i][j];
        }
        name.push_back(temp_name);
        
        j++;
        for(int k = j; k < musicinfos[i].size(); k++)
        {
            string temp_content;
            
            if(k+1 < musicinfos[i].size() && musicinfos[i][k+1== '#')
            {
                temp_content += musicinfos[i][k];
                temp_content += musicinfos[i][k+1];
                temp_content += '.'// # 구분을 위해서 . 삽입
                
                k = k+1;
                content[i].push_back(temp_content);
            }
            else
            {
                temp_content += musicinfos[i][k];
                temp_content += '.'// # 구분을 위해서 . 삽입
                
                content[i].push_back(temp_content);
            }
        }
    }
    
    // 악보의 음마다 . 삽입했기때문에 찾는 m의 사이사이마다 . 삽입한 M 생성
    string M;
    for(int i = 0; i < m.size(); i++)
    {
        if(i+1 < m.size() && m[i+1== '#')
        {
            M += m[i];
            M += m[i+1];
            M += '.';
            
            i = i+1;
        }
        else
        {
            M += m[i];
            M += '.';   
        }
    }
    
    int max_play = 0// 제일 긴 재생 시간 저장
    vector<pair<stringint>> reserve; // 음악 제목, 인덱스 저장
    
    // 시작입력의 갯수 = 음악의 갯수만큼 반복
    for(int i = 0; i < s.size(); i++)
    {
        int diff = e[i]-s[i];
        string total_content;
        
        for(int j = 0; j < diff; j++)
        {
            total_content += content[i][j % content[i].size()];
        }
        
        if(total_content.find(M) != string::npos)
        {
            // 조건이 일치하는 음악이 여러 개일 때에는 라디오에서 재생된 시간이 제일 긴 음악 제목을 반환
            if(diff > max_play)
            {
                reserve.clear();
                
                max_play = diff;
                reserve.push_back({name[i], i});
            }
            else if(diff == max_play)
            {
                reserve.push_back({name[i], i});
            }
        }
    }
    
    if(reserve.size() == 0)
    {
        answer = "(None)";
    }
    else if(reserve.size() == 1)
    {
        answer = reserve[0].first;
    }
    else
    {
        sort(reserve.begin(), reserve.end(), cmp);   
        answer = reserve[0].first;
    }
    
    return answer;
}
cs

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <map>
#include <string.h>
#include <algorithm>
using namespace std;
 
char block[35][35];
int visited[35][35];
int row, col;
bool bomb_flag = false;
 
int dx[4= {-1100};
int dy[4= {00-11};
 
int safe(int x, int y)
{
    if(x >= 0 && x < row && y >= 0 && y < col)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void bomb(int x, int y)
{
    vector<pair<intint>> del; // 삭제할 블럭 좌표 저장
    queue<pair<intint>> q;
    
    q.push({x, y});
    visited[x][y] = 1;
    del.push_back({x, y});
    
    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(safe(xpos, ypos) == 1 && block[xpos][ypos] == block[x][y] && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = 1;
                q.push({xpos, ypos});
                del.push_back({xpos, ypos});
            }
        }
    }
    
    // 삭제할 좌표가 4개이상이면 2*2블록 후보이기 때문에 맞는지 체크
    if(del.size() >= 4)
    {
        sort(del.begin(), del.end());
        
        // 2*2 블록인지 체크
        int check_block[35][35];
        memset(check_block, 0sizeof(check_block));
        
        for(int i = 0; i < del.size(); i++)
        {
            vector<pair<intint>> temp;
            int xx = del[i].first;
            int yy = del[i].second;
            
            temp.push_back({xx, yy});
            
            if(safe(xx+1, yy) == 1 && safe(xx, yy+1== 1 && safe(xx+1, yy+1== 1)
            {
                if(block[xx][yy] == block[xx+1][yy])
                {
                    temp.push_back({xx+1, yy});
                }
                
                if(block[xx][yy] == block[xx][yy+1])
                {
                    temp.push_back({xx, yy+1});
                }
                
                if(block[xx][yy] == block[xx+1][yy+1])
                {
                    temp.push_back({xx+1, yy+1});
                }
            }
            
            // 2*2 블록이 맞으면 check_block에 표시
            if(temp.size() == 4)
            {  
                for(int k = 0; k < temp.size(); k++)
                {
                    check_block[temp[k].first][temp[k].second] += 1;
                }
            }
        }
        
        // 2*2 블록 bomb
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(check_block[i][j] >= 1)
                {
                    // 터지면 종료조건 true
                    bomb_flag = true;
                    block[i][j] = '0';
                }
            }
        }
        
        // 블록이 아래로 떨어지는 경우
        for(int i = 0; i < col; i++)
        {
            queue<char> temp_q;
            
            for(int j = row-1; j >= 0; j--)
            {
                if(block[j][i] != '0')
                {
                    temp_q.push({block[j][i]});
                }
                
                block[j][i] = '0';
            }
            
            for(int j = row-1!temp_q.empty(); j--)
            {
                block[j][i] = temp_q.front();
                temp_q.pop();
            }
        }
    }
}
 
int solution(int m, int n, vector<string> board) 
{
    row = m;
    col = n;
    
    for(int i = 0; i < row; i++)
    {
        for(int j = 0 ; j < col; j++)
        {
            block[i][j] = board[i][j];
        }
    }
    
    while(1)
    {
        bomb_flag = false;
        memset(visited, 0sizeof(visited));
        
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(visited[i][j] == 0 && block[i][j] != '0')
                {
                    bomb(i, j);
                }
            }
        }   
        
        if(bomb_flag == false)
        {
            break;
        }
    }
    
    // block이 0인 갯수 세기 == 터진 갯수
    int answer = 0;
    for(int i = 0; i < row; i++)
    {
        for(int j = 0; j < col; j++)
        {
            if(block[i][j] == '0')
            {
                answer++;
            }
        }
    }
    
    return answer;
}
cs
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
int solution(string name) 
{
    int answer = 0;
    string start;
    
    for(int i = 0; i < name.size(); i++)
    {
        start += "A";
    }
    
    int nowIdx = 0;
    while(1)
    {   
        answer += min(name[nowIdx] - 'A''Z' - name[nowIdx] + 1);
        start[nowIdx] = name[nowIdx];
        
        if(start == name)
        {
            return answer;
        }
        
        // 1. 왼쪽 이동 횟수 구하기
        int leftIdx = nowIdx;
        int leftCnt = 0;
        
        while(start[leftIdx] == name[leftIdx])
        {
            leftIdx--;
            leftCnt++;
            
            // 왼쪽으로 이동시에 범위를 벗어나는 경우
            if(leftIdx == -1)
            {
                leftIdx = name.size()-1;
            }
        }
        
        // 2. 오른쪽 이동 횟수 구하기
        int rightIdx = nowIdx;
        int rightCnt = 0;
        
        while(start[rightIdx] == name[rightIdx])
        {
            rightIdx++;
            rightCnt++;
            
            // 오른쪽으로 이동시에 범위를 벗어나는 경우
            if(rightIdx == name.size())
            {
                rightIdx = 0;
            }      
        }
        
        // 3. 왼쪽, 오른쪽 중 횟수가 최소인 방향을 선택
        // 왼쪽 선택
        if(leftCnt < rightCnt)
        {
            answer += leftCnt;
            nowIdx = leftIdx;
        }
        // 오른쪽 선택
        else
        {
            answer += rightCnt;
            nowIdx = rightIdx;
        }
    }
}
cs
#include <iostream>
using namespace std;
 
int solution(int n)
{
    int ans = 0;
    
    while(n > 0)
    {
        if(n % 2 == 0)
        {
            n /= 2;
        }
        else
        {
            n -= 1;
            ans++;
        }
    }
 
    return ans;
}
cs

1.

#include <string>
#include <vector>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;
 
vector<char> people;
int visited[8];
int answer;
 
void permutation(string result, vector<string> data, int cnt)
{
    if(cnt == 8)
    {        
        for(int i = 0; i < data.size(); i++)
        {
            int p1Idx, p2Idx;
            
            // result에서, 조건에 있는 두사람의 인덱스를 찾음
            for(int j = 0; j < 8; j++)
            {
                if(result[j] == data[i][0])
                {
                    p1Idx = j;
                }
                else if(result[j] == data[i][2])
                {
                    p2Idx = j;
                }
            }
            
            if(data[i][3== '>')
            {
                if(!(abs(p1Idx-p2Idx)-1 > data[i][4]-'0')) 
                {
                    return;
                }
            }
            else if(data[i][3== '=')
            {
                if(!(abs(p1Idx-p2Idx)-1 == data[i][4]-'0')) 
                {
                    return;
                }
            }
            else if(data[i][3== '<')
            {
                if(!(abs(p1Idx-p2Idx)-1 < data[i][4]-'0'))   
                {
                    return;
                }
            }
        }
        
        answer++;
        
        return;
    }
    
    for(int i = 0; i < 8; i++)
    {
        if(visited[i] == 0)
        {        
            visited[i] = 1;
            permutation(result + people[i], data, cnt+1);
            visited[i] = 0;
        } 
    }
}
 
int solution(int n, vector<string> data) 
{
    // 전역변수 초기화
    people.push_back('A');
    people.push_back('C');
    people.push_back('F');
    people.push_back('J');
    people.push_back('M');
    people.push_back('N');
    people.push_back('R');
    people.push_back('T');
    memset(visited, 0sizeof(visited));
    answer = 0;
    
    permutation("", data, 0);
 
    return answer;
}
cs

 

2.

#include <string>
#include <vector>
#include <math.h>
#include <string.h>
#include <iostream>
using namespace std;
 
typedef struct node
{
    char p1;
    char p2;
    char command;
    int diff;
}node;
 
vector<char> people;
int visited[8];
int answer;
 
void permutation(string result, vector<node> condition, int cnt)
{
    if(cnt == 8)
    {        
        for(int i = 0; i < condition.size(); i++)
        {
            int p1Idx, p2Idx;
            
            // result에서, 조건에 있는 두사람의 인덱스를 찾음
            for(int j = 0; j < result.size(); j++)
            {
                if(result[j] == condition[i].p1)
                {
                    p1Idx = j;
                }
                else if(result[j] == condition[i].p2)
                {
                    p2Idx = j;
                }
            }
            
            if(condition[i].command == '>')
            {
                if(!(abs(p1Idx-p2Idx)-1 > condition[i].diff))   
                {
                    return;
                }
            }
            else if(condition[i].command == '=')
            {
                if(!(abs(p1Idx-p2Idx)-1 == condition[i].diff))
                {
                    return;
                }
            }
            else if(condition[i].command == '<')
            {
                if(!(abs(p1Idx-p2Idx)-1 < condition[i].diff))   
                {
                    return;
                }
            }
        }
        
        answer++;
        
        return;
    }
    
    for(int i = 0; i < 8; i++)
    {
        if(visited[i] == 0)
        {    
            string temp;
            temp += people[i];
            
            visited[i] = 1;
            permutation(result + temp, condition, cnt+1);
            visited[i] = 0;
        } 
    }
}
 
// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) 
{
    // 구조체를 사용할 경우 -> node 포함한 선언은 solution 안에 한 후 초기화해야함
    vector<node> condition;
    
    // 전역변수 초기화
    people.push_back('A');
    people.push_back('C');
    people.push_back('F');
    people.push_back('J');
    people.push_back('M');
    people.push_back('N');
    people.push_back('R');
    people.push_back('T');
    memset(visited, 0sizeof(visited));
    answer = 0;
    
    for(int i = 0; i < data.size(); i++)
    {
        condition.push_back({data[i][0], data[i][2], data[i][3], data[i][4]-'0'});   
    }
    
    permutation("", condition, 0);
 
    return answer;
}
cs
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(vector<int> citations) 
{
    sort(citations.begin(), citations.end());
    
    for(int k = citations[citations.size()-1]; k >= 0; k--)
    {
        int cnt = 0;
        
        for(int i = citations.size()-1; i >= 0; i--)
        {
            if(k <= citations[i])
            {
                cnt++;
            }
            else
            {
                break;
            }
        }   
        
        if(cnt >= k && citations.size()-cnt <= k)
        {
            return k;
        }
    }
}
cs
#include <iostream>
using namespace std;
 
long long gcd(long long a, long long b)
{
    if(b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b, a%b);
    }
}
 
long long solution(int w,int h)
{
    long long W = w;
    long long H = h;
    long long divide = gcd(W, H);
    
    long long notUse = (W / divide) + (H / divide) - 1;
    notUse *= divide;
    
    return W * H - notUse;
}
cs

+ Recent posts