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/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://programmers.co.kr/learn/courses/30/lessons/60059

 

코딩테스트 연습 - 자물쇠와 열쇠 | 프로그래머스

[[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true

programmers.co.kr

lock의 크기와 key의 크기가 최대 20이므로 완전 탐색으로 해결할 수 있다.

(key를 90도씩 회전시키는 네 가지 경우) X (자물쇠에 열쇠를 맞춰보는 모든 경우)를 구해주면 된다.

 

주의할 점은 예제에는 똑같이 나와있지만 lock의 크기와 key의 크기는 다를 수 있다.

또, 열쇠를 회전시킬 때 회전시키는 함수에서 실제 key 벡터를 회전시켜야 하므로 &로 받아야 한다.

 

 

문제 조건에 따라서 열쇠는 자물쇠 밖으로 나가도 되므로

열쇠를 자물쇠 홈에 맞춰보는 모든 경우를 위해서 아래 그림과 같이 새로운 2차원 vector를 만들어줬다.

 

열쇠의 가장 오른쪽 아랫부분과 자물쇠의 가장 위쪽 부분을 맞추는 경우부터

열쇠의 가장 왼쪽 윗부분과 자물쇠의 가장 오른쪽 아래 부분을 맞추는 경우까지를 모두 해주면 되기 때문에

lock의 크기 + (key의 크기 -1)*2 크기의 벡터를 만들어주면 된다.

 

 

 

그러면 매 회전 때마다 key의 시작 부분이

(0,0)에서 시작하는 경우부터 lock의 가장 마지막 부분(boardsize-keysize)에서부터 시작하는 경우까지 해보면서

key를 board에 더해 lock부분이 모두 1인지(홈이 모두 채워졌는지)를 확인하면 된다

한 곳이라도 0이거나(비어있는 홈) 2(돌기 두 개가 만남) 이면 안되므로 바로 false를 리턴한다.

 

 

 

**기존 상태에서 먼저 열쇠를 맞춰보면 회전은 3번만 하면 된다고 생각해서

반복문을 3번만 실행하도록 했어서 한참 헤맸다;;

맞춰보는 경우는 어쨌든 4번 해야 하므로 반복문을 4번 실행해주어야 한다...

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
#include <string>
#include <vector>
using namespace std;
 
int keysize, locksize, boardsize;
 
void rotateKey(vector<vector<int>> &key) {
        
    vector<vector<int>> tmp(keysize, vector<int>(keysize));
 
    for (int j = keysize - 1; j >= 0; j--) {
        for (int i = 0; i < keysize; i++) {
            tmp[i][j] = key[keysize - j - 1][i];
        }
    }
 
    key = tmp;
}
 
 
bool putKey(int x, int y, vector<vector<int>> key, vector<vector<int>> board) {
     //(x, y)를 시작점으로 열쇠를 자물쇠에 맞춰본다.
 
    //key를 더한다
    for (int i = x; i < x + keysize; i++) {
        for (int j = y; j < y + keysize; j++) {
            board[i][j] += key[i - x][j - y];
        }
    }
 
 
    //좌물쇠 부분 확인
    for (int i = keysize - 1; i <= boardsize - keysize; i++) {
        for (int j = keysize - 1; j <= boardsize - keysize; j++) {
            if (board[i][j] == 1) continue;
 
            //1이 아니라면 바로 false를 리턴
            return false;
        }
    }
 
 
    return true;
}
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
 
    keysize = key.size();
    locksize = lock.size();
 
 
    boardsize = locksize + (keysize - 1) * 2;
    vector<vector<int>> board(boardsize, vector<int>(boardsize, 0));
 
 
    //board에 lock을 미리 더해놓는다. (lock은 고정되어 있고 key를 움직일 것 이므로)
    for (int i = keysize - 1; i <= boardsize - keysize; i++) {
        for (int j = keysize - 1; j <= boardsize - keysize; j++) {
            board[i][j] = lock[i - keysize + 1][j - keysize + 1];
        }
    }
 
    //회전 방향 네번
    for (int r = 0; r < 4; r++) {
        
        for (int i = 0; i <= boardsize - keysize; i++) {
            for (int j = 0; j <= boardsize - keysize; j++) {
 
                //i,j 를 key의 시작칸으로 자물쇠 홈에 맞춰본다.
                if (putKey(i, j, key, board)) {
                    answer = true;
                    return answer;
                }
 
            }
        }
 
 
        //key 시계방향으로 90도 회전
        rotateKey(key);
 
    }
 
 
    return answer;
}
Colored by Color Scripter
  
저작자표시

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

2019 카카오 개발자 겨울 인턴십 튜플 ( C++ )  (3) 2020.04.09
2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 ( C++ )  (0) 2020.04.08
프로그래머스 [2020카카오공채] 블록 이동하기 c++  (2) 2020.02.14
프로그래머스 [2020카카오공채] 괄호 변환 c++  (0) 2019.10.17
프로그래머스 [2020카카오공채] 문자열 압축 c++  (0) 2019.10.17

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

 

코딩테스트 연습 - 블록 이동하기 | 프로그래머스

[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7

programmers.co.kr

 

백준의 1938번 통나무 옮기기(문제 링크)와 비슷한 느낌의 BFS 문제다.

(통나무 옮기기 풀이 링크)

 

이게 조금 더 어려운 것 같기는 하다...

좌표를 어떻게 저장할까 하다가 아래 카카오 기술 블로그에 있는 해설에서 아이디어를 얻어서 풀었다.

 

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

 

위의 해설에

(r, c, d) : (r, c) 위치에서 d 방향에 있는 칸을 한 칸 더 차지하고 있음이라고 나와있어서

로봇의 x, y좌표, 방향, 시간을 구조체로 저장해 큐에 넣어서 BFS를 진행하였다.

로봇의 나머지 한 칸은 방향 정보를 이용하여 구한다.

 

 

매번 상, 하, 좌, 우로 이동하는 경우와

로봇의 두 칸 중 한 칸에서 시계방향으로 90도 회전하는 경우 / 반시계 방향으로 90도 회전하는 경우

나머지 한 칸에서 시계방향으로 90도 회전하는 경우 /반시계 방향으로 90도 회전하는 경우 중

이동 가능한 위치(벽이 아니고 범위를 벗어나지 않는 곳)를 계속 큐에 넣어주면서 진행하면 된다.

 

 

 

로봇을 이동시킬 때, 두 칸 중 한 칸만의 좌표를 기준으로 이동시키므로

로봇의 한 칸을 (x, y)라고 하고 다른 한칸을 (xx, yy)라고 했을 때, visit 배열을 (x, y)를 기준으로 방문을 확인하고 큐에도 (x, y)좌표와 (x, y) 기준의 방향이 들어간다.


따라서 (x, y)축을 기준으로 회전할때는 (x, y)의 좌표는 변화가 없고 방향만 변화하므로 새로 큐에 넣을 때도 (x, y) 좌표 그대로와 회전된 새 방향을 넣어준다.

반대로, (xx, yy)를 축으로 (x, y)를 회전한 경우에는 (x, y)를 이동시킨 위치인 (nx, ny)를 기준으로 만들어주기 위해서 방향을 반대로 바꿔주고 큐에 넣어줄 때에도 (xx, yy)가 아닌 (nx, ny) 좌표와 (nx, ny) 기준의 방향을 넣어준다.

 

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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include <vector>
#include <queue>
using namespace std;
 
int n;
bool visit[100][100][4];
 
int dx[] = { 0, 1, 0, -1 };
int dy[] = { 1, 0, -1, 0 };
 
//회전할 때 지나칠 곳
int ndx[] = { -1,1,1,-1 };
int ndy[] = { 1,1,-1,-1 };
 
struct Robot {
    int x;
    int y;
    int dir;
    int time;
    Robot(int a, int b, int d, int t) {
        x = a;
        y = b;
        dir = d;
        time = t;
    }
};
 
bool rangeCheck(int x, int y, int xx, int yy) {
    if (x < 0 || x >= n || y < 0 || y >= n) return false;
    if (xx < 0 || xx >= n || yy < 0 || yy >= n) return false;
 
    return true;
}
 
 
int solution(vector<vector<int>> board) {
 
    queue<Robot> q;
    q.push(Robot(0, 0, 0, 0));
    visit[0][0][0] = true;
 
    n = board.size();
    int destX = n - 1;
    int destY = n - 1;
 
    int cnt = 0;
    while (!q.empty()) {
        int x = q.front().x;
        int y = q.front().y;
        int dir = q.front().dir;
        int time = q.front().time;
        q.pop();
 
        //로봇의 나머지 한칸
        int xx = x + dx[dir];
        int yy = y + dy[dir];
 
 
        //로봇의 한칸이라도 도착하면 종료
        if (x == destX && y == destY) return time;
        if (xx == destX && yy == destY) return time;
 
 
        int nx, ny, nxx, nyy;
 
        //우, 하, 좌, 상 이동
        for (int k = 0; k < 4; k++) {
            nx = x + dx[k];
            ny = y + dy[k];
            nxx = xx + dx[k];
            nyy = yy + dy[k];
            
            //이동할 곳의 범위 체크
            if (!rangeCheck(nx, ny, nxx, nyy)) continue;
            //이동할 곳의 방문 체크
            if (visit[nx][ny][dir]) continue;
            //이동할 수 있는지 체크
            if (board[nx][ny] == 1 || board[nxx][nyy] == 1) continue;
 
            visit[nx][ny][dir] = true;
            q.push(Robot(nx, ny, dir, time + 1));
 
        }
 
 
        //x,y 를 축으로 90도 회전
        for (int i = 1; i < 4; i += 2) {
            int ndir = (dir + i) % 4;
            nxx = x + dx[ndir];
            nyy = y + dy[ndir];
 
            int rx, ry; //회전하면서 지나갈 곳의 좌표
            if (i == 1) {
                //시계방향 회전인 경우
                rx = x + ndx[ndir];
                ry = y + ndy[ndir];
            }
            else {
                //반시계방향 회전인 경우
                rx = x + ndx[dir];
                ry = y + ndy[dir];
            }
            
            if (!rangeCheck(rx, ry, nxx, nyy)) continue;
            if (visit[x][y][ndir]) continue;
            if (board[nxx][nyy] == 1) continue;
            if (board[rx][ry]) continue;
 
            visit[x][y][ndir] = true;
            q.push(Robot(x, y, ndir, time + 1));
        }
        
 
        //xx, yy 를 축으로 90도 회전
        dir = (dir + 2) % 4; //xx, yy가 기준이므로 방향이 반대로 바뀐다.
        for (int i = 1; i < 4; i += 2) {
            int ndir = (dir + i) % 4;
            nx = xx + dx[ndir];
            ny = yy + dy[ndir];
 
            int rx, ry; //회전하면서 지나갈 곳의 좌표
            if (i == 1) {
                //시계방향 회전인 경우
                rx = xx + ndx[ndir];
                ry = yy + ndy[ndir];
            }
            else {
                //반시계방향 회전인 경우
                rx = xx + ndx[dir];
                ry = yy + ndy[dir];
            }
 
            if (!rangeCheck(nx, ny, rx, ry)) continue;
            if (board[nx][ny] == 1) continue;
            if (board[rx][ry] == 1) continue;
 
            ndir = (ndir + 2) % 4;
            if (visit[nx][ny][ndir]) continue;
            visit[nx][ny][ndir] = true;
            q.push(Robot(nx, ny, ndir, time + 1));
        }
        
 
 
    }
 
}
Colored by Color Scripter
  

 

저작자표시

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

2019 카카오 개발자 겨울 인턴십 크레인 인형뽑기 게임 ( C++ )  (0) 2020.04.08
프로그래머스 [2020카카오공채] 자물쇠와 열쇠 c++  (1) 2020.03.11
프로그래머스 [2020카카오공채] 괄호 변환 c++  (0) 2019.10.17
프로그래머스 [2020카카오공채] 문자열 압축 c++  (0) 2019.10.17
프로그래머스 - 소수 찾기  (0) 2019.10.04

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

 

코딩테스트 연습 - 문자열 압축 | 프로그래머스

데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수

programmers.co.kr

문자열을 자르는 단위를 1부터 시작해서 모두 해보면 된다.

단위가 문자열의 길이의 반보다 커지면 절대 더 압축되지 않으므로 1부터 문자열의 길이/2 까지만 해보면 된다.

 

 

i개로 자른다고 했을 때, 문자열의 처음부터 i개만큼씩을 문자열 끝까지 계속 검사해주면 된다.

(i개로 나누어 떨어지지 않고 남은 부분은 마지막에 추가적으로 붙여준다.)

 

 

i개로 자른 문자열이 바로 이어서 나타난다면 cnt값을 증가시킨다.

그렇지 않다면, 압축된 결과를 저장할 문자열(result)에 문자열 단위를 붙여주고 문자열 단위를 새로 j번부터 i개로 업데이트한다. 이때, 문제 조건에 따라서 이 문자열 단위가 여러 개였다면(cnt가 1 이상이라면) cnt를 문자열 앞에 붙여서 result에 추가하고 cnt는 1로 다시 초기화한다.

 

 

i개로 잘라서 압축한 경우의 문자열을 모두 완성했다면 그때의 길이를 최솟값과 비교한다.

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
#include <string>
#include <vector>
using namespace std;
 
int solution(string s) {
    int len = s.size();
    int answer = len;
 
    int n = len / 2;
 
 
    //i개 단위로 잘라서 압축
    for (int i = 1; i <= n; i++) {
 
        //i개 단위로 잘라서 압축한뒤 만들어지는 문자열
        string result = "";
 
        //자를 문자열 단위
        string ss = s.substr(0, i);
 
        int cnt = 1;
 
        //앞에서 자른 문자열 단위를 제외한 뒷부분(j번 문자부터) 문자열을 검사한다.
        for (int j = i; j <= len; j += i) {
            //j번 부터 i개 만큼이 문자열 단위와 똑같은 경우 cnt 증가
            if (ss == s.substr(j, i)) {
                cnt += 1;
            }
            else {
                //다른 경우 중 cnt가 1이면 result에 그대로 ss를 붙인다.
                if (cnt == 1) {
                    result += ss;
                }
                else {
                    //cnt가 1보다 크다면 cnt를 문자열 단위 앞에 붙여서 result에 이어준다.
                    result += (to_string(cnt) + ss);
                }
 
                //문자열 단위를 j번부터 i개로 변경 
                ss = s.substr(j, i);
                //cnt값 다시 1로 초기화
                cnt = 1;
            }
 
        }
 
        //문자열이 i로 나누어 떨어지지 않는다면 result에 나머지 부분을 붙여줘야한다.
        if ((len%i) != 0) {
            result += s.substr((len / i)*i);
        }
 
        //최솟값을 answer에 저장
        if (answer > result.size()) answer = result.size();
    }
 
 
    return answer;
}
Colored by Color Scripter
  
저작자표시

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

프로그래머스 [2020카카오공채] 블록 이동하기 c++  (2) 2020.02.14
프로그래머스 [2020카카오공채] 괄호 변환 c++  (0) 2019.10.17
프로그래머스 - 소수 찾기  (0) 2019.10.04
프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 프렌즈4블록 c++  (0) 2019.08.29
프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 다트 게임 c++  (0) 2019.08.28

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

 

코딩테스트 연습 - 소수 찾기 | 프로그래머스

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다. 각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers는 길이 1 이상 7 이하인 문자열입니다. numbers는 0~9까지 숫자만으로 이루어져 있습니다. 013은 0, 1, 3 숫자가 적힌 종이

programmers.co.kr

문자열로 주어지는 numbers의 길이가 7이하이기 때문에 완전탐색으로 풀 수 있다.

문제 카테고리도 완전 탐색이어서 바로 알 수 있긴하다...

 

1. 먼저 에라토스테네스의 체를 이용해서 소수를 모두 구해놓는다. 숫자 i가 소수라면 check[i]는 false값을 갖는다.

2. numbers의 각 자리의 값을 int형으로 변환하여 벡터에 넣어줬다.

3. 벡터에 넣어준 값들로 만들 수 있는 값들을 모두 구해서 set에 넣어준다(중복을 없애기 위해서)

4. 마지막으로 set에 있는 값들을 검사하여 소수이면 answer값을 증가시킨다.

 

 

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
#include <string>
#include <vector>
#include <set>
#define MAX 10000000
using namespace std;
 
bool check[MAX+1];
bool used[10];
set<int> st;
vector<int> vt;
 
void getPrime() {
    check[0] = true;
    check[1] = true;
    for(int i=2; i*i<=MAX; i++) {
        if(check[i]) continue;
        for(int j = i+i; j<=MAX; j+=i) {
            check[j] = true;
        }
    }
}
 
int n;
void select(int index, int num) {
    if(index == n) {
        //n가지 종이조각을 모두 사용하였다.
        return;
    }
    
    int newnum;
    
    //n가지의 종이조각으로 만들 수 있는 모든 수를 구한다.
    for(int i=0; i<n; i++) {
        //i번째 종이 조각을 사용하였는지 검사
        if(used[i]) continue;
        
        //i번째 종이 조각을 사용한다.
        used[i] = true;
 
        //이전의 숫자와 i번째 숫자를 합쳐준다.
        newnum = num*10+vt[i];
        
        //set에 넣고
        st.insert(newnum);
        
        //현재 만들어진 숫자에 다른 숫자를 더 붙이는 경우 탐색
        select(index+1, newnum);
 
        //다른 종이를 선택하는 경우를 위해서 다시 false값으로 변경
        used[i] = false;
    }
}
 
int solution(string numbers) {
    int answer = 0;
    n = numbers.size();
    
    //소수를 찾는다.(소수이면 check배열 값이 true)
    getPrime();
 
    
    //int로 바꿔서 vector에 넣는다.
    for(char c : numbers) {
        vt.push_back(c-'0');
    }
 
    
    //만들 수 있는 숫자 조합을 중복없이 구한다.
    select(0,0);
    
    //set에 들어가있는 값이 소수이면 answer값 증가
    for(auto iter=st.begin(); iter!=st.end(); iter++) {
        if(!check[*iter]) answer++;
    }
    
    return answer;
}
Colored by Color Scripter
  
저작자표시

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

프로그래머스 [2020카카오공채] 괄호 변환 c++  (0) 2019.10.17
프로그래머스 [2020카카오공채] 문자열 압축 c++  (0) 2019.10.17
프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 프렌즈4블록 c++  (0) 2019.08.29
프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 다트 게임 c++  (0) 2019.08.28
프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 비밀지도 c++  (0) 2019.08.26

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

 

코딩테스트 연습 - [1차] 프렌즈4블록 | 프로그래머스

프렌즈4블록 블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 프렌즈4블록. 같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다. 만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면

programmers.co.kr

백준의 Puyo Puyo문제나 SWEA의 벽돌 깨기 문제와 비슷한 문제다.

이 문제에서는 네 칸만 확인해주면 되므로 모든 (i, j) 칸이 바로 오른쪽(j+1, i), 바로 아래쪽(i+1, j), 대각선 아래(i+1, j+1)와 같은지 확인해주면 된다. 이때 범위를 넘어가지 않도록 i는 m-1보다 작을 때까지, j는 n-1보다 작을 때까지만 검사한다. 그리고 지워진 칸에 대해서는 검사하지 않는다.

 

 

네 칸이 모두 같을 때, 해당 칸이 이미 다른 칸으로부터 지워질 수도 있기 때문에 바로 answer값을 증가시키지 않는다. 위의 그림에서 라이언 하나가 중복되어 있는 경우다. check배열을 사용하여 false인 경우에만 answer값을 증가시킨고 check배열의 값을 true로 바꿔준다.

 

 

모든 칸에 대해서 검사를 하는동안 한 번이라도 지워지는 게 있다면 flag변수가 true값을 갖는다.

검사가 끝난 후에 flag변수가 false값을 가지고 있다면 지워지는 게 없다는 뜻이므로 검사를 종료한다.

true값을 가지고 있다면 지워져야하는 블록들이 있다는 뜻이므로 check배열의 값이 true인 블록들을 빈칸으로 만드어준다.

 

 

지워진 블록들이 있다면 이제 떠있는 블록들을 아래로 내려줘야한다.

모든 열에 대해서 각 행들을 밑에서부터 검사해준다. 밑에서부터 빈칸을 찾은 후에 그 빈칸보다 위쪽에 떠있는 블록을 찾아서 해당 빈칸으로 내려주면 된다. ok변수를 사용해서 발견한 빈칸보다 위쪽 칸들이 모두 빈칸일 경우에는 떠있는 블록이 없다는 뜻이므로 다음 열의 검사로 넘어간다.

 

 

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
#include <string>
#include <vector>
#include <cstring>
 
using namespace std;
 
bool check[30][30];
 
int solution(int m, int n, vector<string> board) {
    int answer = 0;
 
    while (true) {
 
        bool flag = false;
        memset(check, false, sizeof(check));
 
        for (int i = 0; i<m - 1; i++) {
            for (int j = 0; j<n - 1; j++) {
 
                if (board[i][j] == ' ') continue;
                if (board[i][j] != board[i][j + 1]) continue;
                if (board[i][j] != board[i + 1][j]) continue;
                if (board[i][j] != board[i + 1][j + 1]) continue;
 
                flag = true;
 
                if (!check[i][j]) {
                    check[i][j] = true;
                    answer++;
                }
 
                if (!check[i][j + 1]) {
                    check[i][j + 1] = true;
                    answer++;
                }
 
                if (!check[i + 1][j]) {
                    check[i + 1][j] = true;
                    answer++;
                }
 
                if (!check[i + 1][j + 1]) {
                    check[i + 1][j + 1] = true;
                    answer++;
                }
 
 
 
            }
        }
 
 
        //더 지워질게 없다면 종료
        if (!flag) break;
 
 
        //붙어있는 애들 지워준다.
        for (int i = 0; i<m; i++) {
            for (int j = 0; j<n; j++) {
                if (check[i][j]) board[i][j] = ' ';
            }
        }
 
 
        //블록 지워진 후에 아래로 떨어져서 빈공간 채운다.
        for (int j = 0; j<n; j++) {
            for (int i = m - 1; i >= 0; i--) {
                if (board[i][j] != ' ') continue;
 
                bool ok = false;
 
                for (int k = i - 1; k >= 0; k--) {
 
                    if (board[k][j] != ' ') {
                        board[i][j] = board[k][j];
                        board[k][j] = ' ';
                        ok = true;
                        break;
                    }
 
                }
 
                if (!ok) break;
 
            }
        }
 
 
    }
    return answer;
}
Colored by Color Scripter
  
저작자표시

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

프로그래머스 [2020카카오공채] 문자열 압축 c++  (0) 2019.10.17
프로그래머스 - 소수 찾기  (0) 2019.10.04
프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 다트 게임 c++  (0) 2019.08.28
프로그래머스 (2017년)KAKAO BLIND RECRUITMENT 비밀지도 c++  (0) 2019.08.26
프로그래머스 (2018년)KAKAO BLIND RECRUITMENT 실패율 c++  (0) 2019.08.22

+ Recent posts

티스토리툴바