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

 

코딩테스트 연습 - 가장 큰 수

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 ��

programmers.co.kr

 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
 
bool cmp(const string& a, const string& b) {
    return a + b > b + a;
}
 
string solution(vector<int> numbers) {
    string answer = "";
 
    vector<string> ns;
    for (int n : numbers) ns.push_back(to_string(n));
    sort(ns.begin(), ns.end(), cmp);
    for (auto s : ns) answer += s;
    if (answer[0] == '0') answer = "0";
    return answer;
}
cs

 

 

 

 

 

https://github.com/has2/Algorithm/blob/master/programmers/level2/%ED%81%B0%20%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp

'Problem-Solving > Programmers' 카테고리의 다른 글

[프로그래머스][level2] 행렬 테두리 회전하기 (C++)  (0) 2021.08.06
[프로그래머스][level2] 거리두기 확인하기 (C++)  (0) 2021.08.06
[프로그래머스] Level2 - 큰 수 만들기(C++)  (0) 2020.07.14
[프로그래머스] Level2 - 조이스틱 (C++)  (0) 2020.07.14
[프로그래머스] Level2 - 더 맵게 (C++)  (0) 2020.07.07

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

 

코딩테스트 연습 - 큰 수 만들기

 

programmers.co.kr

[풀이] Greedy

 

Upperbound를 이용해서 고를 수 있는 범위 내에서 9~0까지 for문을 돌면서 가장 먼저 선택할 수 있는

값을 하나씩 고르면 된다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
 
string solution(string number, int k) {
    string answer = "";
    vector<int> a[10];
    for (int j = 0; j < number.size(); j++) {
        a[number[j] - '0'].push_back(j);
    }
    
    int cur = -1;
    for (int i = k; i < number.size(); i++) {
        for (int j = 9; j >= 0; j--) {
            if (a[j].empty()) continue;
            if (answer == "" && j == 0) continue;
            auto ub = upper_bound(a[j].begin(), a[j].end(), cur);
            if (ub == a[j].end()) continue;
 
            int m = ub - a[j].begin();
            if (a[j][m] <= i) {
                answer.push_back(j + '0');
                cur = a[j][m];
                break;
            }
        }
    }
    return answer;
}
 cs

 

https://github.com/has2/Algorithm/blob/master/programmers/level2/%ED%81%B0%20%EC%88%98%20%EB%A7%8C%EB%93%A4%EA%B8%B0.cpp

'Problem-Solving > Programmers' 카테고리의 다른 글

[프로그래머스][level2] 거리두기 확인하기 (C++)  (0) 2021.08.06
[프로그래머스] Level2 - 가장 큰 수 (C++)  (0) 2020.07.28
[프로그래머스] Level2 - 조이스틱 (C++)  (0) 2020.07.14
[프로그래머스] Level2 - 더 맵게 (C++)  (0) 2020.07.07
[프로그래머스] Level2 - 괄호 변환 (C++)  (0) 2020.06.28

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

 

코딩테스트 연습 - 조이스틱

조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다

programmers.co.kr

[풀이] Greedy

 

가장 효율적으로 알파벳을 변경하는 방법은 이동시 가장 가까운 곳으로 이동해서 변경해주는 것이다.

어차피 변경해야할 모든 알파벳을 방문해야 하기 때문이다.

 

어떤 알파벳을 방문할 때 <-,->를 이용하는 두가지 방법 중 min값이 이동거리이다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <string>
#include <vector>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
int solution(string name) {
    int answer = 0;
 
    string curName(name.size(), 'A');
    int cur = 0;
 
    while (name != curName) {
 
        int near = -1;
        int minDiff = 30;
        for (int i = 0; i < name.size(); i++) {
            if (name[i] != curName[i]) {
                int diff = abs(cur - i);
                diff = min(diff, (int)name.size() - diff);
                if (minDiff > diff) {
                    near = i;
                    minDiff = diff;
                }
            }
        }
        cur = near;
        curName[cur] = name[cur];
        answer += minDiff;
        
        int k = name[cur] - 'A';
        answer += min(26 - k, k);
 
        //cout << "cur : " << cur << ", minDiff : " << minDiff << ", k : " << k << ", len -k : " << 26-k << endl;
    }
 
    return answer;
}
cs
https://github.com/has2/Algorithm/blob/master/programmers/level2/%EC%A1%B0%EC%9D%B4%EC%8A%A4%ED%8B%B1.cpp

