개발자 김수진

[문제]

programmers.co.kr/learn/courses/30/lessons/64063

[풀이]

Union-Find 알고리즘을 사용해서 풀었다.

(Union-Find 알고리즘 : https://tnwlswkd.tistory.com/33 )

고객이 원하는 방이 아직 배정받지 않은 방이라면 해당 고객에게 배정해주고 map에 다음 칸의 방으로 초기화한다.

이미 배정받은 방이라면 Find 함수를 통해 해당 방을 기준으로 다음 방에서 비어있는 방을 찾아 배정해준다.

또한 배열이 아닌 맵을 사용한 이유는 k의 범위가 1 이상 10^12 이하이므로 배열을 사용하면  10^12 크기의 배열을 선언하여 메모리 부족이 발생하게 된다. 

항상 Union-Find 알고리즘 구현할 때, else 부분에서 초기화 해주는걸 깜박한다.

[코드]

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

using namespace std;

map <long long,long long > m;

long long Find(long long num)
{
    if(m[num]==0)
    {
        m[num]=num+1;
        return num;
    }
    else    return m[num]= Find(m[num]);
    
}

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 room= room_number[i];
        if(m[room] == 0)
        {
            answer.push_back(room);
            m[room]=room+1;
        }
        else
        {
            long long res = Find(room);
            answer.push_back(res);
        }
    }
    return answer;
}

[문제]

www.acmicpc.net/problem/1806

[풀이]

연속된 구간의 부분합을 구하는 문제이므로 투포인터 알고리즘을 사용해서 풀었다.

