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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

아래 카카오 테크 블로그에서도 해설을 볼 수 있다. 

https://tech.kakao.com/2019/10/02/kakao-blind-recruitment-2020-round1/

 

2020 신입 개발자 블라인드 채용 1차 코딩 테스트 문제 해설

올해에도 2020이라는 멋진 숫자와 함께, 카카오의 신입 개발자 채용을 시작했습니다! 그 여정 중 첫 단계로 1차 코딩 테스트가 지난 9월 7일 토요일 오후 2시부터 오후 7시까지 5시간 동안 진행됐는데요. 저희 준비위원들도 설렘과 긴장 속에 원활한 진행을 위해 노력했고, 무사히 1차 테스트를 마칠 수 있었습니다. 테스트에는 총 7문제가 출제됐고, 응시자는 5시간 이내에 순서와 상관없이 문제를 해결해야 했습니다. 문제의 배치는 작년과 마찬가지로 쉬운 난이

tech.kakao.com

이 문제는 효율성 테스트 점수가 있는 문제로 문자열을 하나하나 다 검사하면 효율성 테스트를 통과할 수 없다.

트라이 자료구조나 이분 탐색으로 효율성 테스트를 통과할 수 있는데 나는 이분 탐색으로 풀었다.

 

먼저 이분 탐색을 하기 위해서는 가사에 사용된 모든 단어들이 담긴 words를 정렬해줘야 하는데 정렬 기준이 되는 비교 함수를 만들어줘야 한다. 비교 함수는 단어의 길이로 먼저 오름차순 정렬하고 길이가 같다면 사전 순으로 정렬해준다.

 

["frodo", "front", "frost", "frozen", "frame", "kakao"]

문제의 예제로 예를 들면 위의 words 배열은 아래와 같이 될 것이다.

["frame", "frodo", "front", "frost", "kakao", "frozen"]

 

그리고 "????o"와 같이 ?가 접두사로 주어지는 경우에는 문자열의 뒤쪽부터 검사를 해줘야 하므로 words의 각 문자열을 뒤집은 배열 rwords를 만들어서 위와 마찬가지로 단어 길이, 사전 순 순서로 정렬해준다. 그러면 rwords는 아래와 같이 될 것이다.

["emarf", "oakak", "odorf", "tnorf", "tsorf", "nezorf"]

 

 

 

 

words와 rwords 모두 정렬을 해줬다면 이제 각 쿼리에 대해서 쿼리의 0번째 문자가 '?'인지 아닌지에 따라 나눠서 구현한다.

 

쿼리의 0번째 문자가 '?'라면

'?'가 접두사에 있는 경우이므로 문자열을 뒤집어준 배열인 rwords에서 탐색해야 한다. 쿼리 역시 마찬가지로 뒤집어준다. 문제 예제의 "????o" 같은 경우에는 "o????"이 될 것이다.

그러면 이제 "????"의 위치에 각각 "aaaa"와 "zzzz"를 넣고 lower_boud와 upper_bound를 사용해서 이분 탐색을 해준다. 이때도 비교 함수를 기준으로 탐색하도록 정렬할 때 사용한 비교 함수를 함께 넣어줘야 한다.

 

(참고로 lower_bound는 찾으려는 key값 이상의 값이 처음 나타나는 위치를 반환하고 upper_bound는 찾으려는 key값을 초과하는 값이 처음 나타나는 위치를 이분 탐색으로 반환한다.)

 

각 가사 단어는 오직 알파벳 소문자로만 구성되어 있다고 문제 조건에 나와있기 때문에 사전 순으로 가장 작은 값인 a와

가장 큰 값인 z로 채워 해당 범위의 최솟값과 최댓값을 만들어주는 것이다. ozzzz보다 큰 값이 처음 나타나는 위치에서 oaaaa 이상의 값이 처음 나타나는 곳의 위치를 빼주면 "o????"에 해당하는 문자열들의 개수를 구할 수 있다.

 

