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/17090

 

17090번: 미로 탈출하기

크기가 N×M인 미로가 있고, 미로는 크기가 1×1인 칸으로 나누어져 있다. 미로의 각 칸에는 문자가 하나 적혀있는데, 적혀있는 문자에 따라서 다른 칸으로 이동할 수 있다. 어떤 칸(r, c)에 적힌 문자가 U인 경우에는 (r-1, c)로 이동해야 한다. R인 경우에는 (r, c+1)로 이동해야 한다. D인 경우에는 (r+1, c)로 이동해야 한다. L인 경우에는 (r, c-1)로 이동해야 한다. 미로에서 탈출 가능한 칸의 수를 계산해보자. 탈출 가능한

www.acmicpc.net

각 칸은 방향이 정해져 있기 때문에 하나의 방향으로만 이동하여 경로는 정해져 있게 된다. 즉 탈출하는 경로를 찾으면 해당 경로에 해당하는 칸들은 모두 탈출 가능하다. 마찬가지로 탈출할 수 없는 경로가 있다면 해당 칸들은 모두 탈출 불가능하다. 참고로 경로를 따로 저장해놨다가 나중에 다시 한번에 체크해주는 방식으로 구현하면 시간 초과가 발생하므로 DFS로 구현해야 한다.

 

 

3 3

DDR

DLU

LLL

문제의 2번째 예제로 예를 들어보면 첫 번째 칸(0, 0)인 D에서 출발하면 정해진 방향에 따라 D-D-L의 경로로 탈출이 가능하다. 그러면 당연히 (1, 0)인 D에서도 D-L 로도 탈출 가능하고, (2, 0) L에서도 탈출 가능하다. 정확히는 L에서 탈출이 가능한 것이고 위의 D에서는 L로 향하게 방향이 되어있기 때문에 마찬가지로 탈출이 가능하다.

 

 

3 3

DDR

DLU

LLL

다음에 (0, 1) 칸인 위의 파란색 D에서 출발하면 아래로 내려와 L에 도착하고 L에서는 (1, 0)인 D에 도착한다. 그러면 위에서 이미 탈출 가능하다고 확인되었으므로 D에서 L까지 오는 경로는 모두 탈출 가능하다고 판단이 가능하다.

 

 

3 4

RRDD

RRDR

DULU

문제의 예제 입력 4번을 마지막 예시로 들어보면 처음 (0, 0)인 R에서 출발했을 때, R-R-D-D-L-U-R까지 왔다가 다시 D로 와서 사이클이 발생하기 때문에 탈출이 불가능하다. 이때의 각 경로에서는 탈출이 불가능하다는 것을 저장해놓으면 다음 (0,1), (0,2) 등의 빨간 경로에서는 다시 탐색할 필요가 없다.

 

 

3 4

RRDD

RRDR

DULU

마찬가지로 (1, 0)에서 출발하면 미리 저장해놓은 탈출할 수 없는 경로인 (1, 1) R에 도착하므로 탈출할 수 없는 칸이라는 것을 금방 알 수 있다.

 

 

이제 구현을 위해서는 문자를 입력받을 map배열 이외에 두 가지 배열을 더 사용하였다.

x, y 칸에서 탈출이 가능한지 저장할 check배열과 매번 각 탐색에서 방문했는지 확인할 visit배열을 사용하였다.

check배열의 값이 1이면 탈출 가능 / 2이면 탈출 불가능 / 0이면 아직 확인 안 됨으로 해놓고 구현했다.

 

 

또한, 이동한 경로를 저장하기 위해서 DFS를 사용하였다. 이동할 수 있는 칸까지 계속 이동하다가 탈출에 성공하거나 사이클이 발견돼서 실패하는 칸을 발견할 때까지 쭉쭉 탐색을 한다. 탈출에 성공했다면 true값을 리턴하고 실패했다면 false값을 리턴한다. DFS로 리턴 받은 값이 true이면 현재 칸에서 탈출이 가능하다는 뜻이므로 check배열 값을 1로 바꿔주고 탐색에서 돌아왔으므로 visit배열은 false로 바꿔준다. 반대로 false를 리턴 받았다면 check배열의 값을 2로 해주고 visit배열은 마찬가지로 false로 바꿔준다.

 

 

