개발자 김수진

[문제]

https://www.acmicpc.net/problem/21611

[풀이]

1. 상어가 구슬 파괴
2. 구슬 이동
3. 구슬 폭발
   
   1. 4개 이상 연속하는 구슬
4. 구슬 이동
5. 구슬 변화
   1. 하나의 그룹 => 구슬 A,B (  A는 구슬의 개수 , B는 구슬 번호)

위와 같은 과정이 M번 반복해서 일어난다.

1번부터 5번까지의 각 과정을 api로 분리하여 구현했다.

상어가 구슬을 파괴하는 과정은 destruct_bead , 구슬이 이동하는 과정은 move_bead, 구슬이 폭발 후 이동하는 과정은  explode_bead, 구슬이 변화하는 과정은 change_bead에서 처리하도록 구현했다. 

또한 모든 과정이 달팽이 모양 회전을 기반으로 발생한다.

첫번째로 상어가 구슬을 파괴하는 과정은 현재 상어 위치를 기반으로 d 방향으로  s 거리만큼에 존재하는 구슬을 파괴하므로 for 문을 통해 간단하게 구할 수 있다. 

두번째로 구슬이 이동하는 과정을 달팽이 모양을 기반으로 회전한다. 또한 회전하는 길이가 1,1,2,2,3,3,4,4,5,5,... 이런식으로 2번씩 같은 길이를 반복하고 방향이 바뀌면서 길이가 +1이 되는 구조이다. 따라서 이중 for문의 바깥 for문에서는 2번을 count 해주고 내부 for문에서는 len 만큼 반복할 수 있도록 처리해줬다. 현재 길이를 두번 다 돌면 길이를 +1 해주도록 처리했고 영역을 벗어나는 경우에 while문을 빠져나오도록 조건을 걸었다. 달팽이 방향으로 한칸씩 다 돌면서 bead라는 일차원 배열을 선언하여 map에서 0이 아닌 값들에 대해서만 옮겨준다. 모든 map에 대해 한바퀴 다 돌고 나면 기존 map을 0으로 초기화 해주고 bead에 존재하는 값들을 복사해준다. 이때도 마찬가지로 달팽이 방향으로 회전하도록 했다.

세번째로 4개 이상 동일한 구슬이 반복되는 것에 대해 그룹화 하여 폭발시켜줬다. 이 때 문제에서 출력해야 되는 것은 폭발된 구슬의 개수이므로 explode_cnt라는 배열을 선언하여 각 구슬별 폭발된 개수를 저장해놨다. 구슬 이동과 마찬가지로 하나의 길이에 대해 두번씩 카운트 하면서 길이를 +1씩 해주었다. 이와 같이 달팽이 방향으로 돌면서 연속하는 구슬이 4개 이상인 경우 폭발 시켜줬다. bead 라는 벡터를 선언하여 폭발되지 않은 구슬만 담아줬다. 이런식으로 폭발할 구슬을 찾으면 한번 더 확인을 해줘야한다. 예를들어 구슬이 111222211111 이렇게 있으면 bead라는 벡터에 11111111이 존재하는데 이것도 연속된 구슬이 4개 이상이므로 폭발해야 하는 구슬이다. 따라서 bead에 대해서 한번 더 돌면서 연속되는 구슬이 있는지 확인해주고 update_bead 라는 벡터에 담아줬다.. 원래 구슬 폭발 후 바로 이동을 해야하는데 모든 그룹에 대해 폭발을 다 하고 이동하는식으로 구현해서 이렇게 된 것 같다. 이 부분에 대해서는 한번 더 고려해봐야겠다. 이렇게 구슬을 폭발하고  update_bead에 존재하는 구슬을 달팽이 방향으로 map에 옮겨줬다.

마지막으로 구슬을 그룹화하여 구슬 개수, 구슬 번호로 구슬을 change 해줬다. 여기서도 마찬가지로 달팽이 방향으로 돌면서 확인해줬다.

이와 같이 위의 방식을 M번 수행 후 각 구슬별 폭발된 구슬의 개수를  count 하여 출력해줬다.

유사 문제로는 

2022 상반기 오전 문제가 있는데 참고해보면 좋을 것 같다.

[코드]

#include <iostream>
#include <vector>
#include<string.h>
#define MAX 50

using namespace std;

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

int N,M;
int map[MAX][MAX]={0,};
int explode_cnt[4] = {0,};