'Problem-Solving > Programmers' 카테고리의 다른 글

[프로그래머스] Level2 - 가장 큰 수 (C++)  (0) 2020.07.28
[프로그래머스] Level2 - 큰 수 만들기(C++)  (0) 2020.07.14
[프로그래머스] Level2 - 더 맵게 (C++)  (0) 2020.07.07
[프로그래머스] Level2 - 괄호 변환 (C++)  (0) 2020.06.28
[프로그래머스] Level2 - 카카오 프렌즈 컬러링북  (0) 2020.06.21

https://leetcode.com/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/

 

Maximum Nesting Depth of Two Valid Parentheses Strings - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

[풀이] Greedy

 

문제해석이 어려운 문제.

결론적으로 어떤 VPS를 A,B 두 VPS로 나누는 문제. 이 때 depth(A,B)가 최소가 되도록 나누어야 한다.

처음엔 당연히 연속되는 괄호들로 나눠야 한다고 생각했는데

예제를 보니 ()(())() 와 같이 나눠도 된다.

depth를 가장 작게 하려면 겹치는 괄호를 최소한으로 만들어야 한다.그러려면 stack에 여는 괄호를 넣을 때 0,1,0,1 이런식으로 차례대로 넣어주면 된다.닫는 괄호는 여는 괄호와 같은 그룹에 들어가야 하므로 top과 같은 값으로 설정해주면 된다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stack>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        vector<int> ans(seq.size());
        stack<int> a;
        for (int i = 0; i < seq.size(); i++) {
            char c = seq[i];
 
            if (c == '(') {
                if (a.empty()) a.push(0);
                else a.push(1 - a.top());
                ans[i] = a.top();
            }
            else {
                ans[i] = a.top();
                a.pop();
            }
        }
        return ans;
    }
};
cs
https://github.com/has2/Algorithm/blob/master/leetcode/1111.%20Maximum%20Nesting%20Depth%20of%20Two%20Valid%20Parentheses%20Strings.cpp

 

 

 

 

 

 

'Problem-Solving > LeetCode' 카테고리의 다른 글

[Leetcode] 419. Battleships in a Board  (0) 2020.07.28
[Leetcode] 1387. Sort Integers by The Power Value (C++)  (0) 2020.07.07
[Leetcode] 1448. Count Good Nodes in Binary Tree (C++)  (0) 2020.06.28
[Leetcode] 1476. Subrectangle Queries  (0) 2020.06.21

https://leetcode.com/problems/sort-integers-by-the-power-value/

 

Sort Integers by The Power Value - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

[풀이] DP

홀수인경우 kx3 + 1 , 짝수인경우 k/2를 해서 1이 될때까지 만드는 문제

최대 1000개의 값들을 계산해야 하기 때문에 시간복잡도 예상이 안되서 

DP로 풀었는데 완전탐색 해도 풀린다고 한다.

dp 배열을 처음에 4000 크기정도만 해줘도 될거라고 생각했는데 계속 런타임 에러가 나서

500000까지 바꿔주었다. 1000 이하의 k 값을 1로 만드는 과정에서 k가 상당히 커질수도 있는 것 같다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
  
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
 
    int dp[500000];
 
    int sol(int k) {
 
        if (k == 1) return 0;
 
        int& ret = dp[k];
        if (ret != 0) return ret;
 
        if (k % 2) ret = 1 + sol(3 * k + 1);
        else ret = 1 + sol(k/2);
        
        return ret;
    }
 
    int getKth(int lo, int hi, int k) {
        vector<pair<int,int>> a;
        for (int i = lo; i <= hi; i++) a.push_back(make_pair(sol(i),i));
        
        sort(a.begin(), a.end());
    
        return a[k-1].second;
    }
};
 cs

 