upperbound는 3번 위치인 tnorf가 되고 lowerbound값은 1번 위치인 oakak가 되므로 3-1을 해주면 2개인 것을 구할 수 있다.

["emarf", "oakak", "odorf", "tnorf", "tsorf", "nezorf"]

 

 

쿼리의 0번째 문자가 '?'가 아니라면

'?'가 접미사에 있는 경우이므로 가사의 앞부분을 검사하면 되므로 words배열에서 탐색한다.

탐색하는 방법은 위와 마찬가지로 "??"부분에 "aa"와 "zz"를 넣은 경우에 대해 각각 lower_bound와 upper_bound를 구해서 빼주면 된다.

예를 들어, 쿼리가 "fro??"라고 했을 때 "froaa"의 lower_bound값을 구하면 1번째 위치가 나오고 "frozz"의 upper_bound값을 구하면 4번째 위치가 나온다. 그러면 4 - 1을 해면 3이 나와서 아래 표시된 3가지 문자열이 "fro??"에 해당하는 문자열들이다.

["frame", "frodo", "front", "frost", "kakao", "frozen"]

 

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
 
//길이로 먼저 정렬하고 길이가 같다면 사전순으로 정렬
bool comp(string a, string b) {
    if (a.length() < b.length())
        return true;
    else if (a.length() == b.length())
        if (a < b) return true;
    return false;
}
 
 
vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;
 
    //rwords 벡터에 단어를 뒤집어서 저장
    vector<string> rwords = words;
    int size = rwords.size();
    for (int i = 0; i < size; i++) reverse(rwords[i].begin(), rwords[i].end());
 
 
    //comp 기준 정렬
    sort(words.begin(), words.end(), comp);
    sort(rwords.begin(), rwords.end(), comp);
 
 
    int len, lo, hi;
    int idx;
    for (string query : queries) {
        len = query.length();
        
        if (query[0] == '?') {
            //?가 접두사에 있는 경우
            reverse(query.begin(), query.end()); //키워드도 뒤집어준다.
            idx = query.find_first_of('?');
 
            for (int i = idx; i < len; i++) query[i] = 'a';
            lo = lower_bound(rwords.begin(), rwords.end(), query, comp) - rwords.begin();
 
            for (int i = idx; i < len; i++) query[i] = 'z';
            hi = upper_bound(rwords.begin(), rwords.end(), query, comp) - rwords.begin();
        }
        else {
            //?가 접미사에 있는 경우
            idx = query.find_first_of('?');
 
            for (int i = idx; i < len; i++) query[i] = 'a';
            lo = lower_bound(words.begin(), words.end(), query, comp) - words.begin();
 
            for (int i = idx; i < len; i++) query[i] = 'z';
            hi = upper_bound(words.begin(), words.end(), query, comp) - words.begin();            
        }
 
        answer.push_back(hi - lo);
    }
 
    return answer;
}
Colored by Color Scripter
  
저작자표시

'프로그래머스' 카테고리의 다른 글

2019 카카오 개발자 겨울 인턴십 징검다리 건너기 ( C++ )  (0) 2020.04.15
2019 카카오 개발자 겨울 인턴십 호텔 방 배정 ( C++ )  (0) 2020.04.11
2019 카카오 개발자 겨울 인턴십 불량 사용자 ( C++ )  (0) 2020.04.09
2019 카카오 개발자 겨울 인턴십 튜플 ( C++ )  (3) 2020.04.09
2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 ( C++ )  (0) 2020.04.08

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

 

16401번: 과자 나눠주기

첫째 줄에  조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN ≤ 1,000,000,000) 를 만족한다.

www.acmicpc.net

이분 탐색으로 조카들에게 나눠줄 수 있는 과자의 최대 길이를 찾아줘야 한다.

이분 탐색의 처음 범위는 1개를 나눠줄 수 있는 경우부터 가지고 있는 과자 중 가장 큰 과자의 길이까지가 된다.

 

 

3 10

1 2 3 4 5 6 7 8 9 10

