'알고리즘 문제풀이/프로그래머스' 카테고리의 글 목록 (5 Page)

알고리즘 문제풀이/프로그래머스

[C++] 프로그래머스 - 튜플

2020. 5. 7. 19:30

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

프로그래머스

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

programmers.co.kr

<풀이>

1. 주어진 문자열을 잘 쪼개어서 각각 그룹으로 만든다.

2. 그룹의 크기가 가장 작은 것부터 겹쳐지지 않은 원소들을 결과 벡터에 저장한다.

<해법>

1. 문자열을 쪼개어서 그룹화 시키는 방법.

=> 문자열의 처음과 끝의 '{', '}'은 필요가 없으므로 제외하였습니다. 제외하면 {1,2,3},{1,2},... 이런식으로 그룹들의 형식으로만 남게됩니다.

이렇게 되면 그룹은 모두 '{' 을 시작으로 해서 '}' 으로 끝납니다.

또한 각각의 원소들은 ',' 로 구분되어있습니다.

따라서 위와같은 방법으로 문자열을 분리합니다.

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

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
bool visited[100001];
 
bool cmp(vector<int> o1, vector<int> o2) {
    return o1.size() < o2.size();
}
 
vector<int> solution(string s) {
    
    vector<int> answer;
 
    //그룹화된 숫자들 저장
    vector<vector<int>> grp;
 
    int m = s.length();
 
    //시작과 끝의 '{','}' 필요 X
    int index = 1;
 
    while (true) {
 
        //종료조건
        if (index == m - 1) {
            break;
        }
 
        //'{'부터 그룹
        if (s[index] == '{') {
 
            vector<int> v;
            string tmp = "";
            int tmpInt;
 
            index++;
 
            while (true) {
 
                //'}'까지 그룹 
                if (s[index] == '}') {
                    tmpInt = stoi(tmp);
                    v.push_back(tmpInt);
                    break;
                }
 
                //','까지 숫자변환 후 저장
                if (s[index] == ',') {
                    tmpInt = stoi(tmp);
                    v.push_back(tmpInt);
                    tmp = "";
                }
                //숫자 저장
                else {
                    tmp += s[index];
                }
 
                index++;
            }
            //'{  }'안에 있던 원소들 그룹화해서 담아주기
            grp.push_back(v);
        }
        index++;
    }
 
    //그룹의 크기에 따라 정렬
    sort(grp.begin(), grp.end(), cmp);
 
    //answer에 겹치지 않은 원소들 넣어주기
    for (int i = 0; i < grp.size(); i++) {
        for (int j = 0; j < grp[i].size(); j++) {
            if (!visited[grp[i][j]]) {
                visited[grp[i][j]] = true;
                answer.push_back(grp[i][j]);
            }
        }
    }
    return answer;
}
 

문자열 파싱에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 불량 사용자 (0)	2020.05.15
[C++] 프로그래머스 - 오픈채팅방 (0)	2020.05.07
[C++] 프로그래머스 - 크레인 인형뽑기 게임 (0)	2020.05.07
[C++] 프로그래머스 - 외벽 점검 (0)	2020.05.07
[C++] 프로그래머스 - 기둥과 보 설치 (0)	2020.05.07

[C++] 프로그래머스 - 크레인 인형뽑기 게임

2020. 5. 7. 19:23

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

프로그래머스

programmers.co.kr

<풀이>

1. 주어지는 명령을 그대로 구현하여 수행한다.

2. 없어진 인형의 개수를 반환한다.

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 <iostream>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;
 
int map[31][31];
stack<int> basket;
 
