'개발자의 기본기/알고리즘 문제' 카테고리의 글 목록 (2 Page)

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	10349	4540	3209	44.594%

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 숫자가 주어진다. 숫자 카드에 적혀있는 숫자는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 숫자가 적혀있는 경우는 없다.

셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 숫자에 대해서, 각 숫자가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 1

5
6 3 2 10 -10
8
10 9 -5 2 3 4 5 -10

예제 출력 1

1 0 0 1 1 0 0 1

<풀이과정>

고유한 숫자 M이 주어지기 때문에 먼저 상근이의 숫자 카드 집합을 만들고

거기서 개수를 세어 1개가 있으면 1을 출력하고 없으면 0을 출력하면 된다.

숫자에 따른 개수를 저장할 필요도 없기때문에 바로 출력해주면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<iostream>
#include<set>
using namespace std;
 
int main(){
    int N; // 상근이가 가진 숫자카드의 개수
    cin >> N;
    set<int> s; // 상근이가 가진 카드 집합 
 
    while(N--){
        int x;
        cin >> x;// 카드에 적힌 숫자 
        s.insert(x);// 카드를 집합에 추가 
    } 
    
    int M; // 판별할 숫자의 개수
    cin >> M;
 
    for(auto i=0;i<M;i++){
        int x;
        cin >> x;// 판별할 숫자
 
        cout << s.count(x) << " ";
    } 
 
    return 0;     
}
cs

'개발자의 기본기 > 알고리즘 문제' 카테고리의 다른 글

<백준 알고리즘> 2346번 풍선 터뜨리기 (0)	2020.09.26
<백준 알고리즘> 1406번 에디터 (1)	2020.09.26
<백준 알고리즘> 1764번 듣보잡 (0)	2020.09.26
<백준 알고리즘> 10824번 네 수 (0)	2020.09.26
<백준 알고리즘> 11721번 열개씩 출력하기 (0)	2020.09.26

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	6625	2540	1799	39.925%

문제

김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그 길이는 20 이하이다. N, M은 500,000 이하의 자연수이다.

출력

듣보잡의 수와 그 명단을 사전순으로 출력한다.

예제 입력 1

3 4
ohhenrie
charlie
baesangwook
obama
baesangwook
ohhenrie
clinton

예제 출력 1

2
baesangwook
ohhenrie

<풀이과정>

어렵지 않은 문제인데 생각지도 못한 곳에서 실수를 하는 바람에 의외로 고생을 좀 했다.

기본 아이디어는 듣지못한 사람들을 입력받아 배열로 만들고 보도 못한 사람들을 한명씩 입력하고 듣도못한 사람들 배열에서 있는지 확인하는 방식이다.

여기서 빠르게 배열을 탐색하기 위해 이분탐색함수 binary_search를 사용했는데 이분탐색 알고리즘은 찾을 사전역할을 하는 것을 반드시 정렬된 상태로 만들어주고 해줘야 한다는 것을 잊었다!

중복되는 것을 찾았으면 새로운 배열에 넣고 정렬 한 후 출력해주면 된다.

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>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
 
int main(){
    int N,M;
    cin >> N >> M;
    
    vector<string> v1(N);// 듣도못한 
     vector<string> l2;// 듣보잡  
    
    for(int i=0;i<N;i++){// 듣도못한 배열에 넣기 
        cin >> v1[i];
        //v1.push_back(a);
    } // 확인완료 잘들어갔음 
    sort(v1.begin(),v1.end()); //<-- 이분탐색은 반드시 정렬된 사전을 가지고 해야 의미가 있다.  
    string b;
 
    while(M--){// 보도못한 
        cin >> b;
        
        if(binary_search(v1.begin(),v1.end(),b)){
            l2.push_back(b);// 듣보잡에 넣는다
        }
    }
    sort(l2.begin(),l2.end());
    cout << l2.size() << "\n";
    
    for (auto x:l2){
        cout << x << "\n";
    }
 
    return 0;
}
 
Colored by Color Scripter
cs

'개발자의 기본기 > 알고리즘 문제' 카테고리의 다른 글

<백준 알고리즘> 1406번 에디터 (1)	2020.09.26
<백준 알고리즘> 10815번 숫자 카드 (0)	2020.09.26
<백준 알고리즘> 10824번 네 수 (0)	2020.09.26
<백준 알고리즘> 11721번 열개씩 출력하기 (0)	2020.09.26
<백준 알고리즘> 11720번 숫자의 합 (0)	2020.09.26

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	6915	2551	2149	37.199%