https://github.com/has2/Algorithm/blob/master/leetcode/1387.cpp

'Problem-Solving > LeetCode' 카테고리의 다른 글

[Leetcode] 419. Battleships in a Board  (0) 2020.07.28
[Leetcode] 1111. Maximum Nesting Depth of Two Valid Parentheses Strings (C++)  (0) 2020.07.14
[Leetcode] 1448. Count Good Nodes in Binary Tree (C++)  (0) 2020.06.28
[Leetcode] 1476. Subrectangle Queries  (0) 2020.06.21

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

 

코딩테스트 연습 - 더 맵게

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같��

programmers.co.kr

[풀이] 우선순위 queue

 

시간복잡도 : O(nlgn)

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <cstdio>
#include <queue>
#include <vector>
 
using namespace std;
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
 
    priority_queue<int> pq;
    for (int& t : scoville) pq.push(-t);
    
    while (!pq.empty()) {
 
        if (-pq.top() >= K) return answer;
        if (pq.size() <= 1) return -1;
 
        int a = -pq.top(); pq.pop();
        a += -2 * pq.top(); pq.pop();
 
        pq.push(-a);
 
        answer++;
    }
    return answer;
}
cs
https://github.com/has2/Algorithm/blob/master/programmers/level2/%EB%8D%94%20%EB%A7%B5%EA%B2%8C.cpp

'Problem-Solving > Programmers' 카테고리의 다른 글

[프로그래머스] Level2 - 큰 수 만들기(C++)  (0) 2020.07.14
[프로그래머스] Level2 - 조이스틱 (C++)  (0) 2020.07.14
[프로그래머스] Level2 - 괄호 변환 (C++)  (0) 2020.06.28
[프로그래머스] Level2 - 카카오 프렌즈 컬러링북  (0) 2020.06.21
[프로그래머스] Level2 - 문자열 압축  (0) 2020.06.12

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

 

2143번: 두 배열의 합

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다

www.acmicpc.net

[풀이]

 

2632번 피자판매와 비슷한 문제인데 숫자 범위가 커져서 구간합의 개수를 배열에 저장할 수가 없다.

그래서 맵을 사용해서 저장하였다. 그 외에는 2632번과 동일하다.

 

주의할 점은 결과값을 int형에 저장하면 72%에서 오답이 나온다.

T(-1,000,000,000 ≤ T ≤ 1,000,000,000)이고 각 원소의 절댓값이 1000000 이하이기 때문에 합을 구하는

과정은 int형 안에 다 들어오게 된다.

T와 구간합의 범위에만 신경쓰다보니 경우의 수가 int 범위를 넘어갈 수 있다는 것을 놓쳤다.

1<=n<=1000, 1<=n<=1000이므로 최대 1000*1000*1000*1000의 경우의 수가 나올 수 있다.

(가장 간단하게 n,m이 1000, 모든 원소가 0, T가 0인 경우..)

 

경우의수 나오는 문제는 특히 자료형에 주의

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <map>
 
using namespace std;
int t, n, m, A[1000], B[1000];
long long ret;
int main() {
 
    scanf("%d%d", &t,&n);
    for (int i = 0; i < n; i++) scanf("%d", &A[i]);
    scanf("%d", &m);
    for (int i = 0; i < m; i++) scanf("%d", &B[i]);
    map<long long, long long> aMap;
 
    for (int i = 0; i < n; i++) {
        long long sum = 0;
        for (int j = i; j < n; j++) {
            sum += A[j];
            aMap[sum]++;
        }
    }
 
    for (int i = 0; i < m; i++) {
        long long sum = 0;
        for (int j = i; j < m; j++) {
            sum += B[j];
            ret += aMap[t - sum];
        }
    }
 
    printf("%lld", ret);
}
cs
https://github.com/has2/Algorithm/blob/master/boj/%EC%95%84%EB%AC%B4%EA%B1%B0%EB%82%98/2143.cpp

 

 

'Problem-Solving > BOJ' 카테고리의 다른 글