int solution(vector<vector<int>> board, vector<int> moves) {
 
    int answer = 0;
    
    memset(map, 0, sizeof(map));
 
    int m = board.size();
    int n = moves.size();
 
    //보드 -> 맵
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            map[i][j] = board[i][j];
        }
    }
 
    //뽑기 명령 수행
    for (int i = 0; i < n; i++) {
 
        //명령의 열 선택
        int line = moves[i] - 1;
 
        //열의 가장 위에서부터 아래로 탐색
        for (int j = 0; j < m; j++) {
            
            //인형을 발견하였을 경우, 인형 뽑기
            if (map[j][line] != 0) {
 
                //바구니가 비어있으면 인형 담기
                if (basket.empty()) {
                    basket.push(map[j][line]);
                }
                //바구니가 비어있지 않을 경우
                else {
                    //뽑은 인형과 바구니 제일 위의 인형이 같을 경우 없애주고, answer+2
                    if (map[j][line] == basket.top()) {
                        basket.pop();
                        answer += 2;
                    }
                    //같지 않다면 바구니에 담기
                    else {
                        basket.push(map[j][line]);
                    }
                }
 
                //맵에서 인형 없애기
                map[j][line] = 0;
                break;
            }
        }
    }
    return answer;
}
 

시뮬레이션에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 오픈채팅방 (0)	2020.05.07
[C++] 프로그래머스 - 튜플 (0)	2020.05.07
[C++] 프로그래머스 - 외벽 점검 (0)	2020.05.07
[C++] 프로그래머스 - 기둥과 보 설치 (0)	2020.05.07
[C++] 프로그래머스 - 블록 이동하기 (0)	2020.05.07

[C++] 프로그래머스 - 외벽 점검

2020. 5. 7. 19:19

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

프로그래머스

programmers.co.kr

<풀이>

1. 친구를 어디서 부터 보낼 것인지, 어떤 친구부터 보낼 것인지의 경우를 모두 탐색한다.

2. 가장 적게 사용한 친구의 수를 반환한다.

<해법>

1. 친구를 어디서 부터 보낼 것인지

=> 위의 조건에서 친구는 시계방향, 반시계방향 모두 움직일 수 있다고 합니다. 하지만 결국 친구의 수를 가장 적게 사용하려면, 똑같은 방향으로 친구가 탐색하지 못한 다음 취약지점부터 다른 친구를 보내주어야 합니다.

이렇게 되면, 원형으로 나와있는 취약지점이 직선의 경우로 바뀌게 됩니다.

예제 1을 예로들면, (1 5 6 10), (5 6 10 1), (6 10 1 5), (10 1 5 6) 따라서 4가지 경우만 탐색하면 됩니다.

또한, 위의 4가지 경우를 쉽게 탐색하기 위해 맨 앞의 숫자가 뒤로 가면서 숫자 n을 더해주면 직선의 경우가 됩니다.

예제 1을 예로들면, (1 5 6 10), (5 6 10 13), (6 10 13 17), (10 13 17 18) 가 됩니다.

2. 어떤 친구부터 보낼 것인지

=> 친구들이 갈 수 있는 거리가 모두 다르고, 취약 지점마다의 거리가 어떻게 될지 모르니 모든 가짓수를 다 해보아야합니다. 따라서 next_permutation을 사용하였습니다.

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

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int solution(int n, vector<int> weak, vector<int> dist) {
 
    int answer = -1;
 
    //next_permutation을 사용하기 위한 정렬
    sort(dist.begin(), dist.end());
 
    //원형탐색 weak.size()만큼 반복
    for (int i = 0; i < weak.size(); i++) {
 
        //취약지점 순환
        int tmp = weak[0] + n;
        for (int j = 1; j < weak.size(); j++) {
            weak[j - 1] = weak[j];
        }
        weak[weak.size() - 1] = tmp;
 
        //친구들 배치
        do {
 
            //w : 취약지점 index, d : 친구들 index
            int w = 0;
            int d = 0;
 
            //친구 한명이 갈 수 있는 취약지점 까지 모두 탐색
            for (d = 0; d < dist.size(); d++) {
                int fin = weak[w] + dist[d];
                while (fin >= weak[w]) {
                    w++;
                    if (w == weak.size()) {
                        break;
                    }
                }
                if (w == weak.size()) {
                    break;
                }
            }
 
            //모든 취약지점이 탐색 되었다면, 가장 적게 친구를 사용한 결과 저장
            if (w == weak.size()) {
                if (answer == -1 || d + 1 < answer) {
                    answer = d + 1;
                }
            }
 
        } while (next_permutation(dist.begin(), dist.end()));
    }
    return answer;
}
 