void destruct_bead(int d,int s)
{
    int x = (N+1)/2;
    int y = (N+1)/2;
    
    for(int i=1;i<=s;i++){
        int nx = x + dx[d]*i;
        int ny = y + dy[d]*i;
        
        if( nx <= 0 || ny <= 0 || nx > N || ny > N )    break;
        map[nx][ny] =0;
    }
}

void move_bead()
{
    int tmp[MAX][MAX]={0,};
    
    int bead[MAX*MAX]={0,};
    int x= (N+1)/2;
    int y= (N+1)/2;
    int dir =3;
    int len = 1;
    int idx =0;
    bool flag=true;
    
    
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if ( x <= 0 || y<= 0 || x > N || y > N ){
                    flag=false;
                    break;
                }
                
                if(map[x][y] != 0){
                    bead[idx] = map[x][y];
                    idx++;
                }
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    x= (N+1)/2;
    y= (N+1)/2;
    dir =3;
    len = 1;
    idx =0;
    flag=true;
    
    
    for(int i=1;i<=N;i++){
        for(int j=0;j<=N;j++)   map[i][j]=0;
    }
               
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if ( bead[idx] == 0){
                    flag=false;
                    break;
                }
                map[x][y] = bead[idx];
                idx++;
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
}

void explode_bead()
{
    int tmp[MAX][MAX]={0,};
    
    vector<int> bead;
    
    int x = (N+1)/2;
    int y = (N+1)/2;
    int dir =3;
    int len = 1;
    int idx =0;
    bool flag=true;
    
    
    int cur = -1;
    int cnt = 0;
    
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){

                x+=dx[dir];
                y+=dy[dir];

                if ( x <= 0 || y<= 0 || x > N || y > N || cur == 0){
                    flag=false;
                    break;
                }
                

                if(map[x][y] == cur){
                    cnt++;
                } else {
                    if( cnt >= 4 ){
                        explode_cnt[cur] += cnt;
                        for(int k=0;k<cnt;k++)  bead.pop_back();
                    }
                    cur = map[x][y];
                    cnt = 1;
                }
                bead.push_back(map[x][y]);
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    vector<int> update_bead;
    
    cnt=0;
    cur = -1;
    while(1){
        bool duplicate = false;
        for(int i=0;i<bead.size();i++){
            if(bead[i] == cur){
                cnt++;
            } else {

                if( cnt >= 4 ){
                    duplicate= true;
                    explode_cnt[cur] += cnt;
                    for(int k=0;k<cnt;k++)  update_bead.pop_back();
                }
                cur = bead[i];
                cnt = 1;
            }
            update_bead.push_back(cur);

        }
        if( !duplicate )    break;
        else{
            bead.clear();
            bead = update_bead;
            update_bead.clear();
        }
    }
    
    x= (N+1)/2;
    y= (N+1)/2;
    dir =3;
    len = 1;
    idx =0;
    flag=true;
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if ( idx == update_bead.size()){
                    flag=false;
                    break;
                }
                tmp[x][y] = update_bead[idx];
                idx++;
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)    map[i][j] = tmp[i][j];
    }
}

void bead_change()
{
    
    int tmp[MAX][MAX]={0,};
    
    vector<int> bead;
    
    int x = (N+1)/2;
    int y = (N+1)/2;
    int dir = 3;
    int len = 1;
    int idx = 0;
    bool flag=true;
    
    
    int cur = -1;
    int cnt = 0;
    
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){

                x+=dx[dir];
                y+=dy[dir];

                if ( x <= 0 || y<= 0 || x > N || y > N || cur == 0){
                    flag=false;
                    break;
                }

                if(map[x][y] == cur){
                    cnt++;
                } else {
                    if(cnt>0){
                        bead.push_back(cnt);
                        bead.push_back(cur);
                    }
                    cur = map[x][y];
                    cnt = 1;
                }
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    x= (N+1)/2;
    y= (N+1)/2;
    dir =3;
    len = 1;
    idx =0;
    flag=true;
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if (x <= 0 || y<= 0 || x > N || y > N || idx == bead.size()){
                    flag=false;
                    break;
                }
                tmp[x][y] = bead[idx];
                idx++;
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)    map[i][j] = tmp[i][j];
    }
    
}