(투포인터 알고리즘 : https://tnwlswkd.tistory.com/44 )

start부터 end까지의 부분합이 S 이상인 경우 구간의 길이를 구하고 start를 한 칸 뒤로 움직여서 구간의 길이를 좁힌다.

이 때 start와 end가 같다면 최소 구간이 되므로 1을 출력하고 끝낸다.

부분합이 S 미만인 경우 end를 한 칸 뒤로 움직여서 구간의 길이를 넓힌다.

[코드]

시간 : 32ms

#include <iostream>
#include <vector>
#define MAX 100000

using namespace std;

int N,S;
int res = 1e9;
int sequence[MAX] = { 0, };

int main(void)
{
	cin >> N >> S;
	for (int i = 0; i < N; i++)		cin >> sequence[i];

	int start = 0;
	int end = 0;
	int total = sequence[0];

	while (end < N) {
		if (total < S)
		{
			end++;
			total += sequence[end];
		}
		else {
			if (start == end)
			{
				cout << "1";
				return 0;
			}
			int len = end - start + 1;
			if (len < res)		res = len;
			total -= sequence[start];
			start++;
		}
	}
	if (res == 1e9)	cout << "0";
	else    cout << res;
	return 0;
}

[개념]

이분탐색이란 탐색기법중 하나로 중간값을 기준으로 탐색 범위를 절반씩 줄여가며  탐색한다.

따라서 처음부터 끝까지 모두 탐색하는 기법은 worst case의 경우 시간복잡도가 (O(N))이다.

하지만 이분탐색의 경우 탐색범위를 절반씩 줄여나가기 때문에 O(logN)으로 완전탐색보다 빠르다.

1. 탐색하고자 하는 배열은 이미 정렬이 되어있다.

2. left, right 값을 통해 중간값인 mid 값을 구한다.

3-1. 찾고자하는 값이 mid 위치에 존재하는 값보다 클 경우 , left를 mid 뒤로 옮긴다.

3-2. 찾고자하는 값이 mid 위치에 존재하는 값보다 작을 경우 , right를 mid 앞으로 옮긴다.

4. 다시 위의 과정을 left가 right 값보다 커질 때까지 반복한다. 

- 예시

배열의 총 길이는 8이므로 

left =0 , right= 7이되고 mid=3가 된다.

mid에 존재하는 값이 찾고자 하는 값인 7보다 크므로 right를 mid-1로 update 한다.

이 때 , mid에 존재하는 값보다 찾고자 하는 값인 7이 더 뒤에 있으므로 left를 mid+1로 update 한다.

마지막으로 left,right,mid 모두 같은 위치에 존재하고 드디어 찾고자 하는 7을 찾을 수 있게 되었다.

[코드]

int main(void)
{
    int arr[8]  = {1,3,7,8,9,15,17,21};
    
    int target = 7;
    int left = 0;
    int right = 7;
    int mid;
    
    while(left <= right)
    {
        mid = (left+right)/2;
        if(arr[mid] < target )  left = mid+1;
        else if( arr[mid] > target) right = mid-1;
        else    return mid;
    }
}

[문제]

programmers.co.kr/learn/courses/30/lessons/64062

[풀이]

반복문을 사용해 한 명씩 보내면서 구할 수 있다.

하지만 stones 배열의 길이가 200,000이므로 시간초과가 발생하여 효율성 부분에서 틀린다.

따라서 이분 탐색을 사용하여 찾아가는 방식으로 하였다.

(이분탐색 정리 : https://tnwlswkd.tistory.com/112 )

stones 배열에서 left는 1, 가장 큰 값으로 right를 초기화 한다.

중간 값을 구해가면서 left, right 값을 조절하여 건널 수 있는 학생수의 최댓값을 찾는다.

mid를 기준으로 mid 값보다 stones의 값이 작다면 mid만큼의 학생이 건너지 못하는 것이므로 cnt+=1을 해준다. 또한 이러한 경우가 연속으로 k번 이상이라면 mid 만큼의 학생이 건너지 못하므로 false를 return하여 mid 값을 조절한다.

이러한 방식으로 left>right일 때까지 반복하여 이분탐색을 통해 최댓값을 찾을 수 있다.

[코드]

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

using namespace std;
bool binary_search(vector<int> stones, int k, int mid)
{
    int cnt =0;
    for(int i=0;i<stones.size();i++)
    {
        if(stones[i] < mid )    cnt++;
        else    cnt=0;
        
        if(cnt >= k)    return false;
    }
    return true;
}

int solution(vector<int> stones, int k) {
    int answer = 0;
    int left = 1;
    int right = *max_element(stones.begin(),stones.end());
    
    while(left <= right){
        int mid = (left+right)/2;
        if(binary_search(stones,k,mid)){
            left = mid +1;
            if(answer < mid)    answer = mid;
        }
        else{
            right = mid -1;
        }     
    }
    return answer;
}

[문제]

programmers.co.kr/learn/courses/30/lessons/64064

[풀이]

각각의 banned_id마다 가능한 user_id의 index를 vector에 push

DFS를 통해 banned_id마다 제재 id를 구한다.

banned_id에 대해 user ID를 모두 선택했을 경우, 선택된 user ID의 index로 문자열을 만들어 set에 insert해준다.

set을 통해 중복된 경우를 제거하여 모든 경우의 수를 구할 수 있다.

[코드]

#include <string>
#include <vector>
#include <set>
#define MAX 8

using namespace std;

vector<int> v[MAX];
set<string> s;
bool visited[MAX]={0,};
int bsize= 0;
int usize=0;
int res= 0;

void DFS(int cnt,int idx)
{
    if(cnt == bsize)
    {
        string tmp="";
        for(int i=0;i<usize;i++){
            if(visited[i])  tmp+=to_string(i);
        }
        s.insert(tmp);
        return ;
    }
    for(int i=0;i<v[idx].size();i++)
    {
        int num = v[idx][i];
        if(visited[num])    continue;
        visited[num]=true;
        DFS(cnt+1, idx+1);
        visited[num] = false;
    }
}

int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
    bsize= banned_id.size();
    usize= user_id.size();
    for(int i=0;i<bsize;i++)
    {
        int len1= banned_id[i].size();
        for(int j=0;j<user_id.size();j++)
        {
            int len2 = user_id[j].size();
            if(len1 != len2)    continue;
            bool check = true;
            for(int k=0;k<len1;k++){
                if(banned_id[i][k] == '*')  continue;
                if(banned_id[i][k] != user_id[j][k]){
                    check = false;
                    break;
                }
            }
            if(check)   v[i].push_back(j);            
        }   
    }

    DFS(0,0);
    answer = s.size();
    return answer;
}

[문제]

programmers.co.kr/learn/courses/30/lessons/64065

[풀이]

앞쪽에 위치한 원소일수록 집합에 가장 많이 포함되어 있어

따라서 원소가 나온 내림차순 횟수를 정렬하여 

가장 많이 나타난 원소부터 answer에 insert

[코드]

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

using namespace std;

bool cmp(pair<int,int> a, pair<int,int> b) {
	if (a.second > b.second) return true;
	return false;
}
vector<int> solution(string s) {
    vector<int> answer;
    map<int,int> m;
        
    string num = "";

    for(int i=1;i<s.size()-1;i++)
    {
        if(s[i] == ',' || s[i] == '}' || s[i]=='{')
        {
            if(num=="") continue;
            m[stoi(num)]++;
            num="";
        }
        else    num+=s[i];
    }
    vector<pair<int,int>> v( m.begin(), m.end() );
    sort(v.begin(),v.end(),cmp);
    for(int i=0;i<v.size();i++) answer.push_back(v[i].first);
    return answer;
}

[문제]

programmers.co.kr/learn/courses/30/lessons/67257

[풀이]

next_permutation 함수를 사용해 완전탐색으로 풀었다.

먼저 vector에 숫자와 연산자를 구분해서 담아줬다.

그리고 oper_list를 next_permutation 함수를 사용해 연산자의 우선순위를 바꿔가며 모든 경우의 수를 구했다.

우선순위를 바꿔가면서 연산을 하고 , 계산이 끝날 때마다 연산 결과를 비교해가면서 가장 큰 값을 찾아내는 방식으로 풀었다.

 next_permutation 함수 : 순열을 구한다.

예를 들어 집합 { '+' , '-' , '*' }의 모든 순열을 구하면 아래와 같이 총 6가지가 나오게 된다.

{ '+' , '-' , '*'}

{ '+' , '*' , '-'}

{ '-', '+' , '*' }

{ '-' , '*' , '+'}

{ '*' ,'+' , '-' }

{ '*'  , '-' , '+'}

[코드]

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

using namespace std;

long long calc(long long a,long long b, char op)
{
    if(op == '-')   return a-b;
    else if(op == '+')  return a+b;
    else    return a*b;
}

long long solution(string expression) {
    long long answer = 0;
    vector <char> oper_list =  { '*', '+', '-' };
    vector <long long> number;
    vector <char> oper;
    string num = "";
    

    for(int i=0;i<expression.size();i++)
    {
        if(expression[i] == '+' || expression[i] =='*' || expression[i] == '-')
        {
            oper.push_back(expression[i]);
            number.push_back(atoi(num.c_str()));
            num="";
        }
        else    num+= expression[i];  
    }
    number.push_back(atoi(num.c_str()));
    long long _max =0;
    do{
        vector <char> tmp_oper = oper;
        vector <long long> tmp_num = number;
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<tmp_oper.size();j++)
            {
                if(tmp_oper[j] == oper_list[i])
                {
                    tmp_num[j] = calc(tmp_num[j],tmp_num[j+1],oper_list[i]);
                    tmp_num.erase(tmp_num.begin()+j+1);
                    tmp_oper.erase(tmp_oper.begin()+j);
                    j--;
                }
            }
        } 
        if(_max < abs(tmp_num[0]))   _max = abs(tmp_num[0]);
    }while(next_permutation(oper_list.begin(),oper_list.end()));
    answer = _max;
    return answer;
}