백트래킹에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 튜플 (0)	2020.05.07
[C++] 프로그래머스 - 크레인 인형뽑기 게임 (0)	2020.05.07
[C++] 프로그래머스 - 기둥과 보 설치 (0)	2020.05.07
[C++] 프로그래머스 - 블록 이동하기 (0)	2020.05.07
[C++] 프로그래머스 - 자물쇠와 열쇠 (0)	2020.05.07

[C++] 프로그래머스 - 기둥과 보 설치

2020. 5. 7. 19:14

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

프로그래머스

programmers.co.kr

<풀이>

1. 입력으로 주어지는 명령어를 해독하여 기둥과 보를 설치하거나 지운다.

2. 모든 명령어를 수행하고 결과를 저장한다.

<해법>

1. 기둥과 보를 설치하거나 지우는 방법.

(1) 기둥과 보를 설치하는 방법

설치하는 방법은 문제에 나온 조건에 맞게 정확히 구현합니다.

(2) 기둥과 보를 지우는 방법

지우는 방법은 먼저 그 건축물을 map에서 지웁니다. 지운 후 건축물과 관련이 있는 다른 건축물이 설치될 수 있는 지를 확인합니다. 설치될 수 있는지를 확인할 때, 미리 만들어 놓은 설치 함수들을 사용하면 편리합니다.

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
char map[2][102][102];
 
bool canBuildPillar(int n, int x, int y) {
    //기둥이 바닥 위에 있을 경우
    if (x == 0) {
        return true;
    }
    //기둥이 다른 기둥 위에 있을 경우
    if (x - 1 >= 0 && map[0][x - 1][y] == 'p') {
        return true;
    }
    //기둥이 왼쪽 보의 끝 위에 있을 경우
    if (y - 1 >= 0 && map[1][x][y - 1] == 'b') {
        return true;
    }
    //기둥이 오른쪽 보의 끝 위에 있을 경우
    if (map[1][x][y] == 'b') {
        return true;
    }
    return false;
}
 
bool canBuildBo(int n, int x, int y) {
    //보의 왼쪽 끝 부분이 기둥 위에있을 경우
    if (x - 1 >= 0 && map[0][x - 1][y] == 'p') {
        return true;
    }
    //보의 오른쪽 끝 부분이 기둥 위에있을 경우
    if (x - 1 >= 0 && y + 1 <= n && map[0][x - 1][y + 1] == 'p') {
        return true;
    }
    //보의 양쪽 끝이 다른 보와 동시에 연결되어 있을 경우
    if (y - 1 >= 0 && y + 1 <= n && map[1][x][y - 1] == 'b' && map[1][x][y + 1] == 'b') {
        return true;
    }
    return false;
}
 
bool canDeletePillar(int n, int x, int y) {
 
    //기둥을 지운다
    map[0][x][y] = '0';
 
    //기둥 위에 있는 다른 기둥이 지을 수 있는지 확인
    if (x + 1 <= n && map[0][x + 1][y] == 'p') {
        if (!canBuildPillar(n, x + 1, y)) {
            return false;
        }
    }
    //기둥 위에 오른쪽으로 걸쳐있는 보가 지을 수 있는지 확인
    if (x + 1 <= n && map[1][x + 1][y] == 'b') {
        if (!canBuildBo(n, x + 1, y)) {
            return false;
        }
    }
    //기둥 위에 왼쪽으로 걸쳐있는 보가 지을 수 있는지 확인
    if (x + 1 <= n && y - 1 >= 0 && map[1][x + 1][y - 1] == 'b') {
        if (!canBuildBo(n, x + 1, y - 1)) {
            return false;
        }
    }
 
    return true;
}
 