다시 정리를 해보면 복잡해 보이긴 하지만 아래와 같다.

 

  1. 입력을 받는다.
  2. 모든 칸을 검사하여 탈출할 수 있는지 검사한다.
    • 이미 탈출 불가능한 칸으로 확인되었다면 DFS탐색을 하지 않고 다음 칸으로 넘어간다.
    • 이미 탈출 가능한 칸으로 확인되었다면 정답 카운트를 증가시키고 DFS탐색을 하지 않는다. 마찬가지로 다음 칸으로 넘어간다.
    • 확인되지 않은 칸이라면 DFS로 이동해서 경로를 확인하고 탈출할 수 있다면 정답 카운트를 증가시킨다.
  3. 탈출할 수 있는지 검사하기 위해 DFS를 진행한다.
    •  해당 칸에 적혀 있는 문자에 따라 좌표를 이동한다.
    • 범위를 벗어나면 탈출에 성공한 것이므로 해당 좌표의 check배열 값을 1로 바꿔주고 true를 리턴한다.
    • 방문한 칸의 check배열을 값이 1이라면 이미 탈출 가능한 칸이라고 확인됐으므로 check배열의 값을 1로 바꾸고 true를 리턴한다.
    • visit배열을 확인하여 이번 탐색에서 방문했던 칸을 다시 방문하거나(cycle 발생) check배열을 확인했을 때 값이 2로 이미 탈출 불가능한 칸이라고 확인됐으면 check배열의 값을 2로 해주고 false를 리턴한다.
    • 위의 경우들이 아닌 이동한 칸에서 이동을 계속하는 경우에는 DFS탐색을 계속해주면 된다. visit배열을 true값으로 바꿔놓고 재귀 호출로 다음 칸으로 이동한고, 재귀 호출에서 돌아오면 visit배열을 다시 false값으로 바꿔준다. 탐색 결과에 따라 check배열의 값을 바꿔주면 되는데, 결과는 위의 3가지 상황 중에서 true나 false를 리턴 받은 값이다. 이전의 호출 함수에게도 이 결과를 그대로 리턴해줘서 현재 경로의 해당하는 모든 칸에 탈출이 가능한지 체크하도록 해준다.

 

 

DFS의 기본 개념을 알고 있다면 어렵지 않은 문제다.

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
#include <iostream>
using namespace std;
 