문제의 첫 번째 예시처럼 다음과 위와 같이 막대과자를 가지고 있다면 1에서 10까지의 범위를 탐색해준다.

 

4 3

10 10 15

2번째 예제에서의 범위는 1부터 15까지이다.

 

 

문제의 예시에서는 막대과자의 길이가 모두 정렬된 순서로 되어있지만 히든 케이스에서는 정렬되어 있지 않을 수도 있으므로 입력받은 막대과자의 길이 배열을 정렬해놓고 탐색을 시작한다.

 

 

이분 탐색으로 매번 mid값을 구해서 mid길이만큼을 조카들에게 나눠줄 수 있는지 검사한다.

나눠줄 수 있다면 더 큰 길이로 나눠줄 수 있는지 mid값보다 큰 범위를 탐색하고, 나눠줄 수 없다면 더 작은 길이를 찾아야 한다.

 

 

나눠줄 수 있는지 검사할 때에는 길이가 긴 막대과자들부터 mid길이만큼을 나눌 수 있는지 확인한다. 배열을 앞에서 정렬해놓았으므로 배열의 뒤쪽부터 검사해주면 된다. mid길이만큼의 막대과자가 조카의 수이상 나온다면 mid 길이만큼씩 나누어줄 수 있다.

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <algorithm>
using namespace std;
 
int M, N;
int ans;
int arr[1000001];
 