bool canDeleteBo(int n, int x, int y) {
 
    //보를 지운다
    map[1][x][y] = '0';
 
    //보 오른쪽 끝 위에 있는 기둥이 지을 수 있는지 확인
    if (y + 1 <= n && map[0][x][y + 1] == 'p') {
        if (!canBuildPillar(n, x, y + 1)) {
            return false;
        }
    }
    //보 왼쪽 끝 위에 있는 기둥이 지을 수 있는지 확인
    if (map[0][x][y] == 'p') {
        if (!canBuildPillar(n, x, y)) {
            return false;
        }
    }
    //보 오른쪽에 있는 다른 보가 지을 수 있는지 확인
    if (y + 1 <= n && map[1][x][y + 1] == 'b') {
        if (!canBuildBo(n, x, y + 1)) {
            return false;
        }
    }
    //보 왼쪽에 있는 다른 보가 지을 수 있는지 확인
    if (y - 1 >= 0 && map[1][x][y - 1] == 'b') {
        if (!canBuildBo(n, x, y - 1)) {
            return false;
        }
    }
    return true;
}
 
vector<vector<int>> solution(int n, vector<vector<int>> build_frame) {
    
    vector<vector<int>> answer;
 
    memset(map, '0', sizeof(map));
 
    for (int i = 0; i < build_frame.size(); i++) {
 
        int y = build_frame[i][0];
        int x = build_frame[i][1];
        int shape = build_frame[i][2];
        int install = build_frame[i][3];
 
        //지우는 경우
        if (install == 0) {
            //기둥을 지우는 경우
            if (shape == 0) {
                //지울 수 있는지 확인
                if (!canDeletePillar(n, x, y)) {
                    map[0][x][y] = 'p';
                }
            }
            //보를 지우는 경우
            else {
                if (!canDeleteBo(n, x, y)) {
                    map[1][x][y] = 'b';
                }
            }
        }
        //짓는 경우
        else {
            //기둥을 짓는 경우
            if (shape == 0) {
                //지을 수 있는지 확인
                if (canBuildPillar(n, x, y)) {
                    map[0][x][y] = 'p';
                }
            }
            //보를 짓는 경우
            else {
                if (canBuildBo(n, x, y)) {
                    map[1][x][y] = 'b';
                }
            }
        }
    }
 
    //결과 저장
    for (int j = 0; j <= n; j++) {
        for (int i = 0; i <= n; i++) {
            for (int k = 0; k < 2; k++) {
                if (map[k][i][j] != '0') {
                    answer.push_back({ j,i,k });
                }
            }
        }
    }
    return answer;
}
 

구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 크레인 인형뽑기 게임 (0)	2020.05.07
[C++] 프로그래머스 - 외벽 점검 (0)	2020.05.07
[C++] 프로그래머스 - 블록 이동하기 (0)	2020.05.07
[C++] 프로그래머스 - 자물쇠와 열쇠 (0)	2020.05.07
[C++] 프로그래머스 - 괄호 변환 (0)	2020.05.04

[C++] 프로그래머스 - 블록 이동하기

2020. 5. 7. 19:08

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

프로그래머스

programmers.co.kr

<풀이>

1. 로봇이 이동 가능한 경우를 모두 계산한다.

2. 로봇이 가장 빠르게 도착지점에 도착한 경우의 시간을 출력한다.

저의 해법은 자신이 없습니다!!!ㅜㅜ

<해법>

기본적으로 BFS의 틀을 갖고있습니다.

BFS에서 중요한 것은 가능한 모든 경우를 탐색하는 것과, 불필요한 재탐색을 줄이는 것 이렇게 두 가지 입니다.

이 문제를 통해 위 두가지를 알아보겠습니다.

1) 가능한 모든 경우를 탐색하는 것

로봇이 이동하는 방법

- 위,아래,오른쪽,왼쪽 => 4가지

- A를 기준으로 90도 회전(2가지), B를 기준으로 90도 회전(2가지) => 4가지

총 8가지 입니다.

※ 블록 축으로 회전하는 구현이 정말 어려웠습니다. 저가 푼 방식을 어떻게든 그림으로 표현하고 싶었지만 정말 한계가 있었던 문제였습니다ㅜㅜ.

2) 불필요한 재탐색을 줄이는 것

로봇이 전에 탐색했던 위치에 놓이게 되는 경우를 배제해야 합니다.

만약, 방문 확인 배열을 visited[ ][ ][ ][ ] 이렇게 각각 두개의 로봇 좌표를 모두 사용할 경우 AB, BA와 같은 재탐색이 일어날 수 있습니다.

