개발 블로그

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

문제

일반적으로 잠수함 엔진이 작동할 때에 나오는 소리는 잠수함의 종류에 따라서 다르다고 한다.

우리는 물속에서 들리는 소리의 패턴을 듣고서 그 소리가 특정한 잠수함에서 나오는 소리인지 아닌지를 알아내려고 한다. 이 문제에서는 잠수함의 소리가 두 종류의 단위 소리의 연속으로 이루어져 있고, 그 단위 소리를 각각 0과 1로 표시한다.

또, 한 특정한 소리의 반복은 ~로 표시한다. 예를 들어 x~는 x가 한번 이상 반복되는 모든 소리의 집합을 말하고, (xyz)~는 괄호 안에 있는 xyz로 표현된 소리가 한번 이상 반복되는 모든 소리의 집합을 말한다. 다음의 예를 보라.

• 1~ = {1, 11, 111, 1111, ..., 1...1, ...}
• (01)~ = {01, 0101, 010101, 01010101. ...}
• (1001)~ = {1001, 10011001, ..., 100110011001...1001, ...}
• 10~11 = {1011, 10011, 100011, ..., 1000...011, ...}
• (10~1)~ = {101, 1001, 10001, 100001, ...1011001, ...100110110001101, ...}

​그리고 (x|y)는 x또는 y중에서 아무거나 하나만을 선택해서 만든 소리의 집합, 즉 집합{x, y}를 의미한다. 예를 들면(1001|0101)은 집합으로 {1001, 0101}을 의미한다. 따라서 (0|1)~은 0과 1로 이루어진 모든 스트링의 집합, 즉 모든 소리의 집합을 말한다. 또 한 예를 보면 (100|11)~은 100과 11을 마음대로 섞어서 만들 수 있는 모든 소리의 집합을 의미한다. 즉 (100|11)~에 해당하는 스트링을 집합으로 나타내면 {100, 11, 10011, 100100100, 1110011, ...}이 된다. 우리가 식별하고자 하는 잠수함의 엔진소리의 패턴은 다음과 같다.

(100~1~|01)~

여기에 속하는 소리의 예를 들어보면, 1001, 01, 100001, 010101, 1000001110101, 1001110101, 0101010101, 10010110000001111101, 01010101011000111, 10000111001111, ...이다.

다시 말해서 이것은 100~1~과 01을 임의로 섞어서 만들 수 있는 모든 스트링의 집합을 나타낸다.

입력으로 0과 1로 구성된 스트링이 주어질 때, 이 스트링이 앞에서 기술된 잠수함의 엔진소리인지 아닌지를 판별하는 프로그램을 작성하라.

접근 방법

주어진 식은 (100~1~|01)~ 이다.

- part A : 100~

- part B : 1~

 - part C = 01

이라고 하자. 

그 후, next State = cur State + next Char 형식에 맞춰서 나올 수 있는 모든 경우를 계산해보면 다음과 같다.

이렇게 구한 값은 unordered_map<string, vector<string>> umap에 넣어주면 된다.

이때 주의할 점은 value에 해당하는 vector에 nextState값을 넣을 때 인덱스를 고려해서 넣어야한다. 즉, next Char 이 0이면 vector의 0번째 인덱스 [0]에 넣어주고, 1이면 1번째 인덱스[1]에 넣어준다. 그래야 입력된 문자열을 한 글자씩 따라가면서 주어진 형식을 어긋나지 않는지 검사할 수 있다.

그렇게 입력된 문자열을 다 검사한 뒤에, state의 값을 검사한다. 이때 잠수함 엔진소리라면 

case 1) part A -> part B에서 끝나거나

case 2) part C 에서 끝나야 한다. 

case 1)은 "100~1" 와 "100~1~"이 해당되고, case 2)는 "01"이 해당된다.

마지막 state 값이 이 세가지 중 하나라면 잠수함 엔진소리가 맞고, 그 외는 엔진소리가 아니다.

//
//  BF_BOJ2671_잠수함식별.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/07/06.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//


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

int main(){
    
    string str;
    cin >> str;
    
    unordered_map<string, vector<string>> umap;
    
    umap["init"] = {"0","1"};
    umap["0"] = {"X", "01"};
    umap["1"] = {"10", "X"};
    umap["01"] = {"0", "1"};
    umap["10"] = {"100", "X"};
    umap["100"] = {"100~", "100~1"};
    umap["100~"] = {"100~", "100~1"};
    umap["100~1"] = {"0", "100~1~"};
    umap["100~1~"] = {"10 or 0", "100~1~"};
    umap["10 or 0"] = {"100", "01"};
    
    string state = "init";
    for(int i = 0; i<str.length(); i++){
        int nextChar = str[i] - '0';
        state = umap[state][nextChar];
        if(state == "X") break;
    }
    
    if(state == "100~1" || state == "100~1~" || state =="01") cout << "SUBMARINE";
    else cout << "NOISE";
    
    
    
    return 0;
}

(사실 <regex> 라이브러리를 활용하면 한 줄로 끝난다.)

참고  : (https://gglifer-cs.tistory.com/74)

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

문제

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.

회사에는 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

출력

현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

접근 방법

map을 활용해서 key를 기준으로 정렬을 해준다. map을 선언할 때,

    map<string, string, greater<>> m; 

와 같이 선언해서 디폴트인 오름차순 정렬을 내림차순 정렬로 바꿔주면 된다.

그 후 마지막에 value가 "enter"인 사람의 이름만 출력해주면 사전순의 역순으로 출력된다.

//
//  Map_BOJ7785_회사에있는사람.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/06/30.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
#include <map>
using namespace std;

int main(){
    
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    
    map<string, string, greater<>> m;
    int n; cin >> n;
    for(int i = 0; i<n; i++){
        string name, EorL;
        
        cin >> name >> EorL;
        m[name] = EorL;
        
    }
    
    map<string, string>::iterator it;
    for(it = m.begin(); it!=m.end(); it++){
        if(it->second == "enter"){
            cout << it->first << "\n";
        }
    }
        
    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;
}