[문제]

programmers.co.kr/learn/courses/30/lessons/67256

[풀이]

1,4,7을 누를경우 왼손

3,6,9를 누를 경우 오른손

나머지는 현재 왼손, 오른손의 위치를 기준으로 가까운 손으로 누르도록 구현

만약 거리가 같다면 왼손잡이,오른손잡이인지 확인하고 이에 맞게 누르도록

[코드]

#include <string>
#include <vector>

using namespace std;

struct pos{
    int x,y;
};

pos left = {3,0};
pos right = {3,2};

string solution(vector<int> numbers, string hand) {
    string answer = "";
    
    for(int i=0;i<numbers.size();i++)
    {
        int num = numbers[i];
        
        if(num == 1 || num == 4 || num == 7)
        {
            answer += "L";
            left = {num/3,0};
        }
        else if(num == 3 || num == 6 || num == 9)
        {
            answer += "R";
            right = { num/3-1 , 2};
        }
        else
        {
            int x = num/3;
            int y = 1;
            if(num == 0)    x = 3;
            
            int ldis = abs(x-left.x) + abs(y-left.y);
            int rdis = abs(x-right.x) + abs(y-right.y);
            
            if(rdis < ldis)
            {
                answer += "R";
                right = {x,y};
            }
            else if(rdis > ldis )
            {
                answer += "L";
                left = {x,y};
            }    
            else
            {
                if(hand.compare("right") == 0)
                {
                    answer += "R";
                    right = {x,y};
                }
                else
                {
                    answer += "L";
                    left = {x,y};
                }
            }
        }
    }
    return answer;
}