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

 

1037번: 약수

첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되�

www.acmicpc.net

 

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
#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
 
// 수학 - 약수
 
int nSize = 0;
std::vector<int> vec, primes;
 
bool is_prime(int param)
{
    for (int i = 2; i * i < param; ++i)
    {
        if (param % 2 == 0)
        {
            return false;
        }
    }
    return true;
}
 
void input()
{
    std::cin >> nSize;
    for (int i = 0; i < nSize; ++i)
    {
        int input;
        std::cin >> input;
        vec.push_back(input);
        /*if (is_prime(input))
        {
            primes.push_back(input);
        }*/
    }
    std::sort(vec.begin(), vec.end());
 
}
 
// 1 2 4 5 10 20
// 1 3 6 12
// 1 5 10 15
// 1 3 7 9 21 63
// 1 3 
 
// 1 2 7 14
 
int solve()
{
    return 0;
}
 
int main()
{
    input();
    //std::cout << solve();
    std::cout << vec.front() * vec.back();
    return 0;
}
 
 cs

 

방심을 너무 안한게 문제라고 해야할까

 

아는것도 틀리는 슬픈 사람이 되지는 말자

저작자표시

'알고리즘' 카테고리의 다른 글

백준 1620 : 나는야 포켓몬 마스터 이다솜  (0) 2020.08.19
koi : combinations(S)  (0) 2020.08.18
백준 1316 : 그룹단어체커  (0) 2020.08.14
백준 2798 : 블랙잭  (0) 2020.08.14
백준 1568 : 새  (0) 2020.08.14

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

 

1316번: 그룹 단어 체커

그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때�

www.acmicpc.net

 

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 <iostream>
#include <string>
#include <array>
 
std::array<std::string, 100> arr;
int N, ans;
bool alphabet[26];
 
void input()
{
    std::cin >> N;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> arr[i];
    }
}
 
void solve()
{
    for (int i = 0; i < N; ++i)
    {
        bool flag = true;
        for (int j = 0; j < 26; ++j)
        {
            alphabet[j] = false;
        }
 
        for (int j = 0; j < arr[i].size(); ++j)
        {
            if (alphabet[arr[i][j] - 'a'] == false)
            {
                alphabet[arr[i][j] - 'a'] = true;
                continue;
            }
            if (arr[i][j] != arr[i][j - 1] && alphabet[arr[i][j] - 'a'] == true)
            {
                flag = false;
                break;
            }
        }
        if (flag == true)
        {
            ++ans;
        }
    }
}
 
void output()
{
    std::cout << ans;
}
 
int main()
{
    input();
    solve();
    output();
}
 cs

일일 PS 프로젝트

저작자표시

'알고리즘' 카테고리의 다른 글

koi : combinations(S)  (0) 2020.08.18
백준 1037 : 약수  (0) 2020.08.14
백준 2798 : 블랙잭  (0) 2020.08.14
백준 1568 : 새  (0) 2020.08.14
백준 13460 : 구슬 탈출 2  (0) 2020.08.11

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

 

2798번: 블랙잭

문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 ��

www.acmicpc.net

 

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
#include <iostream>
 
int N, M, ans;
int card[100];
int visited[100];
 
void input()
{
    std::cin >> N >> M;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> card[i];
    }
}
 
void dfs(int sum, int toPick)
{
    if (toPick == 0)
    {
        if (M >= sum)
        {
            ans = ans < sum ? sum : ans;
        }
        return;
    }
 
    for (int i = 0; i < N; ++i)
    {
        if (visited[i] == false)
        {
            visited[i] = true;
            dfs(sum + card[i], toPick - 1);
            visited[i] = false;
        }
    }
}
 
void output()
{
    std::cout << ans;
}
 
int main()
{
    input();
    dfs(0, 3);
    output();
    return 0;
}
 cs

일일 PS 프로젝트

저작자표시

'알고리즘' 카테고리의 다른 글

백준 1037 : 약수  (0) 2020.08.14
백준 1316 : 그룹단어체커  (0) 2020.08.14
백준 1568 : 새  (0) 2020.08.14
백준 13460 : 구슬 탈출 2  (0) 2020.08.11
백준 2178 : 미로 탐색  (0) 2020.08.10

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

 