bool check(int len) {
    int tmp;
    int cnt = 0;
 
    //배열의 맨 뒤(큰 값)부터 검사
    for (int i = N - 1; i >= 0; i--) {
        if (arr[i] < len) break;
 
        tmp = arr[i];
        while (tmp >= len) {
            cnt++;
            tmp -= len;
        }
        //len만큼의 길이가 조카의 수만큼 나온다면 바로 true를 리턴
        if (cnt >= M) return true;
    }
 
    if (cnt >= M) return true;
    else return false;
}
 
 
void binarySearch(int left, int right) {
    if (left > right) return;
 
    int mid = (left + right) / 2;
    //막대 과자 길이가 mid일때, 조카들에게 나눠줄 수 있는지 검사
    bool res = check(mid);
    if (res) {
        //나눠줄 수 있다면 일단 길이를 저장해놓고, 더 큰 길이를 나눠줄 수 있는지 탐색
        if (ans < mid) ans = mid;
        binarySearch(mid + 1, right);
    }
    else {
        //mid 길이 만큼씩 나눠줄 수 없다면 더 작은 길이를 나눠줘야한다.
        binarySearch(left, mid - 1);
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> M >> N;
 
    for (int i = 0; i < N; i++) cin >> arr[i];
    sort(arr, arr + N);
 
    ans = 0;
    binarySearch(1, arr[N - 1]);
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17090. 미로 탈출하기  (0) 2020.05.01
[BOJ] 2174. 로봇 시뮬레이션  (0) 2020.04.28
[BOJ] 10711. 모래성  (0) 2020.04.27
[BOJ] 2866. 문자열 잘라내기  (0) 2020.04.21
[BOJ] 5427. 불  (0) 2020.04.19

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

 

5427번: 불

문제 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에는 불이 붙지 않는다. 상근이는 동서남북 인접한 칸으로 이동할 수 있으며, 1초가 걸린다. 상근이는 벽을 통과할 수 없고, 불이 옮겨진 칸 또는 이제 불이 붙으려는 칸으로 이동할 수 없다. 상근이가 있는 칸에 불이 옮겨옴과 동시에 다른 칸으로 이동할 수 있다. 빌딩

www.acmicpc.net

4179번 불! (문제 링크) 문제와 스토리가 비슷한 문제인 것 같다.  (4179 불! 풀이 링크)

이 문제는 테스트 케이스가 최대 100개로 여러 개 있기 때문에 매번의 테스트 케이스에서 배열과, 큐 등 초기화를 잘해주어야 한다.

 

 

 

상근이가 최단 시간으로 탈출하는 경우와 불이 퍼지는 것을 구현하기 위해 BFS를 사용한다.

BFS는 상근이가 이동할 수 있는 곳이 더 없다면 끝나기 때문에 상근이의 좌표를 담은 큐가 비었다면 종료한다.

또는, 탈출에 성공한 경우에 바로 탐색을 종료한다.

 

 

 

큐 2개를 사용하여 상근이와 불의 위치를 각각의 큐에 넣어주고 각각 BFS를 진행한다. 같은 시간 동안 불을 먼저 이동시키고 상근이를 이동시키면 불이 확산되지 않은 곳으로 이동할 수 있다. 매 초마다 불을 먼저 확산시키고 다음에 상근이를 이동시키기 위해서 각자의 큐 사이즈만큼씩만 진행하면 된다. 한 번에 이동할 수 있는 위치만큼(현재 위치로부터 1만큼 이동한 곳)이 큐에 새로 들어가기 때문이다.

 

 

 

상근이가 빌딩 지도 범위를 넘어가면 탈출에 성공한 것이므로 바로 true를 리턴하여 시간을 출력해준다.

BFS가 끝났는데 빌딩을 탈출하지 못했다면 false를 리턴하고 문제 조건에 따라 IMPOSSIBLE을 출력한다.

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
 
int h, w, time;
char map[1000][1000];
bool visit[1000][1000];
 
queue<pair<int, int> > sq; //상근이 이동 큐
queue<pair<int, int> > fq; //불 이동 큐
 
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
 
bool bfs() {
    time = 0;
 
    while (!sq.empty()) {
        int fqsize = fq.size();
        int sqsize = sq.size();
        int x, y, nx, ny;
 
        time++;
 
        //불 이동
        while (fqsize--) {
            x = fq.front().first;
            y = fq.front().second;
            fq.pop();
            for (int k = 0; k < 4; k++) {
                nx = x + dx[k];
                ny = y + dy[k];
                //범위 체크
                if (nx < 0 || ny < 0 || nx >= h || ny >= w) continue;
                //벽
                if (map[nx][ny] == '#') continue;
                //방문 체크
                if (visit[nx][ny]) continue;
 
                fq.push({ nx,ny });
                visit[nx][ny] = true;
            }
        }
 
        //상근이 이동
        while (sqsize--) {
            x = sq.front().first;
            y = sq.front().second;
            sq.pop();
            for (int k = 0; k < 4; k++) {
                nx = x + dx[k];
                ny = y + dy[k];
                if (nx < 0 || ny < 0 || nx >= h || ny >= w) {
                    //탈출 성공
                    return true;
                }
                //벽
                if (map[nx][ny] == '#') continue;
                //방문 체크
                if (visit[nx][ny]) continue;
 
                sq.push({ nx,ny });
                visit[nx][ny] = true;
            }
        }
    }
 
 
//탈출 실패
    return false;
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
 
    while (T--) {        
        //다음 테스트 케이스를 위해 초기화
        memset(visit, false, sizeof(visit));
        while (!fq.empty()) fq.pop();
        while (!sq.empty()) sq.pop();
        bool exitFlag = false;
 
 
        cin >> w >> h;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                cin >> map[i][j];
                if (map[i][j] == '@') {
                    sq.push({ i,j });
                    map[i][j] = '.';
                    visit[i][j] = true;
                }
                else if (map[i][j] == '*') {
                    fq.push({ i,j });
                    visit[i][j] = true;
                }
            }
        }
 
 
        bool result = bfs();
 
        if (result) cout << time << '\n';
        else cout << "IMPOSSIBLE" << "\n";
    }
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 10711. 모래성  (0) 2020.04.27
[BOJ] 2866. 문자열 잘라내기  (0) 2020.04.21
[BOJ] 18809. Gaaaaaaaaaarden  (0) 2020.03.23
[BOJ] 18808. 스티커 붙이기  (0) 2020.03.23
[BOJ] 17822. 원판 돌리기  (0) 2020.03.16

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

아래의 카카오 테크 블로그에서도 해설을 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

 

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

“2019년 카카오 개발자 겨울 인턴십” 공개 채용을 위한 1차 코딩 테스트가 지난 2019년 11월 9일 오후 2시부터 6시까지 총 4시간에 걸쳐 진행되었습니다. ’19년 신입공채 1차 코딩 테스트 시에 7문제가 출제되고 5시간의 풀이 시간이 주어졌던 것과는 달리 이번 인턴 코딩 테스트는 5문제가 출제되고 4시간의 풀이 시간이 주어졌습니다. 인턴의 경우 신입 공채와는 달리 인턴 과정을 통해 추가 […]

tech.kakao.com

 

위의 해설을 참고해서 이분 탐색으로 효율성을 해결했다.

m번째 친구가 다리를 건널 수 있는지 확인할 때, m-1번째 친구까지는 건넜다고 가정한다.

 

그러면 각 stone에서 m-1을 빼준 후에(m-1번째까지 건넜으므로) 연속으로 0 이하인 부분이 k개가 나오면 m번째 친구는 다리를 건널 수 없으므로 m명보다 더 적은 수로 건널 수 있는지 다시 검사한다.

 

0하인 부분이 연속으로 k개만큼 나오지 않아서 다리를 건널 수 있다면 m명보다 더 많은 친구들이 건널 수 있는지 검사한다.

 

이 m번째를 mid값으로 놓고 이분 탐색을 진행하면 된다.

이분 탐색의 초기 최댓값은 stones 배열 각 원소들의 최댓값인 200,000,000 으로 놓는다.

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <string>
#include <vector>
#define MAX 200000000
using namespace std;
 
int maxval;
 
bool check(vector<int> stones, int k, int m) {
    //m-1번째까지는 건넜다고 가정
    int size = stones.size();
    int cnt = 0;
    for (int i = 0; i < size; i++) {
        if ((stones[i] - (m - 1)) <= 0) {
            cnt++;
            if (cnt == k) return false; //0이하가 연속으로 k면 건널수 없다.
        }
        else {
            //연속되지 않는다면 0으로 초기화
            cnt = 0;
        }
    }
    return true;
}
 
 
void binarySearch(vector<int> stones, int k, int left, int right) {
    if (left > right) return;
 
    int mid = (left + right) / 2;
    bool res = check(stones, k, mid);
 
    if (res) {
        //mid번째 친구가 건널 수 있다면 최댓값과 비교
        if (maxval < mid) maxval = mid;
 
        //mid보다 더 큰 값이 가능한지 이분 탐색
        binarySearch(stones, k, mid + 1, right);
    }
    else {
        //mid번째 친구가 건널 수 없다면 mid보다 더 작은 값 범위 탐색
        binarySearch(stones, k, left, mid - 1);
    }
}
 
 
int solution(vector<int> stones, int k) {
    int answer = 0;
 
    maxval = 0;
    binarySearch(stones, k, 1, MAX);
    answer = maxval;
 
    return answer;
}
Colored by Color Scripter
  

 

 

저작자표시

'프로그래머스' 카테고리의 다른 글

프로그래머스 [2020카카오공채] 가사 검색 c++  (3) 2020.05.06
2019 카카오 개발자 겨울 인턴십 호텔 방 배정 ( C++ )  (0) 2020.04.11
2019 카카오 개발자 겨울 인턴십 불량 사용자 ( C++ )  (0) 2020.04.09
2019 카카오 개발자 겨울 인턴십 튜플 ( C++ )  (3) 2020.04.09
2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 ( C++ )  (0) 2020.04.08

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

 

 

먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

 

2019 카카오 개발자 겨울 인턴십 코딩 테스트 문제 해설

“2019년 카카오 개발자 겨울 인턴십” 공개 채용을 위한 1차 코딩 테스트가 지난 2019년 11월 9일 오후 2시부터 6시까지 총 4시간에 걸쳐 진행되었습니다. ’19년 신입공채 1차 코딩 테스트 시에 7문제가 출제되고 5시간의 풀이 시간이 주어졌던 것과는 달리 이번 인턴 코딩 테스트는 5문제가 출제되고 4시간의 풀이 시간이 주어졌습니다. 인턴의 경우 신입 공채와는 달리 인턴 과정을 통해 추가 […]

tech.kakao.com

 

 

효율성 테스트가 있는 문제로 k의 범위가 크기 때문에 방을 하나하나 순차적으로 검사해주면 효율성 테스트에 실패한다.

효율성을 통과하는 방법은 위의 카카오 테크 블로그에 그림과 함께 굉장히 잘 설명되어있는데, 

요청한 방이 빈방이라면 바로 배정하고 배정된 방이 바로 다음 방을 가리키도록 해준다.

요청한 방이 빈방이 아니라면 그 방이 가리키는 다음 방을 계속 찾아가며 빈방을 찾는다.

이 방법은 Union-Find 알고리즘을 사용해서 효율적으로 구현할 수 있다. 부모 노드가 다음 빈 방의 번호 값을 가지도록 해주면 된다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <string>
#include <vector>
#include <map>
using namespace std;
 
map<long long, long long> m;
 
long long getNextEmptyRoom(long long num) {
    if (m[num] == 0) return num;
    return m[num] = getNextEmptyRoom(m[num]);
}
 
 
vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
 
    for (long long num : room_number) {
        long long emptyRoom = getNextEmptyRoom(num);
        answer.push_back(emptyRoom);
        m[emptyRoom] = emptyRoom + 1;
    }
 
    return answer;
}
Colored by Color Scripter
  

 