따라서, 저는 방문 확인 배열을 visited[A의 x좌표][A의 y좌표][누워있는 상태] 이렇게 하였습니다.

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
struct pos {
    int x, y;
};
 
struct robot {
    pos a, b;
    int flt;
    int cnt;
};
 
int di[] = { -1,0,1,0 };
int dj[] = { 0,1,0,-1 };
 
int up[4][2] = {
    {0,0},{0,1},{-1,0},{-1,1}
};
int down[4][2] = {
    {0,0},{0,1},{1,0},{1,1}
};
int Left[4][2] = {
    {0,0},{0,-1},{1,0},{1,-1}
};
int Right[4][2] = {
    {0,0},{0,1},{1,0},{1,1}
};
 
int N;
int map[100][100];
bool visited[100][100][2];
 
bool inner(pos a, pos b) {
    if (a.x < 0 || b.x < 0 || a.x >= N || b.x >= N || a.y < 0 || b.y < 0 || a.y >= N || b.y >= N) {
        return false;
    }
    return true;
}
 
int bfs(robot str) {
    queue<robot> q;
    q.push(str);
    visited[str.a.x][str.a.y][str.flt] = true;
 
    while (!q.empty()) {
        robot cur = q.front();
        q.pop();
 
        if ((cur.a.x == N-1 && cur.a.y == N-1) || (cur.b.x == N-1 && cur.b.y==N-1)) {
            return cur.cnt;
        }
 
        //4방향
        for (int i = 0; i < 4; i++) {
            robot nxt = cur;
 
            nxt.a.x += di[i];
            nxt.a.y += dj[i];
            nxt.b.x += di[i];
            nxt.b.y += dj[i];
 
            if (!inner(nxt.a, nxt.b)) {
                continue;
            }
 
            if (map[nxt.a.x][nxt.a.y] == 0 && map[nxt.b.x][nxt.b.y] == 0 && !visited[nxt.a.x][nxt.a.y][nxt.flt]) {
                nxt.cnt++;
                q.push(nxt);
                visited[nxt.a.x][nxt.a.y][nxt.flt] = true;
            }
        }
 
        //a,b축으로 회전
        //가로방향일 경우
        if (cur.flt == 0) {
            //위쪽으로 회전
            bool isAble = true;
            for (int i = 0; i < 4; i++) {
                int ni = cur.a.x + up[i][0];
                int nj = cur.a.y + up[i][1];
 
                if (ni < 0 || nj < 0 || ni >= N || nj >= N) {
                    isAble = false;
                }
                if (map[ni][nj] != 0) {
                    isAble = false;
                }
            }
 
            //위쪽으로 회전이 가능하다면, a축 b축을 기준으로 모두 위로 회전 가능
            if (isAble) {
                //a축 기준으로 위로 회전
                robot nxt = cur;
                nxt.flt = 1;
                nxt.a.x += -1;
                nxt.b.y += -1;
                nxt.cnt++;
 
                if (!visited[nxt.a.x][nxt.a.y][nxt.flt]) {
                    q.push(nxt);
                    visited[nxt.a.x][nxt.a.y][nxt.flt] = true;
                }
 
                //b축 기준으로 위로 회전
                nxt = cur;
                nxt.flt = 1;
                nxt.a.x += -1;
                nxt.a.y += 1;
                nxt.cnt++;
 
                if (!visited[nxt.a.x][nxt.a.y][nxt.flt]) {
                    q.push(nxt);
                    visited[nxt.a.x][nxt.a.y][nxt.flt] = true;
                }
            }
 
            //아래쪽으로 회전
            isAble = true;
            for (int i = 0; i < 4; i++) {
                int ni = cur.a.x + down[i][0];
                int nj = cur.a.y + down[i][1];
 
                if (ni < 0 || nj < 0 || ni >= N || nj >= N) {
                    isAble = false;
                }
                if (map[ni][nj] != 0) {
                    isAble = false;
                }
            }
 
            if (isAble) {
                robot nxt = cur;
                nxt.flt = 1;
                nxt.b.x += 1;
                nxt.b.y += -1;
                nxt.cnt++;
 
                if (!visited[nxt.a.x][nxt.a.y][nxt.flt]) {
                    q.push(nxt);
                    visited[nxt.a.x][nxt.a.y][nxt.flt] = true;
                }
 
                nxt = cur;
                nxt.flt = 1;
                nxt.a.y += 1;
                nxt.b.x += 1;
                nxt.cnt++;
 
                if (!visited[nxt.a.x][nxt.a.y][nxt.flt]) {
                    q.push(nxt);
                    visited[nxt.a.x][nxt.a.y][nxt.flt] = true;
                }
            }
        }
        else {
            //왼쪽으로 회전
            bool isAble = true;
            for (int i = 0; i < 4; i++) {
                int ni = cur.a.x + Left[i][0];
                int nj = cur.a.y + Left[i][1];
 
                if (ni < 0 || nj < 0 || ni >= N || nj >= N) {
                    isAble = false;
                }
                if (map[ni][nj] != 0) {
                    isAble = false;
                }
            }
 
            if (isAble) {
                robot nxt = cur;
                nxt.flt = 0;
                nxt.a.y += -1;
                nxt.b.x += -1;
                nxt.cnt++;
 
                if (!visited[nxt.a.x][nxt.a.y][nxt.flt]) {
                    q.push(nxt);
                    visited[nxt.a.x][nxt.a.y][nxt.flt] = true;
                }
 
                nxt = cur;
                nxt.flt = 0;
                nxt.a.x += 1;
                nxt.a.y += -1;
                nxt.cnt++;
 
                if (!visited[nxt.a.x][nxt.a.y][nxt.flt]) {
                    q.push(nxt);
                    visited[nxt.a.x][nxt.a.y][nxt.flt] = true;
                }
            }
 
            //오른쪽으로 회전
            isAble = true;
            for (int i = 0; i < 4; i++) {
                int ni = cur.a.x + Right[i][0];
                int nj = cur.a.y + Right[i][1];
 
                if (ni < 0 || nj < 0 || ni >= N || nj >= N) {
                    isAble = false;
                }
                if (map[ni][nj] != 0) {
                    isAble = false;
                }
            }
 
            if (isAble) {
                robot nxt = cur;
                nxt.flt = 0;
                nxt.b.x += -1;
                nxt.b.y += 1;
                nxt.cnt++;
 
                if (!visited[nxt.a.x][nxt.a.y][nxt.flt]) {
                    q.push(nxt);
                    visited[nxt.a.x][nxt.a.y][nxt.flt] = true;
                }
 
                nxt = cur;
                nxt.flt = 0;
                nxt.a.x += 1;
                nxt.b.y += 1;
                nxt.cnt++;
 
                if (!visited[nxt.a.x][nxt.a.y][nxt.flt]) {
                    q.push(nxt);
                    visited[nxt.a.x][nxt.a.y][nxt.flt] = true;
                }
            }
        }
 
    }
}
 
