문제 링크 : https://www.acmicpc.net/problem/14890




문제 접근


1. 코드 작성을 편하게 하기 위해 2차원배열에 들어있는 값들을 한줄씩 살펴 볼때마다, 한줄을 1차원배열에 복사하여 지나갈 수 있는 길인지 체크하였다.


2. 체크하는 과정은 우선 한길에 속한 모든 칸의 높이가 같은지를 먼저 확인하고 만약 모든칸의 높이가 같다면 지나갈 수 있는 길로 판단하였다.


3. 이후엔 복사해놓은 배열을 앞에서 뒤로 탐색하며 인접 칸의 높이 차이를 구하였다.

높이의 차이가 2이상이면 지나갈수 없는길로 판단했다.

높이의 차이가 1이라면 차이가 나기 시작한 점부터 l만큼의 길이에 있는 점들이 같은 높이 인지 판단하였다.

만약 l만큼길이의 점들중 다른 높이가 하나라도 있다면 지나갈수 없는 길로 판단했다.

l만큼의 길이의 점들이 모두 같은 높이라면 오른쪽아래로 내려가는 경사로를 놓았다.

경사로를 놓는 것은 bool 배열을 이용하여 해당 인덱스의 값을 true로 바꾸어 주었다.


4. 3번과 마찬가지로 뒤에서 앞으로 탐색하며 지나갈수있는길인지 경사로를 놓을수 있는지를 판단한 후 왼쪽 아래로 내려가는 경사로를 놓았다.

왼쪽아래로 내려가는 경사로도 마찬가지로 다른 bool 배열을 이용하여 체크하였다.


5. 오른쪽 아래로 내려가는 경사로와 왼쪽 아래로 내려가는 경사로를 체크한 두 배열을 비교하며 경사로가 겹치는 부분이 있으면 지나갈수 없는길로 판단하였다.

겹치는 부분이 없으면 지나갈 수 있는길로 판단하였다.


6. 모든 길에 대해 1번~5번의 과정을 거치며 지나갈수 있는길인지 없는 길인지를 판단하며 지나갈수 있는 길의 경우 그 수를 세어 마지막에 출력하였다.





소스코드


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
#include <iostream>
 
using namespace std;
 
int map[100][100];
int clonline[100];
int n, l, cnt = 0;
 
bool rgsr[100];
bool lgsr[100];
 
bool isSameHeight(int s, int e) {
    for (int i = s; i < e; i++) {
        if (clonline[i] != clonline[i + 1]) {
            return false;
        }
    }
    return true;
}
 