1568번: 새

N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현��

www.acmicpc.net

 

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
#include <iostream>
 
unsigned long long N;
int ans;
 
void input()
{
    std::cin >> N;
}
 
void solve()
{
    unsigned long long song = 1;
    while (N != 0)
    {
        if (N < song)
        {
            song = 1;
        }
        N -= song;
        ++song;
        ++ans;
    }
}
 
void output()
{
    std::cout << ans;
}
 
int main()
{
    input();
    solve();
    output();
    return 0;
}
 cs

 

일일 PS 프로젝트

저작자표시

'알고리즘' 카테고리의 다른 글

백준 1316 : 그룹단어체커  (0) 2020.08.14
백준 2798 : 블랙잭  (0) 2020.08.14
백준 13460 : 구슬 탈출 2  (0) 2020.08.11
백준 2178 : 미로 탐색  (0) 2020.08.10
백준 1697 : 숨바꼭질  (0) 2020.08.10

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

 

13460번: 구슬 탈출 2

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B'

www.acmicpc.net

 

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 <queue>
 
struct coord
{
    int y;
    int x;
}R, B;
 
int N, M;
 
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
 
char board[11][11];
 
void input()
{
    std::cin >> N >> M;
    for (int y = 1; y <= N; ++y)
    {
        for (int x = 1; x <= M; ++x)
        {
            std::cin >> board[y][x];
            if (board[y][x] == 'R')
            {
                board[y][x] = '.';
                R = { y, x };
            }
            if (board[y][x] == 'B')
            {
                board[y][x] = '.';
                B = { y, x };
            }
        }
    }
}
 
void print(int ry, int rx, int by, int bx)
{
    std::cout << '\n';
    for (int y = 1; y <= N; ++y)
    {
        for (int x = 1; x <= M; ++x)
        {
            if (y == ry && x == rx)
            {
                std::cout << 'R' << ' ';
            }
            else if (y == by && x == bx)
            {
                std::cout << 'B' << ' ';
            }
            else
            {
                std::cout << board[y][x] << ' ';
            }
        }
        std::cout << '\n';
    }
}
 
int solve()
{
    std::queue<std::pair<std::pair<coord, coord>, std::pair<int, int>>> bfs;
    bfs.push({ { R, B }, { 1, 4 } });
    int ans = 0;
    while (bfs.empty() == false)
    {
        coord rPos = bfs.front().first.first;
        coord bPos = bfs.front().first.second;
        int cnt = bfs.front().second.first;
        int flag = bfs.front().second.second;
        bfs.pop();
        if (cnt > 10)
        {
            continue;
        }
 
        //print(0, 0, 0, 0);
        //std::cout << "----------------------------------------------------------\n";
        for (int i = 0; i < 4; ++i)
        {
            if (flag != 4 && flag % 2 == 0 && i % 2 == 0)
            {
                continue;
            }
            if (flag != 4 && flag % 2 == 1 && i % 2 == 1)
            {
                continue;
            }
            bool chk = false;
            coord rNext = rPos;
            coord bNext = bPos;
            int rCnt = 0;
            int bCnt = 0;
            while (board[rNext.y][rNext.x] == '.')
            {
                rNext.y += dy[i];
                rNext.x += dx[i];
                ++rCnt;
            }
            rNext.y -= dy[i];
            rNext.x -= dx[i];
 
            while (board[bNext.y][bNext.x] == '.')
            {
                bNext.y += dy[i];
                bNext.x += dx[i];
                ++bCnt;
            }
//             if (board[bNext.y][bNext.x] == 'O')
//             {
//                 continue;
//             }
            bNext.y -= dy[i];
            bNext.x -= dx[i];
            if (bNext.y == rNext.y && bNext.x == rNext.x && board[rNext.y + dy[i]][rNext.x + dx[i]] == 'O')
            {
                continue;
            }
 
            if (rNext.y == bNext.y && rNext.x == bNext.x)
            {
                coord* ptr = nullptr;
                if (rCnt < bCnt)
                {
                    ptr = &bNext;
                }
                else
                {
                    ptr = &rNext;
                }
                ptr->y -= dy[i];
                ptr->x -= dx[i];
            }
 
            if (board[rNext.y + dy[i]][rNext.x + dx[i]] == 'O')
            {
                return cnt;
            }
            if (board[bNext.y + dy[i]][bNext.x + dx[i]] == 'O')
            {
                continue;
            }
            //print(rNext.y, rNext.x, bNext.y, bNext. x);
            if (rNext.y != rPos.y || rNext.x != rPos.x || bNext.y != bPos.y || bNext.x != bPos.x)
            {
                bfs.push({ {rNext, bNext}, { cnt + 1, i } });
            }
        }
    }
    return -1;
}
 
