2019 카카오 개발자 겨울 인턴십

https://school.programmers.co.kr/learn/challenges?order=recent&partIds=17931 

코딩테스트 연습 | 프로그래머스 스쿨

1. 크레인 인형뽑기 게임

• 특징: 구현
• 구현방법 
  • board 배열의 각 행에 몇개의 인형이 있는지를 나타내는 top배열을 구현. 
  • moves를 순회하며, board 배열에서 인형을 뽑고, top 배열에서 그 행의 인형개수를 -1.
    • 뽑은 인형이 stack의 top과 같으면, stack의 top을 pop하고, answer + 2
    • 다르면, stack의 뽑은 인형을 넣음. 
• 코드

#include <bits/stdc++.h>

using namespace std;

stack<int> s;
int top[32]; // board배열에 몇개가 채워져있는지.
int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
    int cur = 0;
    int n =  board.size();
    
    fill(top, top+31, -1);
    for(int i = 0; i < board.size(); i++)
    {
        for(int j = 0; j < board.size(); j++)
        {
            if(board[i][j] != 0 && top[j] == -1)
            {
                top[j] = n-i;
            }
        }   
    }
    
    for(int i = 0; i < moves.size(); i++)
    {
        cur = moves[i]; // 1
        
        int topPoint = top[cur-1]; // 2
        if(top[cur-1] != 0)
        {
            board[n-topPoint][cur-1]; // board[3][0] = 4
            top[cur-1]--;
            if(!s.empty())
            {
                int stop = s.top(); 
                if(stop == board[n-topPoint][cur-1])
                {
                    s.pop();
                    answer+=2;
                }
                else
                {
                    s.push(board[n-topPoint][cur-1]);
                }
            }
            else
            {
                s.push(board[n-topPoint][cur-1]);
            }
            
        }
  
    }
    return answer;
}

2. 튜플

• 특징: map
• 구현방법 
  • string으로 들어오는 s의 값을 숫자를 분리하여 map[숫자] = 그 숫자의 빈도수 로 정의함. 
  • 빈도수가 높은 숫자 일수록 앞쪽 원소이다. 따라서 map을 값을 기준으로 내림차순 정렬함.
• 코드 

#include <bits/stdc++.h>

using namespace std;

map<int, int> _map; //m["나온숫자"] = 개수
void split(string str)
{
    string tmp = "";
    for(int i = 0; i < str.size(); i++)
    {
        if((str[i] == '}' || str[i] == ',' || str[i] == '{'))
        {
            if(tmp.size() > 0)
            {
                _map[stoi(tmp)]++;
                tmp = "";
            }
        }
        else
        {
            tmp += str[i];
        }
    }
}

bool cmp(pair<int, int> & a, pair<int, int> & b)
{
   return a.second > b.second;
}

vector<int> solution(string s) {
    vector<int> answer;
    int n = s.size();
    s = s.substr(1, n-2);
    
    split(s);
    
    //map을 값 기준 내림차순 정렬
    vector<pair<int ,int>> _vec(_map.begin(), _map.end());
    
    sort(_vec.begin(), _vec.end(), cmp);
    
    for(auto m:_vec)
    {
        answer.push_back(m.first);
    }
    
    return answer;
}

3. 불량 사용자

• 특징: set
• 구현방법 
  • 특정 banned_id로 금지할 수 있는 단어를 저장하는 벡터를 정의한다. 이 벡터는 배열 형태로 정의하며, 각 banned_id의 index값을 배열의 index로한다. 
    • vector<string> idv[8];
  • banned_id를 순회하면서, 현재 banned_id로 금지될 수 있는 user_id를 찾아 벡터 배열에 넣는다. 
  • dfs를 돈다. 
    • dfs를 돌면서, 경우의 수가 될 수 있는 금지 아이디의 모음인 set<string>으로 정의한 ans를 채운다. ans에 현재 순회하고 있는 아이디가 없는 경우, insert하고 dfs를 호출한다. 
    • dfs가 종료조건에 도달하면, ans에 들어있는 값으로 string을 만들고, 정답을 모아두는 set<string>으로 정의한 tmp에 해당 string을 넣는다. 
  • tmp의 size를 정답으로 출력한다. 
• 주의점
  • set<string> tmp를 사용하지 않았을 때, 두번째 테케에서 
    • {frodo crodo abc123}, {crodo, frodo, frodoc} 같이 내용물은 같지만 순서가 다른 결과를 각각 다른 값으로 인식했다. 
    • tmp를 사용하면 두 경우 모두 abc123crodofrodo로 받아들여, 같은 값으로 인식한다. 
• 코드 

#include <bits/stdc++.h>

using namespace std;

vector<string> userid;
vector<string> idv[8];
set<string> ans;
set<string> tmp;
int n;
int cnt;
void findingfunc(string & str, int num)
{
    int cur_banndedsize = str.size();
    int count = 0;
    bool isT = false;
    for(int i = 0; i < userid.size(); i++)
    {
        if(userid[i].size() != cur_banndedsize) continue;

        for(int k = 0; k < str.size(); k++)
        {
            if(userid[i][k] == str[k] || str[k] == '*')
            {
                isT = false;
            }
            else
            {
                isT = true;
                break;
            }
        }

        if(isT == false)
        {
            idv[num].push_back(userid[i]);
        } 
        isT = false;
    }

}