int main(void)
{
    cin >> N >> M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)    cin >> map[i][j];
    }
    
    for(int i=0;i<M;i++){
        int d,s;
        cin >> d >> s;
        destruct_bead(d,s);
        move_bead();
        explode_bead();
        bead_change();
    }
    
    cout << explode_cnt[1] * 1 + explode_cnt[2] * 2 + explode_cnt[3] * 3;
    return 0;
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/17677

[풀이]

input string에 대해 두 글자씩 끊어서 다중 집합을 만들고 두 집합 간의 교집합/합집합 * 65536을 구해서 return 해주면 되는 문제

첫 번째로 각 input string에 대해 모두 lower case로 변환해주었다.

다음으로 연속된 두 글자가 알파벳인 경우 vector에 push 해주었다.

이중 for문을 통해 교집합을 구하고 교집합의 중복을 막기 위해 한번 확인한 글자는 #로 변환해주었다.

[코드]

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

bool isChar(char ch){
    if(ch>='a' && ch<='z')  return true;
    if(ch>='A' && ch<='Z')  return true;
    return false;
}

int solution(string str1, string str2) {
    int answer = 0;
    string tmp1="";
    string tmp2="";
    
    for(int i=0;i<str1.size();i++){
        str1[i]=tolower(str1[i]);
    }
    for(int i=0;i<str2.size();i++){
        str2[i]=tolower(str2[i]);
    }
    
    vector<string> p1;
    vector<string> p2;
    for(int i=0;i<str1.size()-1;i++){
        if(isChar(str1[i]) && isChar(str1[i+1]))
            p1.push_back(str1.substr(i,2));
    }    
    for(int i=0;i<str2.size()-1;i++){
        if(isChar(str2[i]) && isChar(str2[i+1]))
            p2.push_back(str2.substr(i,2));
    }
    
    int intersection=0; //교집합
    int _union= p1.size()+ p2.size(); //합집합
    
    for(int i=0;i<p1.size();i++){
        for(int j=0;j<p2.size();j++){
            if(p1[i]==p2[j]){
                intersection++;
                p2[j]="#";
                break;
            } 
        }
    }
    _union-=intersection;
    if(_union == 0)    return 65536;
    answer = intersection * 65536 /_union;
    return answer;
}

문제

https://school.programmers.co.kr/learn/courses/30/lessons/118666?language=cpp

풀이

검사자의 선택지 사이즈만큼 반복하여 결과를 구한다.

map을 사용하여 각 유형의 점수를 관리하였다.

이와 같이 점수를 다 구하여 각 지표별 성격 유형을 구한다.

코드

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

using namespace std;

int score[8] = {0,3,2,1,0,1,2,3};


string solution(vector<string> survey, vector<int> choices) {
    string answer = "";
    map <char, int> m;
    for( int i=0;i<survey.size();i++) {
        string sur= survey[i];
        int ans= choices[i];

        m[sur[ans/4]] += score[ans];
    }
    
    answer += m['R'] >= m['T'] ? "R" : "T";
    answer += m['C'] >= m['F'] ? "C" : "F";
    answer += m['J'] >= m['M'] ? "J" : "M";
    answer += m['A'] >= m['N'] ? "A" : "N";

    return answer;
}

[문제]

https://school.programmers.co.kr/learn/courses/30/lessons/12978

[풀이]

해당 문제는 하나의 정점에서 다른 정점들까지의 최단거리를 구하는 문제이므로 다익스트라 알고리즘을 사용해 풀었다.

map이라는 벡터 배열을 선언하여 각 정점마다 인접한 정점까지의 거리를 가지고 있도로 했다.

또한 1번 정점부터 다른 정점들까지의 거리를 구하기 저장하기 위해 dist 변수를 선언하고 정점의 개수만큼 1e9로 초

기화했다.

다음으로 dijkstra 함수에서는 priority_queue를 사용해 1번 정점에서 다른 정점들까지의 최단거리를 구하도록 했다.

priority_queue는 {1번 정점에서 해당 정점까지의 최단 거리, 정점}을 pair로 가지도록 되어있고 시작점은 1번 정점이므로 먼저 {0,1}을 queue에 push 해줬다. 

다음으로 queue에서 top에 있는 정점을 뽑아 해당 정점과 인접한 정점들은 방문하고 해당 정점까지의 최단거리를 update 해주면 queue에 push 해준다. 이 때 queue는 거리를 기준으로 오름차순하여 정렬하기 때문에 최단거리를 구할 수 있다. 이러한 방식으로 queue가 empty가 아닐 때까지 반복하여 1번 정점으로부터 각 정점까지의 최단거리를 구하게 된다.