int n, m;
char map[501][501];
bool visit[501][501];
int check[501][501];
 
 
bool solve(int r, int c) {
    //이동 전 위치 저장
    int x = r;
    int y = c;
        
    char dir = map[r][c];
 
    if (dir == 'U') r -= 1;
    else if (dir == 'R') c += 1;
    else if (dir == 'D') r += 1;
    else c -= 1;
 
    if (r < 0 || c < 0 || r >= n || c >= m) {
        //탈출
        check[x][y] = 1;
        return true;
    } else if (check[r][c] == 1) {
        //탈출할 수 있는 경로
        check[x][y] = 1;
        return true;
    } else if (visit[r][c] || check[r][c] == 2) {
        //방문했던 곳으로 다시 돌아오거나(cycle) || 탈출할 수 없는 경로
        check[x][y] = 2;
        return false;
    }
    else {
        visit[r][c] = true;
        bool flag = solve(r, c);
        visit[r][c] = false;
 
        if (flag) check[r][c] = 1;
        else check[r][c] = 2;
 
        return flag;
    }
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> map[i];
 
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (check[i][j] == 2) continue; //탈출불가능
            if (check[i][j] == 1) ans++; //탈출가능
            else {
                if (solve(i, j)) ans++;
            }
        }
    }
 
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  

 

 

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 16401. 과자 나눠주기  (2) 2020.04.29
[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/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/2174

 

2174번: 로봇 시뮬레이션

문제 가로 A(1≤A≤100), 세로 B(1≤B≤100) 크기의 땅이 있다. 이 땅 위에 로봇들이 N(1≤N≤100)개 있다. 로봇들의 초기 위치는 x좌표와 y좌표로 나타난다. 위의 그림에서 보듯 x좌표는 왼쪽부터, y좌표는 아래쪽부터 순서가 매겨진다. 또한 각 로봇은 맨 처음에 NWES 중 하나의 방향을 향해 서 있다. 초기에 서 있는 로봇들의 위치는 서로 다르다. 이러한 로봇들에 M(1≤M≤100)개의 명령을 내리려고 한다. 각각의 명령은 순차적으로

www.acmicpc.net

이 문제의 정답률이 낮은 것은 방향이 헷갈려서인 것 같다. 우선 1번 인덱스가 왼쪽 아래부터 시작하고, 입력받는 x, y 도 반대이다. 문제에서 주어지는 아래 그림에서 오른쪽 위에 있는 로봇의 좌표는 (5, 4)인 것에 주의해야 한다.

 

 

 

 

 

 

위의 그림을 아래 그림처럼 시계방향으로 90도 돌려서 생각하면 쉽게 풀 수 있다. (x <= A, y <= B)

일반적으로 사용하는 2차원 배열의 모양이므로 (x, y)를 입력받은 그대로 사용할 수 있다.

대신에 방향도 같이 90도 돌려야 하므로 W면 N방향으로/ N이면 E방향으로/ E면 S방향으로/ S면 W방향으로 바꿔준다.

 

로봇 정보는 현재 위치정보와 방향 정보를 구조체에 넣어서 관리한다. 로봇들은 처음에 입력받은 순서대로 번호를 가지므로 로봇 정보를 가지는 구조체를 벡터에 순차적으로 넣어놓는다. 벡터의 i번 인덱스 위치에 들어있는 로봇 정보가 i번 로봇의 정보이다. 1번 로봇부터 사용하기 위해 벡터에 0번 인덱스 위치에 아무 값을 넣어주고 시작하였다.

 

 

로봇이 이동하는 위치에 다른 로봇에 이미 있는지 검사하기 위해 2차원 int 배열에 로봇의 번호를 저장해놓는다.

배열의 (x, y)에 있는 로봇의 번호를 저장하고, 로봇이 없다면 초기값인 0이다.

예를 들어 로봇 2번이 (5, 4)에 있다면  check[5][4] = 2 이다.

이동후에는 기존 위치의 값을 다시 0으로 만들어주고 새로 이동한 곳에 로봇 번호를 다시 저장한다.

 

 

이후에는 입력받은 로봇 번호, 명령, 반복 횟수를 이용하여 시뮬레이션해주면 된다. 벽에 부딪히거나 다른 로봇에 부딪히는 경우는 F명령으로 이동했을 때만 발생하므로 F명령일 때만 검사해주면 된다.

 

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
#include <iostream>
#include <vector>
using namespace std;
 
int A, B, N, M;
 
int check[102][102];
 
//북, 동, 남, 서
int dx[] = { -1,0,1,0 };
int dy[] = { 0,1,0,-1 };
 
struct Robot {
    int x;
    int y;
    int dir;
    Robot(int a, int b, int c) {
        x = a;
        y = b;
        dir = c;
    }
};
 
vector<Robot> vt;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> A >> B;
    cin >> N >> M;
 
    int x, y, dir;
    char d;
 
    //index 1부터 시작하기위해 아무 값 넣어줌
    vt.push_back(Robot(-1, -1, -1));
 
    for (int i = 1; i <= N; i++) {
        cin >> x >> y >> d;
 
        if (d == 'N') //N을 입력받으면 E방향으로 설정.
            dir = 1;
        else if (d == 'E') //E면 S방향으로 설정.
            dir = 2;
        else if (d == 'S') //S면 W방향으로 설정.
            dir = 3;
        else
            dir = 0; //W면 N방향으로 설정
 
        vt.push_back(Robot(x, y, dir));
        check[x][y] = i;
    }
 
 
    int num;
    char order;
    int orderCnt;
 
    int crashWall = 0; //벽에 부딪힌 로봇 번호를 저장
    int lastRobot = 0; //다른 로봇에 부딪힌 현재 이동 로봇을 저장
    int crashRobot = 0; //현재 이동중인 로봇이 부딪힌 다른 로봇의 번호를 저장
 
 
    while (M--) {
        cin >> num >> order >> orderCnt;
 
        //잘못된 명령이 발생해서 벽이나 로봇이 부딪힌 경우 넘어가서 입력만 계속 받는다.
        if (crashWall || crashRobot) continue;
 
        x = vt[num].x;
        y = vt[num].y;
        dir = vt[num].dir;
 
        //명령 반복 횟수만큼 반복
        while (orderCnt--) {
            if (order == 'L') {
                //왼쪽 90도 회전
                dir = (dir + 3) % 4;
                vt[num].dir = dir;
            }
            else if (order == 'R') {
                //오른쪽 90도 회전
                dir = (dir + 1) % 4;
                vt[num].dir = dir;
            }
            else if (order == 'F') {
                
                //이전 위치 비워준다.
                check[x][y] = 0;
 
                x = x + dx[dir];
                y = y + dy[dir];
 
                if (x < 1 || y < 1 || x > A || y > B) {
                    //벽에 부딪힘
                    crashWall = num;
                    break;
                }
                else if (check[x][y] != 0) {
                    //로봇에 부딪힘
                    lastRobot = num;
                    crashRobot = check[x][y];
                    break;
                }
                else {
                    //이동
                    vt[num].x = x;
                    vt[num].y = y;
                    check[x][y] = num;
                }
            }
 
        }
    }
 
 
    if (crashWall) cout << "Robot " << crashWall << " crashes into the wall" << '\n';
    else if (crashRobot) cout << "Robot " << lastRobot << " crashes into robot " << crashRobot << '\n';
    else cout << "OK" << '\n';
 
 
    return 0;
}
Colored by Color Scripter
  
