'Programmers/Level 3' 카테고리의 글 목록 (3 Page)

#include <string>
#include <vector>
using namespace std;
 
long long dp[60010];
 
int solve(int n)
{
    if(n == 0)
    {
        return 1;
    }
        
    if(dp[n] != 0)
    {
        return dp[n];
    }
    
    if(n-2 >= 0)
    {
        dp[n] += (solve(n-2) % 1000000007);
    }
    
    if(n-1 >= 0)
    {
        dp[n] += (solve(n-1) % 1000000007);
    }
    
    return dp[n] % 1000000007;
}
 
int solution(int n) 
{
    int ans = solve(n);
    
    return ans;
}
Colored by Color Scripter
cs

저작자표시

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 가장 긴 팰린드롬 (C/C++) (★★) (0)	2020.03.07
[프로그래머스 3] 종이접기 (C/C++) (★) (0)	2020.03.06
[프로그래머스 3] 길찾기 게임 (C/C++) (★★) (0)	2020.03.05
[프로그래머스 3] 매칭 점수 (C/C++) (0)	2020.03.01
[프로그래머스 3] 순위 (C/C++) (★★) (0)	2020.02.05

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <stdlib.h>
using namespace std;
 
typedef struct node
{
    int x;
    int y;
    int num;
    struct node *left;
    struct node *right;
}node;
 
vector<node> newinfo;
node *root;
vector<int> pre;
vector<int> post;
 