void inspection(int ay, int ax, int by, int bx) {
    // 클론 배열 복사
    if (ay == by) {
        // y좌표 같음 가로로 봄.
        for (int i = 0; i < n; i++) {
            clonline[i] = map[ay][i];
        }
    }
    else if (ax == bx) {
        // x좌표 같음 세로로 봄.
        for (int i = 0; i < n; i++) {
            clonline[i] = map[i][ax];
        }
    }
 
    // 1. 높이 다 같은 경우
    if (isSameHeight(0, n - 1)) {
        cnt++;
        return;
    }
 
    // 경사로 배열 초기화
    for (int i = 0; i < n; i++) {
        rgsr[i] = false;
        lgsr[i] = false;
    }
 
    int differ;
 
    //앞에서 뒤로 탐색
    for (int i = 0; i < n-1; i++) {
        differ = clonline[i] - clonline[i + 1];
        if (differ > 1) {
            return;
        }
        else if (differ == 1) {
            int e = i + l;
            if (e >= n)
                return;
 
            if (isSameHeight(i + 1, e)) {
                // 경사로 설치
                for (int j = i + 1; j <= e; j++) {
                    rgsr[j] = true;
                }
            }
            else {
                return;
            }
        }
    }
 
    //뒤에서 앞으로 탐색
    for (int i = n - 1; i > 0; i--) {
        differ = clonline[i] - clonline[i - 1];
        if (differ > 1)
            return;
        else if (differ == 1) {
            int s = i - l;
            if (s < 0)
                return;
 
            if (isSameHeight(s, i - 1)) {
                //경사로 설치
                for (int j = s; j <= i - 1; j++) {
                    lgsr[j] = true;
                }
            }
            else {
                return;
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        if (rgsr[i] && lgsr[i]) {
            return;
        }
    }
 
    cnt++;
 
}
 
int main()
{
    cin >> n >> l;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];
 
 
    for (int i = 0; i < n; i++) {
        inspection(i, 0, i, n - 1);
    }
 
    for (int j = 0; j < n; j++) {
        inspection(0, j, n - 1, j);
    }
 
    cout << cnt;
}
cs




저작자표시

'Algorithm > 백준' 카테고리의 다른 글

백준 15683번 감시  (0) 2019.04.30
백준 14889번 스타트와 링크  (0) 2019.04.28
백준 14503번 로봇 청소기  (0) 2019.04.27
백준 14888번 연산자 끼워넣기  (0) 2019.04.27
백준 14500번 테트로미노  (0) 2019.04.26


문제 링크 : https://www.acmicpc.net/problem/14503



시뮬레이션 문제였다.


문제에서 하라는대로 해서 풀었다.


청소한 칸은 지도에 2로 표시하고 청소가 종료된 후 마지막에 값이 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
#include <iostream>
 
using namespace std;
 
int n, m, y, x, drec, cnt=0;
int map[50][50];
int dy[] = { -1,0,1,0 };
int dx[] = { 0,1,0,-1 };
 
void clean() {
    while (true) {
        //1.현재 위치 청소
        map[y][x] = 2;
        //모든방향 봄.
        int ny, nx;
        bool clearPossible = false;
        for (int i = 0; i < 4; i++) {
            ny = y + dy[i];
            nx = x + dx[i];
            if (map[ny][nx] == 0)
                clearPossible = true;
        }
        // 청소불가
        if (clearPossible == false) {
            int rd = (drec + 2) % 4;
            ny = y + dy[rd];
            nx = x + dx[rd];
            //벽
            if (map[ny][nx] == 1) {
                break;
            }
            else {
                y = ny;
                x = nx;
                continue;
            }
        }
 
        else {
            //왼쪽 봄.
            if (drec == 0)
                drec = 3;
            else
                drec--;
            
            ny = y + dy[drec];
            nx = x + dx[drec];
 
            if (map[ny][nx] == 0) {
                y = ny;
                x = nx;
            }
            continue;
        }
    }
}
 
int main()
{
    cin >> n >> m >> y >> x >> drec;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> map[i][j];
 
    clean();
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 2)
                cnt++;
        }
    }
 
    cout << cnt;
 
}
cs


저작자표시

'Algorithm > 백준' 카테고리의 다른 글

백준 14889번 스타트와 링크  (0) 2019.04.28
백준 14890번 경사로  (0) 2019.04.28
백준 14888번 연산자 끼워넣기  (0) 2019.04.27
백준 14500번 테트로미노  (0) 2019.04.26
백준 13460번 구슬 탈출 2  (0) 2019.03.08


문제 링크 : https://www.acmicpc.net/problem/14888



완전탐색으로 풀었다.


가능한 연산자 조합의 경우를 모두 계산해보고 그 중 최소값과 최대값을 체크하여 마지막에 출력하였다.




소스코드


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 <iostream>
 
using namespace std;
 
int a[11];
int oper[4];
int minNum = 1000000001, maxNum = -1000000001;
 
int oprtn(int fir, int oper, int sec) {
    switch (oper)
    {
    case 0:
        return fir + sec;
    case 1:
        return fir - sec;
    case 2:
        return fir * sec;
    case 3:
        if (fir < 0) {
            int tmp = fir * -1;
            tmp = tmp / sec;
            return tmp * -1;
        }
        else {
            return fir / sec;
        }
    default:
        break;
    }
}
 
void recur(int fir, int secIndex, int toPick) {
    if (toPick == 0) {
        if (fir > maxNum)
            maxNum = fir;
        if (fir < minNum)
            minNum = fir;
        return;
    }
 
    for (int i = 0; i < 4; i++) {
        if (oper[i] == 0) continue;
 
        oper[i]--;
        int ans = oprtn(fir, i, a[secIndex]);
        recur(ans, secIndex + 1, toPick - 1);
        oper[i]++;
    }
}
 
int main()
{
    int n;
 
    cin >> n;
 
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    for (int i = 0; i < 4; i++) {
        cin >> oper[i];
    }
 
    recur(a[0], 1, n - 1);
 
    cout << maxNum << "\n" << minNum;
}
cs



저작자표시

'Algorithm > 백준' 카테고리의 다른 글

백준 14890번 경사로  (0) 2019.04.28
백준 14503번 로봇 청소기  (0) 2019.04.27
백준 14500번 테트로미노  (0) 2019.04.26
백준 13460번 구슬 탈출 2  (0) 2019.03.08
백준 2407 조합  (0) 2019.02.26

 

