개발 블로그

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

문제

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

입력

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

듣도 못한 사람의 명단에는 중복되는 이름이 없으며, 보도 못한 사람의 명단도 마찬가지이다.

출력

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

접근 방법

입력되는 명단에 중복되는 이름이 없으므로 이름을 key로 하는 unordered_map을 사용해서 빠른 탐색을 하도록 하자.

먼저 N명의 듣도 못한 사람 명단을 map에 입력받고,

그 다음 M명의 보도 못한 사람의 명단을 입력받는데 이때, 그 보도 못한 사람의 이름이 듣도 못한 사람 명단에 있는지 검사해서 있으면 ansVec에 push한다.

명단을 사전순으로 출력하기 위해 마지막에 ansVec를 sort 해주면 된다.

//
//  Map_BOJ1764_듣보잡.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/04.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
    
    int N, M; cin >> N >> M;
    string str1 = "";
    unordered_map<string, int> umap;
    vector<string> ansVec;
    for(int i = 0; i<N; i++){
        cin >> str1;
        umap[str1] = 0;
    }
    string str2 = "";
    for(int i = 0; i<M; i++){
        cin >> str2;
        if(umap.find(str2)!=umap.end()){    //보도 못한 사람이 듣도 못한 사람 명단에도 있으면
            ansVec.push_back(str2);
        }
    }
    
    sort(ansVec.begin(), ansVec.end());
    cout << ansVec.size() << "\n";
    for(int i = 0; i<ansVec.size(); i++){
        cout << ansVec[i] << "\n";
    }
    
    return 0;
}

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

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

접근 방법

value를 pair로 지정해서 각각 first 는 leftChild로, second는 rightChild를 설정해준다.

그 후 전위, 중위, 후위 탐색 알고리즘에 맞게 unordered_map의 key와 value를 이용해준다. 

//
//  Tree_BOJ19991_트리순회.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/01.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <unordered_map>
#include <utility>
using namespace std;

int N;
unordered_map<char, pair<char,char>> umap;

void preOrder(char c){
    if(umap.find(c) == umap.end()) return;
    else{
        cout << c;
        if(umap.find(umap[c].first) != umap.end() && umap[c].first != '.') preOrder(umap[c].first);
        if(umap.find(umap[c].second) != umap.end() && umap[c].second != '.') preOrder(umap[c].second);
    }
    
}
void inOrder(char c){
    if(umap.find(c) == umap.end()) return;
    else{
        if(umap.find(umap[c].first) != umap.end() && umap[c].first != '.') inOrder(umap[c].first);
        if(umap.find(umap[c].second) != umap.end() && umap[c].second != '.') inOrder(umap[c].second);
        cout << c;

    }
    
}
void postOrder(char c){
    if(umap.find(c) == umap.end()) return;
    else{
        if(umap.find(umap[c].first) != umap.end() && umap[c].first != '.') postOrder(umap[c].first);
        if(umap.find(umap[c].second) != umap.end() && umap[c].second != '.') postOrder(umap[c].second);
        cout << c;

    }
    
}

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    cin >> N;

    for(int i = 0; i<N; i++){
        char p, n1, n2;
        cin >> p >> n1 >> n2;
        umap[p] = make_pair(n1, n2);
    }
    
    preOrder('A');
    cout << "\n";
    inOrder('A');
    cout << "\n";
    postOrder('A');

    
    return 0;
}

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

문제

해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신 렌즈를 착용하거나 해야한다. 해빈이가 가진 의상들이 주어졌을때 과연 해빈이는 알몸이 아닌 상태로 며칠동안 밖에 돌아다닐 수 있을까?

입력

첫째 줄에 테스트 케이스가 주어진다. 테스트 케이스는 최대 100이다.

• 각 테스트 케이스의 첫째 줄에는 해빈이가 가진 의상의 수 n(0 ≤ n ≤ 30)이 주어진다.
• 다음 n개에는 해빈이가 가진 의상의 이름과 의상의 종류가 공백으로 구분되어 주어진다. 같은 종류의 의상은 하나만 입을 수 있다.

모든 문자열은 1이상 20이하의 알파벳 소문자로 이루어져있으며 같은 이름을 가진 의상은 존재하지 않는다.

출력

각 테스트 케이스에 대해 해빈이가 알몸이 아닌 상태로 의상을 입을 수 있는 경우를 출력하시오.

접근 방법

unordered_map 을 이용해서 의상의 종류에 해당하는 옷 이름이 각각 몇개인지 구한다. 주어진 예시를 보면,