int main()
{
    input();
    std::cout << solve();
    return 0;
}
 cs

 

테스트케이스를 돌려보기 전에 먼저

 

실수한 부분이 없는지(오타 등), 내 생각대로 코드가 흘러가는지

 

먼저 생각해보고

 

그 뒤에도 틀린다면 예외를 생각해보자

저작자표시

'알고리즘' 카테고리의 다른 글

백준 2798 : 블랙잭  (0) 2020.08.14
백준 1568 : 새  (0) 2020.08.14
백준 2178 : 미로 탐색  (0) 2020.08.10
백준 1697 : 숨바꼭질  (0) 2020.08.10
koi : 별그리기  (0) 2020.08.07

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

 

2178번: 미로 탐색

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

www.acmicpc.net

 

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
#include <iostream>
#include <string>
#include <vector>
#include <queue>
 
struct coord
{
    int y;
    int x;
};
 
int N, M;
int dy[4] = { 1, 0, -1, 0 };
int dx[4] = { 0, 1, 0, -1 };
 
int ans = 987654321;
int maze[100][100];
 
void input()
{
    std::cin >> N >> M;
    for (int y = 0; y < N; ++y)
    {
        for (int x = 0; x < M; ++x)
        {
            scanf("%1d", &maze[y][x]);
            maze[y][x] = -maze[y][x];
        }
    }
}
 
void pf()
{
    std::cout << '\n';
    for (int y = 0; y < N; ++y)
    {
        for (int x = 0; x < M; ++x)
        {
            std::cout << maze[y][x] << ' ';
        }
        std::cout << '\n';
    }
}
 
bool border_check(int y, int x)
{
    return (-1 < y && -1 < x) && (y < N&& x < M);
}
 
void solve()
{
    std::queue<coord> bfsQueue;
    bfsQueue.push({ 0, 0 });
    maze[0][0] = 1;
    while (bfsQueue.empty() == false)
    {
        //pf();
        coord pos = bfsQueue.front();
        if (pos.y == N - 1 && pos.x == M - 1)
        {
            return;
        }
        bfsQueue.pop();
 
        for (int i = 3; i >= 0; --i)
        {
            if (border_check(dy[i] + pos.y, dx[i] + pos.x) && maze[dy[i] + pos.y][dx[i] + pos.x] != 0)
            {
                //if (maze[dy[i] + pos.y][dx[i] + pos.x] == -1 || maze[pos.y][pos.x] < maze[dy[i] + pos.y][dx[i] + pos.x])
                if (maze[dy[i] + pos.y][dx[i] + pos.x] == -1)
                {
                    maze[dy[i] + pos.y][dx[i] + pos.x] = maze[pos.y][pos.x] + 1;
                    bfsQueue.push({ dy[i] + pos.y, dx[i] + pos.x });
                }
            }
        }
    }
}
 
 
void output()
{
    std::cout << maze[N - 1][M - 1];
}
 
int main()
{
    input();
    solve();
    output();
    return 0;
}
 cs

 

 

BFS는 너비 우선이기 때문에 겉에서부터 얕게 깐다는걸 필히 마음속에 새겨놔야 한다

 

즉, 목적된 값을 찾는다면 그 값이 바로 어떠한 거리의 최솟값인 경우가 태반이기 때문에

 

다른 조건이 구태여 의미가 없어지는 경우가 생긴다

 

69번 라인의 저 주석처럼..

저작자표시