문제 링크 : https://www.acmicpc.net/problem/14500

 

14500번: 테트로미노

폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 꼭짓점끼리 연결되어 있어야 한다. 즉, 변과 꼭짓점이 맞닿아있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누어

www.acmicpc.net

 

 

처음엔 대칭도 가능하다는 것을 못보고 맞왜틀 하고있었는데

대칭이 가능하단걸 알고 추가 해주니 맞았다.

 

문제 접근

1. 3차원배열에 가능한 테트노미로의 모양을 다 저장해놓았다.

 ttrmn[19][5][2]

- 19 : 가능한 도형의 모양 9개

- 5 : 블럭4개 + 그 도형의 세로, 가로길이를 넣어줄 마지막 인덱스 1개

- 2 : y좌표, x좌표

 

2. 반복문으로 모든 경우의 수의 합을 구하고 그중 가장 큰 값 출력하였다.

 

 

 

소스코드

#include <iostream>

 

using namespace std;

 

int n, m, max_sum = 0;

int map[500][500];

 

int ttrmn[19][5][2] = {

 

{ {0,0}, {0,1}, {1,0}, {1,1}, {2,2} },

 

{ {0,0}, {0,1}, {0,2}, {0,3}, {1,4} },

{ {0,0}, {1,0}, {2,0}, {3,0}, {4,1} },

 

{ {0,0}, {1,0}, {2,0}, {2,1}, {3,2} },

{ {0,0}, {0,1}, {0,2}, {1,0}, {2,3} },

{ {0,0}, {0,1}, {1,1}, {2,1}, {3,2} },

{ {0,2}, {1,0}, {1,1}, {1,2}, {2,3} },

 

{ {0,1}, {1,1}, {2,0}, {2,1}, {3,2} },

{ {0,0}, {1,0}, {1,1}, {1,2}, {2,3} },

{ {0,0}, {0,1}, {1,0}, {2,0}, {3,2} },

{ {0,0}, {0,1}, {0,2}, {1,2}, {2,3} },

 

{ {0,0}, {1,0}, {1,1}, {2,1}, {3,2} },

{ {0,1}, {0,2}, {1,0}, {1,1}, {2,3} },

{ {0,1}, {1,0}, {1,1}, {2,0}, {3,2} },

{ {0,0}, {0,1}, {1,1}, {1,2}, {2,3} },

 

{ {0,0}, {0,1}, {0,2}, {1,1}, {2,3} },

{ {0,1}, {1,0}, {1,1}, {2,1}, {3,2} },

{ {0,1}, {1,0}, {1,1}, {1,2}, {2,3} },

{ {0,0}, {1,0}, {1,1}, {2,0}, {3,2} }

 

};

 

int main()

{

    cin >> n >> m;

    

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            cin >> map[i][j];

        }

    }

    

    for (int t = 0; t < 19; t++) {

        for (int i = 0; i < n - ttrmn[t][4][0] + 1; i++) {

            for (int j = 0; j < m - ttrmn[t][4][1] + 1; j++) {

                int sum = 0;

                for (int k = 0; k < 4; k++) {

                    sum += map[i + ttrmn[t][k][0]][j + ttrmn[t][k][1]];

                }

                if (max_sum < sum)

                    max_sum = sum;

            }

        }

    }

 

    cout << max_sum;

 

}

'Algorithm > 백준' 카테고리의 다른 글

백준 14503번 로봇 청소기  (0) 2019.04.27
백준 14888번 연산자 끼워넣기  (0) 2019.04.27
백준 13460번 구슬 탈출 2  (0) 2019.03.08
백준 2407 조합  (0) 2019.02.26
백준 10974 모든 순열  (0) 2019.02.25


문제 링크 : https://www.acmicpc.net/problem/13460



삼성 기출문제이다.


구현하는게 좀 짜증나는 문제였다.


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
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
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
 
int m, n;
char map[10][10];
//상오하왼
int dy[] = { -1, 0, 1, 0 };
int dx[] = { 0, 1, 0, -1 };
 
vector<int> v;
 