문제

네 자연수 A, B, C, D가 주어진다. 이 때, A와 B를 붙인 수와 C와 D를 붙인 수의 합을 구하는 프로그램을 작성하시오.

두 수 A와 B를 합치는 것은 A의 뒤에 B를 붙이는 것을 의미한다. 즉, 20과 30을 붙이면 2030이 된다.

입력

첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000)

출력

A와 B를 붙인 수와 C와 D를 붙인 수의 합을 출력한다.

예제 입력 1

10 20 30 40

예제 출력 1

< 풀이과정 >

문제를 자세히 살피지 않으면 런타임에러가 날 수 있다. (나도 처음에 그랬다...)

문제의 조건을 자세히 보면 각 수는 1,000,000 까지 입력이 가능하다.

ABCD모두 1,000,000이 입력된 경우에는 2,000,000 * 2,000,000 = 4,000,000,000,000 까지 최대값이 나올 수 있다.

따라서 알맞은 자료형을 사용해 줘야 한다.

문자열을 숫자형으로 바꾸는 함수는

int 형 = stoi

float형 = stof

double형 = stod

long long형 = stoll

.

즉 자료형의 앞글자를 따서 뒤에 붙여주면 된다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
#include <string>
using namespace std;
int main() {
    int a, b, c, d;
    cin >> a >> b >> c >> d;
 
    string s1 = to_string(a) + to_string(b); //a+b결합
    string s2 = to_string(c) + to_string(d); //c+d결합
 
    long long n1 = stoll(s1);
    long long n2 = stoll(s2);
 
    cout << n1 + n2 << '\n';
    return 0;
}
Colored by Color Scripter
cs

'개발자의 기본기 > 알고리즘 문제' 카테고리의 다른 글

<백준 알고리즘> 10815번 숫자 카드 (0)	2020.09.26
<백준 알고리즘> 1764번 듣보잡 (0)	2020.09.26
<백준 알고리즘> 11721번 열개씩 출력하기 (0)	2020.09.26
<백준 알고리즘> 11720번 숫자의 합 (0)	2020.09.26
<백준 알고리즘> 2839번 설탕배달 (0)	2020.09.26

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	23930	11924	10534	51.652%

문제

알파벳 소문자와 대문자로만 이루어진 길이가 N인 단어가 주어진다.

한 줄에 10글자씩 끊어서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 단어가 주어진다. 단어는 알파벳 소문자와 대문자로만 이루어져 있으며, 길이는 100을 넘지 않는다. 길이가 0인 단어는 주어지지 않는다.

출력

입력으로 주어진 단어를 열 개씩 끊어서 한 줄에 하나씩 출력한다. 단어의 길이가 10의 배수가 아닌 경우에는 마지막 줄에는 10개 미만의 글자만 출력할 수도 있다.

예제 입력 1

BaekjoonOnlineJudge

예제 출력 1

BaekjoonOn
lineJudge

예제 입력 2

OneTwoThreeFourFiveSixSevenEightNineTen

예제 출력 2

OneTwoThre
eFourFiveS
ixSevenEig
htNineTen

<풀이과정>

C++ 언어를 이용한 풀이

문자열 자료형과 getline함수를 사용해서 한 줄을 통째로 입력받는다.

입력받은 글자 수만큼 반복하여 출력하면서 10으로 나눠 떨어질 때마다 줄바꿈을 하여 10개씩 출력되도록한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<string>
#include<vector>
using namespace std;
 
int main() {
    string s;
    getline(cin, s);
 
    for (int i = 0; i < s.size(); i++) {
        cout << s[i];
        if ((i+1) % 10 == 0) {
            cout << '\n';
        }
    }
    cout << '\n';
    return 0;
}
Colored by Color Scripter
cs

C언어를 이용한 풀이

%10s를 이용하여 문자열을 입력 받을 때 10개씩 끊어서 입력되도록 한다.

끊어서 입력받은 것을 출력.

더이상 출력할 입력 값이 없으면 루프는 종료된다.

1
2
3
4
5
6
7
8
9
10
#include<cstdio>
using namespace std;
 