저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 17090. 미로 탈출하기  (0) 2020.05.01
[BOJ] 16401. 과자 나눠주기  (2) 2020.04.29
[BOJ] 10711. 모래성  (0) 2020.04.27
[BOJ] 2866. 문자열 잘라내기  (0) 2020.04.21
[BOJ] 5427. 불  (0) 2020.04.19

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

 

10711번: 모래성

문제 명우와 친구들은 여름방학을 맞이하여 해변가에 놀러가기로 했다. 이번에 여행을 떠난 해수욕장의 이름은 ALPS(Awsome Land & Poor Sea)이다. 해변가에서 수영복을 입은 미녀들에게 관심이 많은 원철이와는 달리 명우는 해변가의 모래에 더 관심이 많다. 해변가의 모래는 무한한 것들을 만들 수 있는 가능성을 내포하고 있다. 또한 이렇게 만들어진 작품이 파도에 의해 사라지는 모습은, 마치 자신이 가장 빛날 수 있는 시간을 알고 스스로 아름답게

www.acmicpc.net

처음에 무너질 모래성을 매번 검사해서 없애주는 방식으로 구현했다가 시간 초과가 났다.

 

 

어차피 나중에 무너질 모래성들은 이전에 무너진 모래성들이 없어져서 영향을 받으므로 무너지는 모래성의 위치로부터