void dfs(int cur)
{
    if(cur == n)
    {
        cnt++;
        string curtmp = "";
        for(auto e: ans)
        {
            curtmp += e;
        }

        tmp.insert(curtmp);
        return;
    }
    
    for(int i = 0; i < idv[cur].size(); i++)
    {

        if(ans.find(idv[cur][i]) == ans.end())
        {
            ans.insert(idv[cur][i]);
        }
        else
        {
            continue;
        }
        dfs(cur+1);
        ans.erase(idv[cur][i]);
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    n = banned_id.size();
    for(int i = 0; i < user_id.size(); i++)
    {
        userid.push_back(user_id[i]);
    }
    
    for(int i = 0; i < banned_id.size(); i++)
    {
        findingfunc(banned_id[i], i); 
    }
    
    dfs(0);
    answer = tmp.size();
    return answer;
}

 

4. 징검다리 건너기

• 특징: 윈도우 슬라이딩
• 구현방법 
  • stones를 순회하면서, 
    • k만큼 stones를 자른다.(윈도우 슬라이딩)
    • 해당 영역에서 가장 큰값을 저장함. 그리고 순회하면서 이 값의 최솟값을 저장함.  
• 주의할점
  • 윈도우 슬라이딩을 사용하며, 해당 영역에서의 가장 큰 값을 저장하려고 set을 이용했다.... 하지만 multiset을 이용해야 했다. (중복값이 있을 수 있기 때문에)...
• 추가
  • 이 문제는 이분 탐색으로도 풀 수 있다. stones[i] - target을 했을 때, 연속된 0이하의 값이 k개 이상인 target의 최솟값 구하는 이분탐색 코드를 짜면 된다. 
• 코드 - 윈도우 슬라이딩

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    int res = INT_MAX;
    int en = 0;
    
    multiset<int, greater<int>> s;
    s.insert(stones[en]);
    int cnt = k-1;
    
    for(int st = 0; st < stones.size(); st++)
    {
        while(cnt > 0)
        {
            cnt--;
            en++;
            s.insert(stones[en]);
        }
        
        int mx = *s.begin();
        res = min(res, mx);
        
        s.erase(s.find(stones[st]));
        cnt++;

        if(en == stones.size()-1) break;

    }
    
    answer = res;
    return answer;
}

• 코드 - 이분 탐색

#include <bits/stdc++.h>

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    
    int l = *min_element(stones.begin(), stones.end());
    int r = *max_element(stones.begin(), stones.end());

    while(l <= r)
    {
        int mid = (l+r)/2;
        
        int seq = 0;
        bool isT = false;
        for(int i = 0; i < stones.size(); i++)
        {
            if(stones[i] - mid <= 0)
            {
                seq++;
            }
            else
            {
                seq = 0;
            }
            if(seq >= k)
            {
                isT = true;
                break;
            }
            
        } 
        
        if(isT) 
        {
            r = mid - 1;
            answer = mid;
        }
        else
        {
            l = mid +1;
        }
    }
    
    return answer;
}

 

5. 호텔 방 배정

이 문제 못풀었다. k가 10^12이기 때문에 O(n)으로는 시간초과가 난다. 따라서 O(logn) 풀이법인 이분탐색을 시도했다. lower_bound를 이용해서, 호텔 방을 어떻게 배정할 수 있을거같았는데, 도저히 불가능했다. 해답을 봤는데 유니온 파인드로 푸는 문제였다. 유니온 파인드라는 게 있다는 것을 알고있었는데, 뭐인지는 모르고 있어 이참에 공부했다. 

• 특징: 유니온 파인드
• 구현방법 
  • map 정의
    • key: 방번호
    • value: 0이면 빈방, a이면 이 방은 빈방이 아니므로 a번방으로 가라는 의미
  • 유니온 파인드 알고리즘에 사용되는 getParent 함수를 사용하여 해시맵을 타고 타고 가서 다음으로 가능한 빈방을 찾아내 리턴받는다. 
    • 재귀호출 
      • 빈방이 아니라면, 다음 방으로가고 이를 빈방이 나올때까지 반복한다. 
      • 재귀에서 돌아오면서 이 재귀에서 호출된 방들을 빈방 번호로 업데이트 해준다. 
  • 코드

#include <bits/stdc++.h>

using namespace std;

unordered_map<long long, long long> room;

long long GetEmptyRoom(long long n)
{
    if(room[n] == 0) return n;
    else
    {
        long long tmp = GetEmptyRoom(room[n]);
        room[n] = tmp;
        return tmp;
    }
}

vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    
    for(int i = 0; i < room_number.size(); i++)
    {
        long long num = GetEmptyRoom(room_number[i]);
        answer.push_back(num);
        room[num] = num + 1;
    }
    
    
    return answer;
}

풀이 참고: https://ansohxxn.github.io/programmers/138/