int main(){
    char s[101]; 
    while(scanf("%10s",s)==1){
        printf("%s\n",s);
    }
    return 0;
}
cs

둘다 정답

C언어를 사용한 코드가 역시 더 효율적이다.

'개발자의 기본기 > 알고리즘 문제' 카테고리의 다른 글

<백준 알고리즘> 10815번 숫자 카드 (0)	2020.09.26
<백준 알고리즘> 1764번 듣보잡 (0)	2020.09.26
<백준 알고리즘> 10824번 네 수 (0)	2020.09.26
<백준 알고리즘> 11720번 숫자의 합 (0)	2020.09.26
<백준 알고리즘> 2839번 설탕배달 (0)	2020.09.26

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	30488	12385	10846	44.608%

문제

N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다.

출력

입력으로 주어진 숫자 N개의 합을 출력한다.

예제 입력 1

1
1

예제 출력 1

예제 입력 2

5
54321

예제 출력 2

예제 입력 3

25
7000000000000000000000000

예제 출력 3

예제 입력 4

11
10987654321

예제 출력 4

<풀이과정>

scanf의 %1d 기능을 활용한다.

%와 d 사이에 숫자를 넣으면 해당 자리수 만큼 값을 입력받는다는 의미

12345를 입력하면 1,2,3,4,5 따로 따로 입력받아 각각 x로 할당한다.

그 값을 모두 더해서 sum에 저장하고 해당 값을 출력

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<cstdio>
using namespace std;
 
int main(){
    int n;
    scanf("%d",&n); // 숫자의 개수  
    int sum=0; // 합을 저장할 변수 
    
    for(int i=0; i<n;i++){
        int x;
        scanf("%1d",&x); // x의 정수를 한 자리씩 각각 입력 받는다.  
        sum += x;
    }
    printf("%d",sum);
 
    return 0;
}
Colored by Color Scripter
cs

정답!

'개발자의 기본기 > 알고리즘 문제' 카테고리의 다른 글

<백준 알고리즘> 10815번 숫자 카드 (0)	2020.09.26
<백준 알고리즘> 1764번 듣보잡 (0)	2020.09.26
<백준 알고리즘> 10824번 네 수 (0)	2020.09.26
<백준 알고리즘> 11721번 열개씩 출력하기 (0)	2020.09.26
<백준 알고리즘> 2839번 설탕배달 (0)	2020.09.26

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	72281	18972	15425	28.284%

문제

상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.

상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.

상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (3 ≤ N ≤ 5000)

출력

상근이가 배달하는 봉지의 최소 개수를 출력한다. 만약, 정확하게 N킬로그램을 만들 수 없다면 -1을 출력한다.

예제 입력 1

예제 출력 1

예제 입력 2

예제 출력 2

-1

예제 입력 3

예제 출력 3

예제 입력 4

예제 출력 4

예제 입력 5

예제 출력 5

<풀이 과정>

1. 가장 먼저 5키로짜리 봉지로 최대한 담을 수 있는 만큼 담는다.

2. 그리고 남은 나머지를 3키로짜리 봉지로 담는다.

3. 이때 나누어 떨어지지 않으면 5키로 짜리 봉지를 하나 해체하여 3키로 봉지로 담는다.

4. 이것을 계속 반복. 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
#include<iostream>
 
using namespace std;
 
int solution(int n){
    int five =n/5; // N을 5로 나눴을 때, 즉 5키로 봉지의 개수 
    
    while(five>=0){
        int X=n-(5*five);// 전체 에서 5*몫을 뺀값
        // 5키로 빼고 나머지가 3으로 나눠 떨어지면  
        if(X%3==0){
            int three=X/3;
            return five+ three;
        }
        five--;
    }
    return -1;
}
int main(){
    int N;
    cin >> N;
    
    int result=0;
    result=solution(N);
    
    cout << result;
 
    return 0;
}
Colored by Color Scripter
cs

'개발자의 기본기 > 알고리즘 문제' 카테고리의 다른 글

<백준 알고리즘> 10815번 숫자 카드 (0)	2020.09.26
<백준 알고리즘> 1764번 듣보잡 (0)	2020.09.26
<백준 알고리즘> 10824번 네 수 (0)	2020.09.26
<백준 알고리즘> 11721번 열개씩 출력하기 (0)	2020.09.26
<백준 알고리즘> 11720번 숫자의 합 (0)	2020.09.26