주변을 탐색하여 또 무너질 모래성이 있는지 찾아주고 다시 없애주는 방식으로 구현하면 문제를 해결할 수 있다.

 

 

 

  1. 입력을 받는다.
  2. 입력 받은 배열에서 튼튼함이 9보다 작은 모든 모래성을 검사하여 자기 격자 주변의 8방향에 모래성이 쌓여있지 않은 부분의 개수가 자기 모래성의 튼튼함보다 많거나 같은 경우 무너질 것이므로 큐에 넣어주고 배열에도 방문 표시를 해준다. 이때 다음에 무너져야 하는 모래성이 영향을 받으므로 바로 ' . '으로 바꿔주면 안 된다.
  3. 파도가 한 번 칠 때의 무너질 모래성들을 모두 큐에 넣었다면, ' . '으로 바꿔준다. 그리고 무너질 모래성 주변의 8방향을 다시 검사하여 또 무너질 모래성이 있다면 큐에 넣어준다. 이때 기존에 큐에 들어가 있던 모래성의 개수(큐 사이즈)만큼만 탐색을 진행하여, 탐색이 끝난다면 파도치는 횟수를 증가시킨다.
  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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include <iostream>
#include <queue>
using namespace std;
 
int h, w;
char map[1000][1000];
bool visit[1000][1000];
int dx[] = { -1,-1,-1,0,0,1,1,1 };
int dy[] = { -1,0,1,-1,1,-1,0,1 };
 
queue<pair<int, int>> q;
 
int check(int x, int y) {
    int cnt = 0;
    int nx, ny;
 
    //자기 격자 주변의 8방향을 검사하여 모래성이 없다면 cnt증가
    for (int k = 0; k < 8; k++) {
        nx = x + dx[k];
        ny = y + dy[k];
        if (map[nx][ny] == '.') cnt++;
    }
 
    return cnt;
}
 
void solve() {
    queue<pair<int, int> > tmp;
    int time = 0;
 
    int x, y;
 
    //더이상 무너질 모래성이 없을때까지 반복
    while (!q.empty()) {
        tmp = q;
 
        //이전에 무너질 모래성들을 없애준다.
        while (!tmp.empty()) {
            x = tmp.front().first;
            y = tmp.front().second;
            tmp.pop();
            map[x][y] = '.';
        }
 
        int qsize = q.size();
        while (qsize--) {
            x = q.front().first;
            y = q.front().second;
            q.pop();
 
            int nx, ny;
            for (int k = 0; k < 8; k++) {
                nx = x + dx[k];
                ny = y + dy[k];
 
                if (visit[nx][ny]) continue; //이미 체크함
                if (map[nx][ny] == '.') continue; //모래성이 아님
 
 
                //자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너진다.
                if (check(nx, ny) >= (map[nx][ny] - '0')) {
                    q.push(make_pair(nx, ny));
                    visit[nx][ny] = true;
                }
            }
        }
        //시간 증가
        time++;
    }
 
    cout << time << '\n';
}
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> h >> w;
    for (int i = 0; i < h; i++) cin >> map[i];
 
    int num, cnt;
    //무너질 모래의 위치를 큐에 넣는다.
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (map[i][j] == '.') continue;
 
            num = map[i][j] - '0';
            if (num == 9) continue; //튼튼함이 9이면 무너지지 않으므로 넘어간다
 
            //(i, j)칸 주변 8방향에 모래성이 쌓여있지 않은 부분의 개수
            cnt = check(i, j);
 
            //자기 모래성의 튼튼함보다 많거나 같은 경우 파도에 의해서 무너진다.
            if (cnt >= num) {
                q.push(make_pair(i, j));
                visit[i][j] = true;
            }
        }
    }
 
 
    solve();
 
    return 0;
}
htColored by Color Scripter
  

 

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 16401. 과자 나눠주기  (2) 2020.04.29
[BOJ] 2174. 로봇 시뮬레이션  (0) 2020.04.28
[BOJ] 2866. 문자열 잘라내기  (0) 2020.04.21
[BOJ] 5427. 불  (0) 2020.04.19
[BOJ] 18809. Gaaaaaaaaaarden  (0) 2020.03.23

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

 