int solution(vector<vector<int>> board) {
 
    int answer = 0;
 
    N = board.size();
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = board[i][j];
        }
    }
 
    robot str = { {0,0},{0,1},0,0 };
 
    answer = bfs(str);
 
    return answer;
}
 

BFS에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 외벽 점검 (0)	2020.05.07
[C++] 프로그래머스 - 기둥과 보 설치 (0)	2020.05.07
[C++] 프로그래머스 - 자물쇠와 열쇠 (0)	2020.05.07
[C++] 프로그래머스 - 괄호 변환 (0)	2020.05.04
[C++] 프로그래머스 - 문자열 압축 (0)	2020.05.03

[C++] 프로그래머스 - 자물쇠와 열쇠

2020. 5. 7. 19:03

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

프로그래머스

programmers.co.kr

<풀이>

1. 주어진 자물쇠에 90도씩 회전한 4가지 열쇠를 처음부터 끝까지 맞추어 보면서 맞는 가능한 여부를 출력한다.

<해법>

1. 자물쇠에 열쇠를 맞추어 보는 방법.

=> 자물쇠를 자물쇠 크기의 9배인 백그라운드 배열의 가운데에 위치시킵니다. 그 후 키 배열을 백그라운드 처음부터 이동시키면서 자물쇠를 탐색합니다.