마지막으로 각 정점까지의 최단거리가 저장된 dist 배열에서 배달 가능 시간이 K보다 작거나 같은 정점들의 개수를 count 하여 return 해주면 된다. 

[코드]

#include <iostream>
#include <vector>
#include <queue>
#define MAX 51

using namespace std;

vector<int> dist;
vector<pair<int,int>> map[MAX];

void dijkstra()
{
    priority_queue< pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
    pq.push({0,1});
    dist[1] = 0;
    while(!pq.empty()) {
        int cost = pq.top().first;
        int from = pq.top().second;
        pq.pop();
        for(int i =0 ; i< map[from].size(); i++) {
            int to = map[from][i].first;
            int distance = map[from][i].second + cost;
            if (dist[to] > distance){
                dist[to] = distance;
                pq.push({distance, to});
            }
        }
    }
}

int solution(int N, vector<vector<int> > road, int K) {
    int answer = 0;

    for(int i=0;i<road.size();i++){
        int start = road[i][0];
        int end = road[i][1];
        int cost = road[i][2];
        
        map[start].push_back({end,cost});
        map[end].push_back({start,cost});
        
    }
    
    dist.resize(N+1,1e9);
    dijkstra();
    for(int i=1;i<=N;i++){
        if ( dist[i] <= K)  answer++;
    }
    
    return answer;
}

[문제]

https://programmers.co.kr/learn/courses/30/lessons/17680

[풀이]

LRU 알고리즘으로 캐시를 관리하며, 캐시에서 읽어올 경우 +1, 캐시에 존재하지 않는 데이터일 경우 +5를 추가하여 총 실행시간을 구하는 문제이다. 

LRU란 Least Recently Used로 새로운 데이터가 들어올 경우, 가장 오랫동안 참고하지 않은 데이터를 빼고 새로운 데이터를 삽입하는 방식이다.

따라서 각 데이터에 대해 이미 캐시에 데이터가 존재하는지 확인 후 , 존재하지 않는다면 캐시에 삽입하고 +5를 해준다.

존재할 경우 가장 최신에 조회한 데이터이므로 벡터의 맨 뒤로 넣어주고 +1을 하여 총 실행시간을 구할 수 있다.

[코드]

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

using namespace std;

vector <string> v;

string solve(string tmp)
{
    string res = "";
    for(int i=0;i<tmp.size();i++){
        if(tmp[i] >= 97 && tmp[i] <= 122)   res += (tmp[i] - 32);
        else res += tmp[i];
    }
    return res;
}

int solution(int cacheSize, vector<string> cities) {
    int answer = 0;
    
    for(int i=0;i<cities.size();i++){
        string city = solve(cities[i]);
        if(cacheSize == 0) {
            answer+=5;
            continue;
        }
        auto itr = find(v.begin(),v.end(), city);
        if( itr != v.end()) {
            answer += 1;
            v.erase(itr);
        }  
        else{
            if(v.size() == cacheSize){
                v.erase(v.begin());
            }
            answer += 5;
        }
        v.push_back(city);
    }
    return answer;
}

[문제]

https://programmers.co.kr/learn/courses/30/lessons/72411

[풀이]

우선 존재하는 모든 메뉴를 c라는 벡터에 insert 해준다.

결과값은 각 알파벳을 기준으로 오름차순으로 정렬되어 있어야 하므로 c를 오름차순으로 정렬해준다.

그 다음으로 course의 케이스마다 만들 수 있는 모든 메뉴 조합을 DFS 함수를 통해서 구한다.

course  배열의 각 개수를 만족하면 각 손님이 해당 메뉴 조합을 시킨 횟수를 count하고 가장 많이 시킨 메뉴 조합을 result를 위한 벡터인 v에 insert한다.

이러한 방식으로 각 course 케이스에 대한 메뉴 조합을 구하고, 가장 많이 시킨 순서대로 정렬하여 return 하면 된다 .

[코드]

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

using namespace std;

vector<string> order;
vector<char> c;
vector <pair<int , string>> v;
vector <int> comb;
int num=0;

bool comp(const pair<int,string> a, const pair<int,string> b)
{
    if(a.first>b.first) return true;
    else return false;
}