저작자표시

'프로그래머스' 카테고리의 다른 글

프로그래머스 [2020카카오공채] 가사 검색 c++  (3) 2020.05.06
2019 카카오 개발자 겨울 인턴십 징검다리 건너기 ( C++ )  (0) 2020.04.15
2019 카카오 개발자 겨울 인턴십 불량 사용자 ( C++ )  (0) 2020.04.09
2019 카카오 개발자 겨울 인턴십 튜플 ( C++ )  (3) 2020.04.09
2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 ( C++ )  (0) 2020.04.08

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

 

 

 

당첨에서 제외되어야 할 제재 아이디 목록이 몇 가지 경우의 수가 가능한 지를 구해야하는데 id배열의 크기가 8 이하이므로 모든 경우를 구해봐도 된다.

 

 

 

먼저 각 불량 아이디에 대해 모든 응모 아이디와 비교하여, 매핑될 수 있는 응모 아이디를 찾아 각각의 응모 아이디에 매핑되는 경우를 조합해준다. 불량 아이디와 매핑 될 수 있는 응모 아이디는 불량 아이디의 *부분을 제외한 모든 문자가 일치해야 하고 문자열의 길이도 같아야 한다.

 

응모 아이디를 제재목록으로 만들어주는 방법은 응모 아이디의 인덱스를 문자열로 만든 후에 이전 제재 목록 문자열과 합쳐서 넘겨주는 방법으로 구현했다.

 

