개발 블로그

문제 링크 : 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;
}

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

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 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개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

접근 방법

이번에도 nextInt()와 System.out.print() 로 입출력을 하니까 시간초과가 나서 버퍼입출력으로 시간초과를 해결했다.

HashMap과 containsKey(), get() 메소드만 이용하면 쉽게 해결할 수 있다.

import java.util.*;
import java.io.*;

public class Map_BOJ10816_숫자카드2 {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static StringTokenizer tokens;
	
	public static void main(String[] args) throws IOException {
		
		int N = Integer.parseInt(br.readLine());
		
		HashMap<Integer,Integer> map = new HashMap<>();
		
		tokens = new StringTokenizer(br.readLine());
		for(int i = 0; i<N; i++) {
			int num = Integer.parseInt(tokens.nextToken());
			if(!map.containsKey(num)) {
				map.put(num, 1);
			}
			else {
				int newValue = map.get(num) + 1;
				map.put(num, newValue);
			}
		}
		
		
		int M = Integer.parseInt(br.readLine());
		tokens = new StringTokenizer(br.readLine());
		for(int i = 0; i<M; i++) {
			int num = Integer.parseInt(tokens.nextToken());
			if(map.containsKey(num)) {
				bw.write(map.get(num) + " ");
			}
			else {
				bw.write("0 ");
			}
			
		}
		bw.flush();
		bw.close();
		br.close();
	}
}