[BOJ/백준][Gold4] 10830 : 행렬 제곱(C++)  (0) 2020.12.12
[BOJ/백준][Gold4] 1403 : 거짓말(C++)  (0) 2020.12.12
[BOJ/백준][Gold4] 1022 : 소용돌이 예쁘게 출력하기 (C++)  (0) 2020.12.12
[BOJ/백준] 2624: 동전 바꿔주기 (C++)  (0) 2020.07.28
[BOJ/백준] 2632 : 피자판매 (C++)  (0) 2020.06.30

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

 

2632번: 피자판매

첫 번째 줄에는 손님이 구매하고자 하는 피자크기를 나타내는 2,000,000 이하의 자연수가 주어진다. 두 번째 줄에는 A, B 피자의 피자조각의 개수를 나타내 는 정수 m, n 이 차례로 주어진다 ( 3≤m, n�

www.acmicpc.net

[풀이] 완전탐색,부분합

 

1. n,m 제한이 1000이므로 모든 연속된 구간의 합 sum을 계산한다.

2. sum이 어떤 구간에 있는지는 중요하지 않고 몇개나 나올 수 있는지가 중요하므로

   Acnt,Bcnt 배열을 각각 만들에 sum이라는 값이 몇번 나올 수 있는지를 저장한다.

 

3. 1,2 과정은 피자 A와 B에 대해 중복되는 연산이므로 func 함수를 만들어서 중복코드를 줄인다.

4. func에서 sum을 구할 때 i를 구간의 크기로 잡는 피자 조각이 n개라면 1에서 n까지 돌아야 한다.

   j는 시작 index로 정한다. 최초 index 0부터 시작하는 i 구간만큼의 sum을 구한다.

   그 뒤의 for문은 j를 옮겨가면서 앞에는 빼주고 뒤에는 더해주는 과정이다.

   i가 최대 크기인 경우엔 이 과정은 break.

 

5. A,B 한개의 피자에서만 조각을 모두 가져올 수도 있으므로 func에서 sum을 구하는 도중에 답을 더해준다. 

 

6. Acnt,Bcnt를 모두 구했으면 곱연산으로 경우의 수를 구한다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <cstdio>
 
int k,n,m,A[1000], B[1000],Acnt[2000001], Bcnt[2000001],ret;
 
void func(int p, int arr[], int arrCnt[]) {
    for (int i = 1; i <= p; i++) {
        int sum = 0;
        for (int j = 0; j < i; j++) sum += arr[j];
        arrCnt[sum]++;
        if (sum == k) ret++;
        
        if (i == p) break;
        for (int j = 1; j < p; j++) {
            sum -= arr[j - 1];
            sum += arr[(j + i - 1) % p];
            arrCnt[sum]++;
            if (sum == k) ret++;
        }
    }
}
 
int main() {
    scanf("%d%d%d", &k, &n, &m);
    for (int i = 0; i < n; i++) scanf("%d", &A[i]);
    for (int i = 0; i < m; i++) scanf("%d", &B[i]);
 
    func(n, A, Acnt);
    func(m, B, Bcnt);
 
    for (int i = 1; i < k; i++) {
        int j = k - i;
        ret += Acnt[i] * Bcnt[j];
    }
    printf("%d", ret);
}
cs

https://github.com/has2/Algorithm/blob/master/boj/%EC%95%84%EB%AC%B4%EA%B1%B0%EB%82%98/2632.cpp

'Problem-Solving > BOJ' 카테고리의 다른 글

[BOJ/백준][Gold4] 10830 : 행렬 제곱(C++)  (0) 2020.12.12
[BOJ/백준][Gold4] 1403 : 거짓말(C++)  (0) 2020.12.12
[BOJ/백준][Gold4] 1022 : 소용돌이 예쁘게 출력하기 (C++)  (0) 2020.12.12
[BOJ/백준] 2624: 동전 바꿔주기 (C++)  (0) 2020.07.28
[BOJ/백준] 2143: 두 배열의 합(C++)  (0) 2020.07.05

+ Recent posts

티스토리툴바