문제에 나온 첫 번째 예시로 예를 들어보면 

user_id banned_id

 ["frodo", "fradi", "crodo", "abc123", "frodoc"]

 ["fr*d*", "abc1**"]

user_id

frodo와 abc123을 선택하는 경우는 각각 인덱스가 0과 3이므로 "03"

fradi와 abc123을 선택하는 경우는 각각 인덱스가 1과 3이므로 "13"이 된다.

 

 

그리고 제재 아이디 목록은 순서가 상관없으므로 이 문자열을 정렬해준 후 set에 넣어줘서 중복을 제거해줬다.

최종적으로 set의 크기가 정답이 된다.

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
#include <string>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
 
bool check[8];
int blen, ulen;
set<string> s;
 
void solve(int index, string res, vector<string> user_id, vector<string> banned_id) {
    if (index == blen) {
        //불량 사용자의 아이디가 이벤트 응모자 아이디와 모두 매핑되어 제재목록이 다 만들어졌다면
        sort(res.begin(), res.end());
        s.insert(res);
        return;
    }
 
 
    string bid = banned_id[index];
    int bidlen = bid.size();
 
    //각 응모자 아이디와 index번째 불량 사용자 아이디를 비교한다.
    for (int i = 0; i < ulen; i++) {
        string uid = user_id[i];
 
        //이벤트 응모자 아이디와 불량 사용자 아이디의 길이가 다르다면 continue
        if (uid.size() != bidlen) continue;
        //i번째 응모아이디가 이미 불량 사용자의 아이디와 매핑된 경우 continue
        if (check[i]) continue;
 
 
        bool flag = true;
        //*을 제외한 문자들이 같은지 검사
        for (int j = 0; j < bidlen; j++) {
            if (bid[j] == '*') continue;
 
            //문자가 하나라도 다르면 매핑될 수 없다.
            if (uid[j] != bid[j]) {
                flag = false;
                break;
            }
        }
 
 
        //불량 사용자의 아이디와 별을 제외한 부분이 같은 경우
        if (flag) {
            //i번째 사용자 아이디는 index번째 불량아이디에 매핑된 것으로 체크하고 다음 불량아이디를 경우를 탐색한다.
            check[i] = true;
            solve(index + 1, res + to_string(i), user_id, banned_id);
 
            //index번째 불량 아이디에 매핑 될 수 있는 다른 사용자 아이디를 위해 현재 i번은 다시 false로 체크
            check[i] = false;
        }
    }
}
 
 
int solution(vector<string> user_id, vector<string> banned_id) {
    int answer = 0;
 
    ulen = user_id.size();
    blen = banned_id.size();
 
    solve(0, "", user_id, banned_id);
    answer = s.size();
 
    return answer;
}
Colored by Color Scripter
  

 