// 정상졸료 0, 탈출 1
int move(int drt, int& ny, int& nx, int othy, int othx) {
    bool enemy = false;
    if (drt == 0) {
        //위로 이동
        if (othx == nx && othy < ny) {
            enemy = true;
        }
        for (int i = ny - 1; i > 0; i--) {
            if (enemy) {
                if (i == othy) break;
            }
            if (map[i][nx] != '.') {
                break;
            }
            ny--;
        }
        if (map[ny - 1][nx] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    else if (drt == 1) {
        //오른쪽으로 이동
        if (othy == ny && othx > nx) {
            enemy = true;
        }
        for (int i = nx + 1; i < m - 1; i++) {
            if (enemy) {
                if (i == othx) break;
            }
            if (map[ny][i] != '.') {
                break;
            }
            nx++;
        }
        if (map[ny][nx + 1] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    else if (drt == 2) {
        //아래로 이동
        if (othx == nx && othy > ny) {
            enemy = true;
        }
        for (int i = ny + 1; i < n - 1; i++) {
            if (enemy) {
                if (i == othy) break;
            }
            if (map[i][nx] != '.') {
                break;
            }
            ny++;
        }
        if (map[ny + 1][nx] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    else if (drt == 3) {
        //왼쪽으로 이동
        if (othy == ny && othx < nx) {
            enemy = true;
        }
        for (int i = nx - 1; i > 0; i--) {
            if (enemy) {
                if (i == othx) break;
            }
            if (map[ny][i] != '.') {
                break;
            }
            nx--;
        }
        if (map[ny][nx - 1] == 'O') {
            ny = -1;
            nx = -1;
            return 1;
        }
        else
            return 0;
    }
    return 3;
}
 
void go(int ry, int rx, int by, int bx, int direction, int cnt) {
    if (cnt == 10) return;
 
    for (int d = 0; d < 4; d++) {
        int wry = ry;
        int wrx = rx;
        int wby = by;
        int wbx = bx;
 
        if (direction != -1 && (direction + 2) % 4 == d) continue;
        int nry = ry + dy[d];
        int nrx = rx + dx[d];
        bool rvs = false;
        
        if (d == 0) {
            if (rx == bx && by < ry) rvs = true;
        }
        else if (d == 1) {
            if (ry == by && bx > rx) rvs = true;
        }
        else if (d == 2) {
            if (rx == bx && by > ry) rvs = true;
        }
        else if (d == 3) {
            if (ry == by && bx < rx) rvs = true;
        }
 
        if (rvs) {
            //b움직, r움직, 탈출인지 확인, 재귀
            int br = move(d, wby, wbx, wry, wrx);
            int rr = move(d, wry, wrx, wby, wbx);
            if (br == 1) continue;
            if (br == 0 && rr == 1) {
                v.push_back(cnt + 1);
                continue;
            }
            go(wry, wrx, wby, wbx, d, cnt + 1);
        }
        else {
            //r움직, b움직, 탈출인지 확인, 재귀
            int rr = move(d, wry, wrx, wby, wbx);
            int br = move(d, wby, wbx, wry, wrx);
            if (br == 1) continue;
            if (br == 0 && rr == 1) {
                v.push_back(cnt + 1);
                continue;
            }
            go(wry, wrx, wby, wbx, d, cnt + 1);
        }
    }
 
}
 
 
int main()
{
    int fRy, fRx, fBy, fBx;
    char t;
    cin >> n >> m;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> t;
            if (t == 'R') {
                fRy = i;
                fRx = j;
                map[i][j] = '.';
            }
            else if (t == 'B') {
                fBy = i;
                fBx = j;
                map[i][j] = '.';
            }
            else {
                map[i][j] = t;
            }
        }
    }
 
    go(fRy, fRx, fBy, fBx, -1, 0);
 
    if (v.size() == 0) cout << -1;
    else {
        int minr = 9999;
        for (int i = 0; i < v.size(); i++) {
            minr = min(minr, v[i]);
        }
        cout << minr;
    }
}
cs



'Algorithm > 백준' 카테고리의 다른 글

백준 14888번 연산자 끼워넣기  (0) 2019.04.27
백준 14500번 테트로미노  (0) 2019.04.26
백준 2407 조합  (0) 2019.02.26
백준 10974 모든 순열  (0) 2019.02.25
백준 1764 듣보잡  (0) 2019.02.20


문제 링크 : https://www.acmicpc.net/problem/2407


대충보고 쉬운 문제인줄 알고 생각없이 코딩하고 테케를 넣어봤는데 결과값이 너무 커서 자료형 범위를 넘어가서 답이 안나왔다.


할수 없이 오랜만에 이클립스를 켰다. 자바 만세.


BigInteger를 사용한 것 빼고는 뭐 그냥 조합공식을 코드로 옮기기만 하면 되는 문제이다.



아래는 소스코드이다.


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
import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        int n, m;
        BigInteger bm, bj;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        
        bm = facto(n-m).multiply(facto(m));
        bj = facto(n);
        
        System.out.println(bj.divide(bm));
    }
    
    public static BigInteger facto(int a) {
        if(a==0) return BigInteger.valueOf(1);
        
        BigInteger ret = new BigInteger("1");
        for(int i=1; i<=a; i++) {
            ret = ret.multiply(BigInteger.valueOf(i));
        }
        return ret;
    }
}
cs






'Algorithm > 백준' 카테고리의 다른 글

백준 14500번 테트로미노  (0) 2019.04.26
백준 13460번 구슬 탈출 2  (0) 2019.03.08
백준 10974 모든 순열  (0) 2019.02.25
백준 1764 듣보잡  (0) 2019.02.20
백준 1779번 비숍  (0) 2019.01.29


문제 링크 : https://www.acmicpc.net/problem/10974


n이 작아서 재귀를 이용한 완전탐색으로 풀었다.




1. n을 입력받고,  pair<int, bool>가 들어갈 벡터 v를 선언하고 1~n까지 총 n개의 수를 벡터에 넣어주었다.

( pair의 first : 1~n까지의 정수 / pair의 second : 해당 정수를 선택했는지 여부 )


2. 재귀를 이용하여 완전탐색을 하였다.

for문으로 벡터v를 훑으면서 선택하지 않은 수가 있다면 선택하여 picked 벡터에 추가.

n개의 수를 모두 선택하였다면 벡터 picked 출력하고 함수 종료.




아래는 소스코드이다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
using namespace std;
 
int n;
vector<pair<int, bool>> v;
vector<int> picked;
 
void pick(int toPick) {
    if (toPick == 0) {
        for (int i = 0; i < picked.size(); i++) {
            cout << picked[i] << " ";
        }
        cout << "\n";
        return;
    }
 
    for (int i = 0; i < n; i++) {
        if (v[i].second) continue;
 
        v[i].second = true;
        picked.push_back(v[i].first);
        pick(toPick - 1);
        v[i].second = false;
        picked.pop_back();
    }
}
 
int main()
{
    cin >> n;
 
    for(int i = 1; i <= n; i++) {
        v.push_back(make_pair(i, false));
    }
 
    pick(n);
}
cs





'Algorithm > 백준' 카테고리의 다른 글

백준 13460번 구슬 탈출 2  (0) 2019.03.08
백준 2407 조합  (0) 2019.02.26
백준 1764 듣보잡  (0) 2019.02.20
백준 1779번 비숍  (0) 2019.01.29
백준 9663번 N-Queen  (0) 2019.01.28


문제 링크 : https://www.acmicpc.net/problem/1764


두개의 벡터에 입력받아 하나하나 다 비교를 해보면 시간초과가 날것같아서 맵을 사용하여 풀었다.


1. 듣도못한 사람의 목록을 입력받아 map에 저장한다.

2. 보도못한 사람들의 목록을 입력받으며 map에 존재하는 이름인지 체크하고 존재한다면 벡터에 추가해준다.

3. 벡터를 sort해주고 벡터길이와 내용을 출력해준다.


맵은 처음 사용해봐서 너무 익숙치않았다.

다 풀고나서 같이 공부하는 동생의 소스를 봤는데 굳이 맵을 사용하지 않고 훨씬더 쉽게 풀어놨다.

비효윻적으로 푼것같지만 안써본 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
#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
 
vector<string> v;
 
int main()
{
    int a, b;
    map<string, int> m;
    map<string, int>::iterator iter;
 
    cin >> a >> b;
 
    for (int i = 0; i < a; i++) {
        string tmp;
        cin >> tmp;
        m.insert(make_pair(tmp, 0));
    }
 
    for (int i = 0; i < b; i++) {
        string tmp;
        cin >> tmp;
        iter = m.find(tmp);
        if (iter != m.end()) {
            v.push_back(iter->first);
        }
    }
 
    cout << v.size() << "\n";
 
    sort(v.begin(), v.end());
 
    for (int i = 0; i < v.size(); i++) {
        cout << v[i] << "\n";
    }
}
cs









'Algorithm > 백준' 카테고리의 다른 글

백준 2407 조합  (0) 2019.02.26
백준 10974 모든 순열  (0) 2019.02.25
백준 1779번 비숍  (0) 2019.01.29
백준 9663번 N-Queen  (0) 2019.01.28
백준 1325번 효율적인 해킹  (0) 2019.01.23

+ Recent posts

티스토리툴바