'알고리즘' 카테고리의 다른 글

백준 1568 : 새  (0) 2020.08.14
백준 13460 : 구슬 탈출 2  (0) 2020.08.11
백준 1697 : 숨바꼭질  (0) 2020.08.10
koi : 별그리기  (0) 2020.08.07
백준 1110 : 더하기 사이클  (0) 2020.08.07

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

 

1697번: 숨바꼭질

문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가

www.acmicpc.net

 

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
#include <iostream>
#include <algorithm>
#include <queue>
 
typedef int sec;
typedef int pos;
 
int N, K;
int minimumSec = 987654321;
 
int visited[200001];
 
struct state
{
    int pos;
    int sec;
};
 
void input()
{
    std::cin >> N >> K;
}
 
void solve()
{
    if (N == K)
    {
        minimumSec = 0;
        return;
    }
    std::queue<state> bfs;
    int dest = K;
 
    bfs.push({ N, 0 });
    while (bfs.empty() == false)
    {
        state curr = bfs.front();
        visited[curr.pos] = 1;
        bfs.pop();
 
        if (curr.pos > dest)
        {
            int restSec = curr.sec + curr.pos - dest;
            minimumSec = minimumSec > restSec ? restSec : minimumSec;
            continue;
        }
        if (curr.sec > dest - N)
        {
            minimumSec = minimumSec > curr.sec ? curr.sec : minimumSec;
            return;
        }
 
        if (dest == curr.pos * 2 || dest == curr.pos + 1 || dest == curr.pos - 1)
        {
            minimumSec = minimumSec > curr.sec + 1 ? curr.sec + 1 : minimumSec;
            return;
        }
        else
        {
            if (visited[curr.pos * 2] == 0)
            {
                bfs.push({ curr.pos * 2, curr.sec + 1 });
            }
            if (visited[curr.pos + 1] == 0)
            {
                bfs.push({ curr.pos + 1, curr.sec + 1 });
            }
            if (curr.pos > 0)
            {
                if (visited[curr.pos - 1] == 0)
                {
                    bfs.push({ curr.pos - 1, curr.sec + 1 });
                }
            }
        }
    }
}
 
void solve_dp()
{
}
 
void output()
{
    std::cout << minimumSec;
}
 
int main()
{
    input();
    solve();
    output();
    return 0;
}
 cs

 

BFS의 뭐 개념이야 그렇다 쳐도

 

핵심은 이미 접근한 곳에 대해 어떻게 배제하는가

 

visited 변수를 안쓰고 하려면 어떤 방식이 필요할까...

저작자표시

'알고리즘' 카테고리의 다른 글

백준 13460 : 구슬 탈출 2  (0) 2020.08.11
백준 2178 : 미로 탐색  (0) 2020.08.10
koi : 별그리기  (0) 2020.08.07
백준 1110 : 더하기 사이클  (0) 2020.08.07
koi : 숫자 뒤집기(s)  (0) 2020.08.04

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

 

5567번: 결혼식

문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

www.acmicpc.net

 

항상 느끼는거지만

 

디버깅을 할 때에는 내가 생각한 대로 코드가 진행되는지

 

예상과는 다른 연산을 하지는 않는지

 

집요하게 살펴봐야 할 필요가 있다.

 

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
#include <iostream>
 
int friends[510][510];
bool visited[510];
int ans;
int n, m;
 
void input()
{
    std::cin >> n >> m;
    for (int i = 0; i < m; ++i)
    {
        int to, from;
        std::cin >> from >> to;
        friends[from][to] = 1;
        friends[to][from] = 1;
    }
    visited[1] = true;
}
 
void solve_dfs(int stk, int currPos)
{
    if (stk >= 2)
    {
        return;
    }
     for (int x = 1; x <= n; ++x)
    {
        if (friends[currPos][x] == 1)
        {
            if (visited[x] == false)
            {
                visited[x] = true;
                ++ans;
            }
            solve_dfs(stk + 1, x);
        }
    }
}
 
 
int main()
{
    std::cin.tie(0);
    std::cin.sync_with_stdio(false);
    std::cout.tie(0);
    std::cout.sync_with_stdio(false);
    input();
    solve_dfs(0, 1);
    std::cout << ans;
    return 0;
}
cs

 

 