저작자표시

'프로그래머스' 카테고리의 다른 글

2019 카카오 개발자 겨울 인턴십 징검다리 건너기 ( C++ )  (0) 2020.04.15
2019 카카오 개발자 겨울 인턴십 호텔 방 배정 ( C++ )  (0) 2020.04.11
2019 카카오 개발자 겨울 인턴십 튜플 ( C++ )  (3) 2020.04.09
2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 ( C++ )  (0) 2020.04.08
프로그래머스 [2020카카오공채] 자물쇠와 열쇠 c++  (1) 2020.03.11

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

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

먼저 깔끔한 문제풀이 설명은 카카오 테크 블로그에서 볼 수 있다.

https://tech.kakao.com/2020/04/01/2019-internship-test/

 

 

인형을 바구니에 쌓는 것을 스택을 이용해서 구현해준다.

터트려져 사라진 인형의 개수를 구하는 것이므로 터질 때마다 정답에 2씩 더 해주면 된다.

처음에 문제를 제대로 안 읽어서 바구니에 남아있는 인형이 정답인 줄 알고 왜 정답이 안 나오지 하고 있었다...

 

 

 

먼저 moves에 있는 인형을 뽑을 위치는 1부터 시작하므로 인덱스로 사용하기 위해서 1을 빼주고 사용한다.

그리고 해당 위치에서 인형이 있는 곳까지 아래로 쭉쭉 내려간다.

문제 조건에 따라 인형을 발견하지 못하면 그냥 다음 뽑을 위치로 넘어가면 되고, 집어 올린 인형과 바구니 위의 가장 위에 있는 인형을 비교해준다.

 

 

 

바구니(스택)의 가장 위에 있는 인형과 현재 뽑은 인형이 같다면 가장 위에 있는 인형을 스택에서 pop 해주고 정답에 2를 더해준다.

같지 않다면 그냥 뽑은 인형을 바구니(스택)에 push 해준다.

 

 

스택에 쌓이든 터져서 사라지든 일단 크레인으로 잡혀서 왔으므로 원래 있던 자리는 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
#include <string>
#include <vector>
#include <stack>
using namespace std;
 