<headgear, 2>

<eyewear, 1>

라는 두개의 pair가 unordered_map에 저장이 된다. 

그 후, map 전체를 돌면서 second에 1을 더한 숫자를 곱해서 해빈이가 가진 옷들로 만들 수 있는 총 조합의 수를 구한다.

1을 더한 이유는 해당 옷을 입지 않는 경우도 있기 때문이다.

그리고 마지막에 1을 빼줘야하는데, 이유는 headgear도 입지 않고 eyewear도 입지 않는 경우(알몸인 상태)를 선택한 경우는 제외해야하기 때문이다. 

//
//  Map_BOJ9375_패션왕신해빈.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/06/27.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <unordered_map>

using namespace std;

int main(){
    
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    int test_case;
    cin >> test_case;
    for(int t = 0; t<test_case; t++){
       
        int n;
        cin >> n;
        int answer =  1;
        
        if(n==0) answer = 0;
        else{
            unordered_map<string, int> umap;
            
            for(int i = 0; i<n; i++){
                string name, type;
                cin >> name >> type;
                if(umap.find(type) != umap.end()){          //이미 맵에 해당 종류 있으면
                    int cnt = umap[type];   //value
                    umap[type] = cnt+1;                     //그 종류의 가짓수 1 증가
                }
                else{
                    umap[type] = 1;
                   // umap.insert(make_pair(type,1));         //없으면 1로 초기화해서 추가
                }
            }
           
            unordered_map<string,int>::iterator it;
            for(it = umap.begin(); it!=umap.end(); it++){
                answer *= (it->second) + 1;
            }
            answer -= 1;
        }
        
        cout << answer << "\n";
    
    }
    
    return 0;
}

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

오박사 : 그럼 다솜아 이제 진정한 포켓몬 마스터가 되기 위해 도감을 완성시키도록 하여라. 일단 네가 현재 가지고 있는 포켓몬 도감에서 포켓몬의 이름을 보면 포켓몬의 번호를 말하거나, 포켓몬의 번호를 보면 포켓몬의 이름을 말하는 연습을 하도록 하여라. 나의 시험을 통과하면, 내가 새로 만든 도감을 주도록 하겠네.

입력

첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어.

둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 포켓몬 이름의 최대 길이는 20이야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알파벳으로만 들어오면 포켓몬 번호를 말해야 하고, 숫자로만 들어오면, 포켓몬 번호에 해당하는 문자를 출력해야해. 입력으로 들어오는 숫자는 반드시 1보다 크거나 같고, N보다 작거나 같고, 입력으로 들어오는 문자는 반드시 도감에 있는 포켓몬의 이름만 주어져. 그럼 화이팅!!!

출력

첫째 줄부터 차례대로 M개의 줄에 각각의 문제에 대한 답을 말해줬으면 좋겠어!!!. 입력으로 숫자가 들어왔다면 그 숫자에 해당하는 포켓몬의 이름을, 문자가 들어왔으면 그 포켓몬의 이름에 해당하는 번호를 출력하면 돼. 그럼 땡큐~

접근 방법

unordered_map을 사용했다. (java - HashMap)

처음 포켓몬 이름을 입력 받을 때 strArr[]에도 같이 저장해준다. 번호로 포켓몬을 찾을 때 인덱스로 접근하기 위해서다.

그 후 이름을 입력했으면 map에서 찾을 수 있으므로 해당 이름(key)에 해당하는 value를 출력하면 되고, 

번호를 입력했으면 map에서 찾을 수 없으므로 strArr[번호]를 참조해서 출력한다. 

//
//  Map_BOJ1620_나는야포켓몬마스터이다솜.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/06/27.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int main(){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);	//없으면 시간 초과
    
    int N, M;
    cin>> N >> M;
    
    string strArr[100001];
    
    string name;
    unordered_map <string, int> pocketMon;
    for(int i = 1; i<=N; i++){
        cin >> name;
        
        pocketMon.insert(make_pair(name,i));
        strArr[i] = name;
    }
    
    for(int i = 0; i<M; i++){
        string input;
        cin >> input;
        if(pocketMon.find(input)!=pocketMon.end()){	//이름을 입력하면 map 참조
            cout << pocketMon.find(input)->second << "\n";
        }
        else{
            int num = stoi(input);			//번호를 입력한 경우에는 배열 참조
            cout << strArr[num] << "\n";
        }
    }
    
    return 0;
}