2866번: 문자열 잘라내기

문제 R개의 행과 C개의 열로 이루어진 테이블이 입력으로 들어오게 됩니다. 이 테이블의 원소는 알파벳 소문자로 주어집니다. 각 테이블의 열을 위에서 아래로 읽어서 하나의 문자열을 만들 수 있습니다. 예제 입력에서 dobarz adatak 이 주어지는 경우 "da", "od", "ba", "at", "ra", "zk"와 같이 6개의 문자열들이 만들어지게 됩니다. 만약 가장 위의 행을 지워도 테이블의 열을 읽어서 문자열이 중복되지 않는다면, 가장 위의 행을

www.acmicpc.net

테이블의 행을 i-1번째까지 지운 상태에서 i번째행부터의 문자열을 검사한다고 했을 때, 동일한 문자열이 있다면 그 이후 문자열들도 중복이다. 예를 들어, abc와 abc가 중복이면 이후인 bc와 bc, c와 c가 중복이기 때문이다.

반대로 중복이 아니라면 i-1번째 행까지 지웠을 때에도 중복이 아니다. 그 이전에 중복이면 위와 같은 이유로 현재도 중복일 것이기 때문이다. 

 

 

이분 탐색으로 mid번째 행부터 시작하는 문자열(mid-1번째까지는 지워진 상태)을 검사하여 동일한 문자열이 발생한다면 mid 이전의 행을 탐색하고, 만약 동일한 문자열이 발생하지 않는다면 더 큰 값을 찾기 위해 mid이후의 행을 지웠을 때의 문자열들을 검사해서 정답을 구할 수 있다. 중복이 발생하지 않은 행 중 최댓값이 count값으로 정답이 된다.

 

 

문자열의 중복을 검사할 때에는 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
69
#include <iostream>
#include <string>
#include <set>
using namespace std;
 
int r, c;
int ans;
char table[1000][1000];
 
bool check(int start, int end) {
    set<string> s;
 
    for (int j = 0; j < c; j++) {
        string tmp;
        //start행부터 마지막행까지 읽어서 문자열을 만든다.
        for (int i = start; i <= end; i++) tmp += table[i][j];
 
        //set에 문자열이 존재한다면 바로 false를 리턴한다.
        if (s.find(tmp) == s.end())
            s.insert(tmp);
        else
            return false;
    }
 
    return true;
}
 
void binarySearch(int left, int right, int end) {
    if (left > right) return;
 
    int mid = (left + right) / 2;
 
    //mid번째 행부터 마지막 행까지의 문자열을 검사
    bool flag = check(mid, end);
    
    if (flag) {
        //동일한 문자열이 발생하지 않았다면 mid이후 부분을 검사
        
        //중복이 발생하지 않은 행 중 최댓값이 정답
        if (ans < mid) ans = mid;
        binarySearch(mid + 1, right, end);
    }
    else {
        //동일한 문자열이 발생했다면 mid 이전 부분을 검사
        binarySearch(left, mid - 1, end);
    }
 
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> table[i][j];
        }
    }
 
    ans = 0;
    
    //처음에 주어지는 테이블에는 열을 읽어서 문자열을 만들 때, 동일한 문자열이 존재하지 않음이 보장되므로 1번째 행부터 검사
    binarySearch(1, r - 1, r - 1);
    cout << ans << '\n';
 
    return 0;
}
Colored by Color Scripter
  

 

저작자표시

'BOJ' 카테고리의 다른 글

[BOJ] 2174. 로봇 시뮬레이션  (0) 2020.04.28
[BOJ] 10711. 모래성  (0) 2020.04.27
[BOJ] 5427. 불  (0) 2020.04.19
[BOJ] 18809. Gaaaaaaaaaarden  (0) 2020.03.23
[BOJ] 18808. 스티커 붙이기  (0) 2020.03.23

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

+ Recent posts

티스토리툴바