bool cmp(node a, node b)
{
    if(a.y > b.y)
    {
        return true;
    }
    else if(a.y == b.y)
    {
        if(a.x < b.y)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}
 
void find_position_and_connect(node *now, int idx)
{        
    if(now == NULL)
    {
        return;
    }
        
    if(now->x < newinfo[idx].x)
    {
        if(now->right == NULL)
        {
            node *newNode = (node*)malloc(sizeof(node)*1);
            newNode[0] = {newinfo[idx].x, newinfo[idx].y, newinfo[idx].num, NULL, NULL};
            now->right = newNode;
            
            return;
        }
        else
        {
            find_position_and_connect(now->right, idx);   
        }
    }
    else
    {
        if(now->left == NULL)
        {
            node *newNode = (node*)malloc(sizeof(node)*1);
            newNode[0] = {newinfo[idx].x, newinfo[idx].y, newinfo[idx].num, NULL, NULL};
            now->left = newNode;
            
            return;
        }
        else
        {
            find_position_and_connect(now->left, idx);   
        }
    }
}
 
void preOrder(node *now)
{
    if(now == NULL)
    {
        return;
    }
    
    pre.push_back(now->num+1);
    preOrder(now->left);
    preOrder(now->right);
}
 
void postOrder(node *now)
{
    if(now == NULL)
    {
        return;
    }
    
    postOrder(now->left);
    postOrder(now->right);
    post.push_back(now->num+1);
}
 
vector<vector<int>> solution(vector<vector<int>> nodeinfo) 
{    
    vector<vector<int>> answer;
    
    for(int i = 0; i < nodeinfo.size(); i++)
    {
        newinfo.push_back({nodeinfo[i][0], nodeinfo[i][1], i, NULL, NULL}); // x, y, 노드번호
    }
    sort(newinfo.begin(), newinfo.end(), cmp);
    
    root = (node*)malloc(sizeof(node)*1);
    root[0] = {newinfo[0].x, newinfo[0].y, newinfo[0].num, NULL, NULL};
    
    for(int i = 1; i < newinfo.size(); i++)
    {
        find_position_and_connect(root, i);
    }
 
    preOrder(root);
    postOrder(root);
    
    answer.push_back(pre);
    answer.push_back(post);
    
    return answer;
}
Colored by Color Scripter
cs

저작자표시

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 종이접기 (C/C++) (★) (0)	2020.03.06
[프로그래머스 3] 2xN 타일링 (C/C++) (0)	2020.03.06
[프로그래머스 3] 매칭 점수 (C/C++) (0)	2020.03.01
[프로그래머스 3] 순위 (C/C++) (★★) (0)	2020.02.05
[프로그래머스 3] 가장 먼 노드 (C/C++) (0)	2020.02.05

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
void lower(string &a)
{
    for(int i = 0; i < a.size(); i++)
    {
        if('A' <= a[i] && a[i] <= 'Z')
        {
            a[i] = a[i]-'A'+'a';
        }
    }
}
 
int solution(string word, vector<string> pages) 
{
    int stdScore[25] = {0};
    double result[25] = {0};
    vector<string> my_page[25];
    vector<string> out_page[25];
    
    for(int i = 0; i < pages.size(); i++)
    {
        // 페이지, 찾는 단어 소문자 변환
        int idx = 0;
        lower(pages[i]);
        lower(word);
        
        // my_page
        idx = pages[i].find("<meta property=\"og:url\"", idx);
        idx = pages[i].find("https://", idx);
        
        string my_url = "";
        for(int j = idx; pages[i][j] != '"'; j++)
        {
            my_url += pages[i][j];
        }
        my_page[i].push_back(my_url);
        
        // out_page
        while(pages[i].find("<a href=", idx) != string::npos)
        {
            idx = pages[i].find("<a href=", idx);
            idx = pages[i].find("https://", idx);
            
            string link_url = "";
            for(int j = idx; pages[i][j] != '"'; j++)
            {
                link_url += pages[i][j];
            }       
            out_page[i].push_back(link_url);
        }   
        
        // 기본점수
        idx = 0;
        int wordCnt = 0;
        while(pages[i].find(word, idx) != string::npos)
        {
            bool notWord = false;
            idx = pages[i].find(word, idx);
    
            // 찾은 단어 바로 앞 확인
            if(0 <= idx-1 && idx-1 < pages[i].size() && 'a' <= pages[i][idx-1] && pages[i][idx-1] <= 'z')
            {
                notWord = true;
            }
            
            idx += word.size();
            
            // 찾은 단어 뒤 확인
            while(0 <= idx && idx < pages[i].size() && 'a' <= pages[i][idx] && pages[i][idx] <= 'z')
            {
                notWord = true;
                idx++;   
            }
            
            if(notWord == false)
            {
                wordCnt++;
            }
        }   
        stdScore[i] = wordCnt;
    }
    
    // 링크점수 + 매칭점수
    for(int i = 0; i < pages.size(); i++)
    {
        int linkCnt = 0;
        vector<int> link;
            
        for(int j = 0; j < pages.size(); j++)
        {
            if(i == j)
            {
                continue;
            }
            
            for(int k = 0; k < out_page[j].size(); k++)
            {
                if(my_page[i][0] == out_page[j][k])
                {
                    link.push_back(j);
                }
            }   
        }
        
        result[i] = stdScore[i];
        for(int j = 0; j < link.size(); j++)
        {
            if(stdScore[link[j]] == 0 || out_page[link[j]].size() == 0)
            {
                continue;    
            }
            
            double linkScore = (double)stdScore[link[j]] / out_page[link[j]].size();
            result[i] += linkScore;
        }
    }
    
    double Max = -1;
    int MaxIdx = -1;
    for(int i = 0; i < pages.size(); i++)
    {
        if(Max < result[i])
        {
            Max = result[i];
            MaxIdx = i;
        }
    }
    
    return MaxIdx;
}
Colored by Color Scripter
cs

저작자표시

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 2xN 타일링 (C/C++) (0)	2020.03.06
[프로그래머스 3] 길찾기 게임 (C/C++) (★★) (0)	2020.03.05
[프로그래머스 3] 순위 (C/C++) (★★) (0)	2020.02.05
[프로그래머스 3] 가장 먼 노드 (C/C++) (0)	2020.02.05
[프로그래머스 3] 입국 심사 (C/C++) (0)	2020.01.27

#include <string>
#include <vector>
#include <iostream>
using namespace std;
 
int graph[110][110];
int N;
int ans;
 
void floyd()
{
    for(int k = 1; k <= N; k++)
    {
        for(int i = 1; i <= N; i++)
        {
            for(int j = 1; j <= N; j++)
            {
                if(graph[i][k] == 1 && graph[k][j] == 1)
                {
                    graph[i][j] = 1;
                }
            }
        }
    }
}
 
int solution(int n, vector<vector<int>> results) 
{
    N = n;
    
    for(int i = 0; i < results.size(); i++)
    {
        graph[results[i][0]][results[i][1]] = 1;
    }
    
    floyd();
    
    for(int i = 1; i <= N; i++)
    {
        int cnt = 0;
        
        for(int j = 1; j <= N; j++)
        {
            if(graph[i][j] == 1 || graph[j][i] == 1)
            {
                cnt++;
            }
        }
        
        if(cnt == N-1)
        {
            ans++;
        }
    }
    
    return ans;
}
Colored by Color Scripter
cs

저작자표시

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 길찾기 게임 (C/C++) (★★) (0)	2020.03.05
[프로그래머스 3] 매칭 점수 (C/C++) (0)	2020.03.01
[프로그래머스 3] 가장 먼 노드 (C/C++) (0)	2020.02.05
[프로그래머스 3] 입국 심사 (C/C++) (0)	2020.01.27
[프로그래머스 3] 예산 (C/C++) (0)	2020.01.26

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;
 
vector<pair<int, int>> map[20010];
int d[20010];
 
void dijkstra(int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({0, start});
    d[start] = 0;
 
    while(!pq.empty())
    {
        int now = pq.top().second;
        int nowCost = pq.top().first;
        pq.pop();
        
        if(d[now] != nowCost)
        {
            continue;
        }
        
        for(int i = 0; i < map[now].size(); i++)
        {
            int next = map[now][i].first;
            int nextCost = map[now][i].second;
            
            if(d[next] > nowCost + nextCost)
            {
                d[next] = nowCost + nextCost;
                pq.push({d[next], next});
            }
        }
    }
}
 
int solution(int n, vector<vector<int>> edge) 
{
    for(int i = 1; i <= n; i++)
    {
        d[i] = 99999999;
    }
    
    for(int i = 0; i < edge.size(); i++)
    {
        map[edge[i][0]].push_back({edge[i][1], 1});
        map[edge[i][1]].push_back({edge[i][0], 1});
    }
    
    dijkstra(1);
    
    int Max = 0;
    for(int i = 1; i <= n; i++)
    {
        if(Max < d[i])
        {
            Max = d[i];
        }
    }
    
    int cnt = 0;
    for(int i = 1; i <= n; i++)
    {
        if(Max == d[i])
        {
            cnt++;
        }
    }
   
    return cnt;
}
Colored by Color Scripter
cs

저작자표시

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 매칭 점수 (C/C++) (0)	2020.03.01
[프로그래머스 3] 순위 (C/C++) (★★) (0)	2020.02.05
[프로그래머스 3] 입국 심사 (C/C++) (0)	2020.01.27
[프로그래머스 3] 예산 (C/C++) (0)	2020.01.26
[프로그래머스 3] 등굣길 (C/C++) (0)	2020.01.14

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
long long cal(vector<int> times, long long mid)
{
    long long peopleCnt = 0;
    
    for(int i = 0; i < times.size(); i++)
    {
        if(times[i] > mid)
        {
            break;
        }
        
        peopleCnt += mid / times[i];
    }
    
    return peopleCnt;
}
 
long long solution(int n, vector<int> times) 
{
    long long Min = 200000000000000;
    
    sort(times.begin(), times.end());
    
    long long left = 1;
    long long right = (long long)times[times.size()-1] * n;
    
    while(left <= right)
    {
        long long mid = (left + right) / 2;
        
        long long peopleCnt = cal(times, mid);
        
        if(peopleCnt >= n)
        {
            right = mid-1;
            
            if(mid < Min)
            {
                Min = mid;
            }
        }
        else if(peopleCnt < n)
        {
            left = mid+1;
        }
    }
    
    return Min;
}
Colored by Color Scripter
cs

저작자표시

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 순위 (C/C++) (★★) (0)	2020.02.05
[프로그래머스 3] 가장 먼 노드 (C/C++) (0)	2020.02.05
[프로그래머스 3] 예산 (C/C++) (0)	2020.01.26
[프로그래머스 3] 등굣길 (C/C++) (0)	2020.01.14
[프로그래머스 3] 타일 장식물 (C/C++) (0)	2020.01.11

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
long long cal(vector<int> budgets, int limit)
{
    long long sum = 0;
    
    for(int i = 0; i < budgets.size(); i++)
    {
        if(budgets[i] <= limit)
        {
            sum += budgets[i];
        }
        else
        {
            sum += limit;
        }   
    }
    
    return sum;
}
 
int solution(vector<int> budgets, int M) 
{
    int answer = 0;
    long long Max;
    long long MM = M;
    
    sort(budgets.begin(), budgets.end());
    
    int left = 1;
    int right = budgets[budgets.size()-1];
    
    long long sum = cal(budgets, right);
    if(sum <= MM)
    {
        return right;
    }
    
    while(left <= right)
    {
        int mid = (left+right)/2;
        
        long long sum = cal(budgets, mid);
        
        if(sum > MM)
        {
            right = mid-1;
        }
        else if(sum < MM)
        {
            left = mid+1;
            
            if(sum > Max)
            {
                Max = sum;
                answer = mid;
            }
        }
        else if(sum == MM)
        {
            answer = mid;
            break;
        }
    }
    
    return answer;
}
Colored by Color Scripter

cs

저작자표시

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 가장 먼 노드 (C/C++) (0)	2020.02.05
[프로그래머스 3] 입국 심사 (C/C++) (0)	2020.01.27
[프로그래머스 3] 등굣길 (C/C++) (0)	2020.01.14
[프로그래머스 3] 타일 장식물 (C/C++) (0)	2020.01.11
[프로그래머스 3] 정수 삼각형 (C/C++) (0)	2020.01.11

#include <string>
#include <vector>
using namespace std;
 
int solution(int m, int n, vector<vector<int>> puddles) 
{
    int dp[110][110] = {0}; // dp[n][m]
    
    // 세로 1로 표시
    for(int i = 1; i <= n; i++)
    {
        dp[i][1] = 1;
    }   
        
    // 가로 1로 표시
    for(int i = 1; i <= m; i++)
    {
        dp[1][i] = 1;
    }
    
    // 웅덩이 -1로 표시
    for(int i = 0; i < puddles.size(); i++)
    {
        dp[puddles[i][1]][puddles[i][0]] = -1;
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            // 집
            if(i == 1 && j == 1)
            {
                continue;
            }
            
            // 웅덩이
            if(dp[i][j] == -1)
            {
                dp[i][j] = 0;
            }
            else
            {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007;  
            }
        }
    }
    
    return dp[n][m];
}
Colored by Color Scripter
cs

저작자표시

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 입국 심사 (C/C++) (0)	2020.01.27
[프로그래머스 3] 예산 (C/C++) (0)	2020.01.26
[프로그래머스 3] 타일 장식물 (C/C++) (0)	2020.01.11
[프로그래머스 3] 정수 삼각형 (C/C++) (0)	2020.01.11
[프로그래머스 3] 저울 (C/C++) (★) (0)	2020.01.11

코딩 잘하면 학교에서 인싸되나요?

Programmers/Level 3

[프로그래머스 3] 2xN 타일링 (C/C++)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 길찾기 게임 (C/C++) (★★)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 매칭 점수 (C/C++)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 순위 (C/C++) (★★)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 가장 먼 노드 (C/C++)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 입국 심사 (C/C++)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 예산 (C/C++)

'Programmers > Level 3' 카테고리의 다른 글

[프로그래머스 3] 등굣길 (C/C++)

'Programmers > Level 3' 카테고리의 다른 글

+ Recent posts

티스토리툴바