2. 자물쇠를 풀 수 있는 조건.

=> 자물쇠의 홈 갯수를 미리 파악하고, 탐색해 나가면서 열쇠의 돌기와 자물쇠의 홈이 만나는 갯수를 파악합니다. 이렇게 할 경우, 자물쇠의 홈은 전부 채워졌지만 돌기끼리 만나는 경우가 생길 수 있습니다. 이럴 경우 조건을 걸어주어 넘어가도록 진행하였습니다.

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

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
 
int KEY[20][20];
int LOCK[20][20];
int tmpKEY[20][20];
int background[60][60];
int M, N;
int hmCnt = 0;
 
//KEY배열 회전 함수
void rotate() {
    memcpy(tmpKEY, KEY, sizeof(tmpKEY));
 
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            KEY[j][M - 1 - i] = tmpKEY[i][j];
        }
    }
}
 
bool solution(vector<vector<int>> key, vector<vector<int>> lock) {
    bool answer = false;
 
    //키 배열의 가로,세로
    M = key.size();
    //자물쇠 배열의 가로,세로
    N = lock.size();
 
    //주어진 자료 배열에 담기
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < M; j++) {
            KEY[i][j] = key[i][j];
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            LOCK[i][j] = lock[i][j];
            //자물쇠 홈 개수 저장
            if (LOCK[i][j] == 0) {
                hmCnt++;
            }
        }
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            background[N + i][N + j] = LOCK[i][j];
        }
    }
 
    for (int i = 0; i < 4; i++) {
 
        //KEY 90도씩 회전
        rotate();
 
        //백그라운드 배열 전체 탐색
        for (int i = 0; i <= 2 * N; i++) {
            for (int j = 0; j <= 2 * N; j++) {
 
                //열쇠의 돌기와 자물쇠의 홈이 맞는 개수
                int cnt = 0;
                //열쇠의 돌기와 자물쇠의 돌기끼리 만나는 경우 판단
                bool isAble = true;
 
                for (int k = 0; k < M; k++) {
                    for (int l = 0; l < M; l++) {
 
                        //index
                        int x = i + k;
                        int y = j + l;
 
                        //영역을 벗어난 부분, 영향X
                        if (x < N || y < N || x >= 2 * N || y >= 2 * N ) {
                            continue;
                        }
 
                        //돌기끼리 만나는 경우 or 홈끼리 만나는 경우, 불가능
                        if (background[x][y] == KEY[k][l]) {
                            isAble = false;
                            break;
                        }
 
                        //열쇠의 돌기와 자물쇠의 홈끼리 만나는 경우, 개수++
                        if (background[x][y] == 0 && KEY[k][l] == 1) {
                            cnt++;
                        }
                    }
                }
 
                if (isAble) {
                    if (cnt == hmCnt) {
                        answer = true;
                        return answer;
                    }
                }
            }
        }
    }
    return answer;
}
 

구현과 시뮬레이션에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 외벽 점검 (0)	2020.05.07
[C++] 프로그래머스 - 기둥과 보 설치 (0)	2020.05.07
[C++] 프로그래머스 - 블록 이동하기 (0)	2020.05.07
[C++] 프로그래머스 - 괄호 변환 (0)	2020.05.04
[C++] 프로그래머스 - 문자열 압축 (0)	2020.05.03

[C++] 프로그래머스 - 괄호 변환

2020. 5. 4. 18:34

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

프로그래머스

programmers.co.kr

<풀이>

1. 입력받는 괄호 문자열을 올바른 괄호 문자열로 바꾼다.

2. 올바른 괄호 문자열로 바꾸는 방법을 주어진 그대로 구현한다.

3. 올바른 괄호 문자열을 반환한다.

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

#include <iostream>
#include <string>
using namespace std;
 
bool isRight(string u) {
    int cnt = 0;
    for (int i = 0; i < u.length(); i++) {
        if (u[i] == '(') {
            cnt++;
        }
        else {
            cnt--;
        }
 
        if (cnt < 0) {
            return false;
        }
    }
    return true;
}
 