저작자표시

'알고리즘' 카테고리의 다른 글

koi : 숫자 뒤집기(s)  (0) 2020.08.04
관계기반 알고리즘의 설계  (0) 2020.08.04
백준 1722 : 순열의 순서  (0) 2020.07.30
백준 8979 : 올림픽  (0) 2020.07.23
백준 1764 : 듣보잡  (0) 2020.07.22

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

 

8979번: 올림픽

입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 �

www.acmicpc.net

 

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 <algorithm>
 
struct country
{
    int gold;
    int silver;
    int copper;
    int number;
}countrys[1010];
 
int N, K;
 
bool cmp(country& first, country& second)
{
    if (first.gold == second.gold)
    {
        if (first.silver == second.silver)
        {
            return first.copper > second.copper;
        }
        else
        {
            return first.silver > second.silver;
        }
    }
    else
    {
        return first.gold > second.gold;
    }
}
 
void input()
{
    int nation;
    std::cin >> N >> K;
    for (int i = 1; i <= N; ++i)
    {
        std::cin >> countrys[i].number >> countrys[i].gold >> countrys[i].silver >> countrys[i].copper;
    }
}
 
void solve()
{
    std::sort(countrys + 1, countrys + N + 1, cmp);
    for (int i = 1; i <= N; ++i)
    {
        //std::cout << countrys[i].number << ' ' << countrys[i].gold << ' ' << countrys[i].silver << ' ' << countrys[i].copper << '\n';
        if (countrys[i].number == K)
        {
            int ans = i;
            while (countrys[ans].gold == countrys[ans - 1].gold &&
                countrys[ans].silver == countrys[ans - 1].silver &&
                countrys[ans].copper == countrys[ans - 1].copper)
            {
                --ans;
            }
            std::cout << ans;
            break;
        }
    }
}
 
int main()
{
    input();
    solve();
    return 0;
}
 cs

 

정렬을 열심히 배웁시다 정렬은 나의 원수

 

strick week ordering에 주의합시다

저작자표시

'알고리즘' 카테고리의 다른 글

백준 5567 : 결혼식  (0) 2020.08.04
백준 1722 : 순열의 순서  (0) 2020.07.30
백준 1764 : 듣보잡  (0) 2020.07.22
백준 9517 : 아이 러브 크로아티아  (0) 2020.07.21
백준 14890 : 경사로  (0) 2020.07.17

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

 

1764번: 듣보잡

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. ��

www.acmicpc.net

 

해싱 해싱 해싱을할까요

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
#include <iostream>
#include <unordered_map>
#include <string>
#include <vector>
#include <algorithm>
 
int N, M;
std::unordered_map<std::string, int> unknownList;
 
std::vector<std::string> ans;
 
void input()
{
    std::cin >> N >> M;
    std::string input;
    for (int i = 0; i < N; ++i)
    {
        std::cin >> input;
        unknownList[input] += 1;
    }
    for (int i = 0; i < M; ++i)
    {
        std::cin >> input;
        unknownList[input] += 2;
        if (unknownList[input] == 3)
        {
            ans.push_back(input);
        }
    }
}
 
int main()
{
    std::cin.tie(0);
    std::cin.sync_with_stdio(false);
    std::cout.tie(0);
    std::cout.sync_with_stdio(false);
    input();
    std::cout << ans.size() << '\n';
    std::sort(ans.begin(), ans.end());
    for (auto& it : ans)
    {
        std::cout << it << '\n';
    }
    return 0;
}
 cs

C++ unordered map의 성능은 날이 갈수록 좋아지고 있다고 한다...

저작자표시

'알고리즘' 카테고리의 다른 글

백준 1722 : 순열의 순서  (0) 2020.07.30
백준 8979 : 올림픽  (0) 2020.07.23
백준 9517 : 아이 러브 크로아티아  (0) 2020.07.21
백준 14890 : 경사로  (0) 2020.07.17
백준 1094 : 막대기  (0) 2020.07.16

+ Recent posts

티스토리툴바