int solution(vector<vector<int>> board, vector<int> moves) {
    int answer = 0;
 
    stack<int> stk;
    int n = board.size();
    
    for (int num : moves) {
        num -= 1;    
        for (int i = 0; i < n; i++) {
            if (board[i][num] == 0) continue;
 
            if (!stk.empty() && stk.top() == board[i][num]) {
                stk.pop();
                answer += 2;
            }
            else {
                stk.push(board[i][num]);
            }
 
            board[i][num] = 0;
            break;
        }
    }
 
    return answer;
}
Colored by Color Scripter
  
저작자표시

'프로그래머스' 카테고리의 다른 글

2019 카카오 개발자 겨울 인턴십 불량 사용자 ( C++ )  (0) 2020.04.09
2019 카카오 개발자 겨울 인턴십 튜플 ( C++ )  (3) 2020.04.09
프로그래머스 [2020카카오공채] 자물쇠와 열쇠 c++  (1) 2020.03.11
프로그래머스 [2020카카오공채] 블록 이동하기 c++  (2) 2020.02.14
프로그래머스 [2020카카오공채] 괄호 변환 c++  (0) 2019.10.17

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

 

10757번: 큰 수 A+B

두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오.

www.acmicpc.net

수의 범위가 long long의 범위도 넘어가는 경우에는 문자열로 구현해주어야 한다.

이 문제를 풀어놓으면 활용해서 풀 수 있는 문제들이 꽤 있다. (1914 하노이탑, 2407 조합, 10826 피보나치 수 4 등)

15353번 큰 수 A + B (2) 문제는 아예 똑같은 코드로 풀 수 있다.

 

 

먼저 문자열 두 개를 입력받았으면 덧셈을 해주기 위해서 자릿수를 맞춰주어야 한다.

길이를 비교하고 길이가 더 짧은 곳에 0을 붙여준다.

예를 들어 123456과 123456789이라면 123456 앞에 두 수의 길이의 차이인 3만큼 0을 붙여줘서 000123456을 만들어준 후에 덧셈을 진행한다.

 

 

각각의 자리에서 더해주고 9보다 큰 값이 있다면 다음 자릿수의 덧셈에서 1을 더 더해준다.

이런 식으로 정답 문자열에 붙여주면 거꾸로 되므로 마지막에 문자열을 뒤집어준다.

 

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    string a, b;
    string ans = "";
    cin >> a >> b;
 
    int n = a.length() - 1;
    int m = b.length() - 1;
 
 
    //자릿수 맞춰준다.
    string tmp = "";
    if (n < m) {
        for (int i = 0; i < m - n; i++) {
            tmp += "0";
        }
        a = tmp + a;
    }
    else if (n > m) {
        for (int i = 0; i < n - m; i++) {
            tmp += "0";
        }
        b = tmp + b;
    }
 
    
    int len = a.size(); //자릿수 위에서 맞춰줬으므로 길이 아무거나 상관없음
    int x, y, z;
    int up = 0;
 
//1의 자리부터 진행
    for (int i = len - 1; i >= 0; i--) {
        x = a[i] - '0';
        y = b[i] - '0';
        z = x + y;
        if (up == 1) {
            z += 1;
            up = 0;
        }
 
 
        if (z > 9) {
            ans += to_string(z % 10);
            up = 1;
        }
        else {
            ans += to_string(z);
        }
    }
    
    if (up == 1) ans += "1";
 
 
    reverse(ans.begin(), ans.end());
 
    cout << ans << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 18808. 스티커 붙이기  (0) 2020.03.23
[BOJ] 17822. 원판 돌리기  (0) 2020.03.16
[BOJ] 1331. 나이트 투어  (0) 2020.03.03
[BOJ] 4179. 불!  (0) 2020.02.17
[BOJ] 1938. 통나무 옮기기  (0) 2020.02.12

+ Recent posts

티스토리툴바