string solution(string s) {
 
    string answer = "";
 
    //1.
    if (s == "") {
        return answer;
    }
 
    //2.
    string u = "", v = "";
    int cnt1 = 0;
    int cnt2 = 0;    
    for (int i = 0; i <= s.length(); i++) {
        if (s[i] == '(') {
            cnt1++;
        }
        else {
            cnt2++;
        }
        if (cnt1 == cnt2) {
            u = s.substr(0, i + 1);
            v = s.substr(i + 1);
            break;
        }
    }
 
    //3.
    if (isRight(u)) {
        //3-1.
        answer = u + solution(v);
        return answer;
    }
    //4.
    else {
        //4-1.
        string tmp = "";
        tmp += '(';
 
        //4-2.
        tmp += solution(v);
 
        //4-3.
        tmp += ')';
 
        //4-4.
        for (int i = 0; i < u.length(); i++) {
 
            if (i == 0 || i == u.length() - 1) {
                continue;
            }
 
            if (u[i] == '(') {
                tmp += ')';
            }
            else {
                tmp += '(';
            }
        }
        answer = tmp;
 
        //4-5.
        return answer;
    }
}
 

구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 외벽 점검 (0)	2020.05.07
[C++] 프로그래머스 - 기둥과 보 설치 (0)	2020.05.07
[C++] 프로그래머스 - 블록 이동하기 (0)	2020.05.07
[C++] 프로그래머스 - 자물쇠와 열쇠 (0)	2020.05.07
[C++] 프로그래머스 - 문자열 압축 (0)	2020.05.03

[C++] 프로그래머스 - 문자열 압축

2020. 5. 3. 19:43

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

프로그래머스

programmers.co.kr

<풀이>

1. 주어진 문자열 맨 앞에서 부터 한 글자, 두 글자씩 잘라보면서 가장 짧게 압축된 문자열의 길이를 출력한다.

<해법>

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

#include <iostream>
#include <string>
using namespace std;
 
int solution(string s) {
 
    int answer = 1;
 
    //주어진 문자열 길이
    int sLength = s.length();
 
    //1칸,2칸 ... 길이의 절반만큼 문자 자르기 반복
    for (int i = 1; i <= sLength / 2; i++) {
 
        //최종 문자열 보관
        string tmp = "";
 
        //처음 비교 문자열, 반복된 갯수
        string cmp = s.substr(0, i);
        int cnt = 1;
 
        //문자열 처음부터 끝까지 시행
        for (int j = i; j <= sLength; j += i) {
 
            //현재 문자열
            string cur = s.substr(j, i);
 
            //현재 문자열과 비교 문자열과 비교
            //현재 문자열과 비교 문자열이 같다면
            if (cmp == cur) {
                cnt++;
            }
            //현재 문자열과 비교 문자열이 다르다면
            else {
                //이전에 반복된 문자열이 있다면 반복된 문자열 출력
                if (cnt > 1) {
                    tmp += (to_string(cnt) + cmp);
                    cnt = 1;
                }
                else {
                    tmp += cmp;
                }
                cmp = cur;
            }
        }
 
        //문자열 뒤에 남은 문자들
        if (sLength / i != 0) {
            tmp += s.substr((sLength / i) * i);
        }
 
        //결과 저장
        if (answer == 1 || tmp.length() < answer) {
            answer = tmp.length();
        }
    }
 
    return answer;
}
 

문자열과 구현에 대해 알아볼 수 있는 문제였습니다.

저작자표시

'알고리즘 문제풀이 > 프로그래머스' 카테고리의 다른 글

[C++] 프로그래머스 - 외벽 점검 (0)	2020.05.07
[C++] 프로그래머스 - 기둥과 보 설치 (0)	2020.05.07
[C++] 프로그래머스 - 블록 이동하기 (0)	2020.05.07
[C++] 프로그래머스 - 자물쇠와 열쇠 (0)	2020.05.07
[C++] 프로그래머스 - 괄호 변환 (0)	2020.05.04

PREV 1 2 3 4 5 NEXT

알고리즘 고수가 되기까지