int solve()
{
    int cnt =0;
    for(int i=0;i<order.size();i++){
        bool bCheck = true;
        for(int j=0;j<comb.size();j++){
            if(order[i].find(comb[j]) == -1){
                bCheck= false;
                break;
            }
        }
        if(bCheck)  cnt++;
    }
    return cnt;
}
void DFS(int cnt,int idx)
{
    if(num == cnt)   {
        int res = solve();
        string tmp = "";
        for(int i =0 ;i<comb.size();i++)
            tmp+=comb[i];
        v.push_back({res, tmp});
        return ;
    }
    for(int i=idx;i<c.size();i++){
        comb.push_back(c[i]);
        DFS(cnt+1,i+1);
        comb.pop_back();
    }
}
vector<string> solution(vector<string> orders, vector<int> course) {
    vector<string> answer;
    order = orders;
    
    for(int i=0;i<orders.size();i++){
        for(int j=0;j<orders[i].size();j++){
            if(find(c.begin(),c.end(),orders[i][j]) == c.end()) c.push_back(orders[i][j]);
        }
    
    }
    sort(c.begin(),c.end());
    for(int i=0;i<course.size();i++){
        num = course[i];
        DFS(0,0);
        comb.clear();
        sort(v.begin(),v.end(),comp);
        int res = v[0].first;
        if(res < 2 ) {
            v.clear();
            break;
        }  
        for(int j=0;j<v.size();j++){
            if(v[j].first == res)   answer.push_back(v[j].second);
            else break;
        }
        v.clear();
    }
    sort(answer.begin(),answer.end());
    return answer;
}

[문제]

https://programmers.co.kr/learn/courses/30/lessons/1835

[풀이]

처음 문제 봤을 때 Level2라는게 믿기지 않았다.

도저히 감이 안잡혀서 다른 분들의 풀이를 봤는데 생각보다 간단한 문제였다.

next_permutation 함수를 통해 프렌즈들이 일렬로 설 수 있는 모든 경우의 수를 구할 수 있다.

각 case마다 주어진 조건을 만족하는지 확인 후 , 모든 조건을 만족할 경우 answer에 +1을 해주어 

주어진 조건을 만족하여 사진을 찍는 모든 경우의 수를 구할 수 있다.

[코드]

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

using namespace std;

int len =0;
char sign;

bool check(int diff)
{
    if(sign == '=')
        return diff==len;
    else if(sign == '>')
        return diff > len ? true : false;
    else if(sign == '<')
        return diff < len ? true : false;
}
int solution(int n, vector<string> data) {
    int answer = 0;
    string friends = "ACFJMNRT";

    do{
        bool bCheck = true;
        for(int i=0;i<data.size();i++){
            int diff = friends.find(data[i][0]) - friends.find(data[i][2]);
            sign = data[i][3];
            len = data[i][4]-'0';
            bCheck = check(abs(diff)-1);
            if(!bCheck) break;
        }
        if(bCheck)  answer++;
    }while(next_permutation(friends.begin(),friends.end()));
        
    return answer;
}

[문제]

https://programmers.co.kr/learn/courses/30/lessons/42889

[풀이]

스테이지의 실패율이 같을 경우, 스테이지 번호를 기준으로 오름차순 해야하므로  cmp 함수에서 second 값으로 비교해준다.

[코드]

#include <string>
#include <vector>
#include <algorithm>
#define MAX 501

using namespace std;

int people =0;
double score[MAX]={0,};
vector <pair<double,int>> v;

bool cmp(pair<double,int> a, pair<double,int> b){
    if(a.first > b.first)
        return true;
    else if(a.first == b.first) {
        if(a.second< b.second) {
            return true;
        } else
            return false;
    } 
    else
        return false;
}


vector<int> solution(int N, vector<int> stages) {
    vector<int> answer;
    
    for(int i=1;i<=N;i++)   score[i] =0;
    people = stages.size();
    sort(stages.begin(), stages.end());
    int idx =0;
    int tmp_people = people;
    for(int i=0;i<people;i++){
        if(stages[i] > N)   continue;
        idx=i+1;
        int goal = 1;
        while(idx < people && stages[idx] == stages[i]){
            idx++;
            goal++;
        }
        double d =  (double)goal/tmp_people;
        score[stages[i]] =d;
        tmp_people -= goal;
        i = idx-1;
    }
    for(int i=1;i<=N;i++) 
        v.push_back({score[i],i});
    
    sort(v.begin(), v.end(),cmp);
    for(int i=0;i<N;i++)   answer.push_back(v[i].second);
    return answer;
}