[99클럽 코테 스터디 7일차 TIL] #해시3

오늘은 7일 차. 알바 갔다 와서 피곤하지만 할 일은 해야겠죠? 오늘도 어김없이 파이팅입니다. 

 

문제 설명

---

 

음을 아는 노래의 개수 n, 맞출 노래 개수 m이 먼저 주어지고 이러한 횟수를 바탕으로 노래길이와 노래제목, 노래의 음계가 문자로 주어진다. 이를 활용하여 정환이가 윤수를 이기기 위해 비교 분석하는 문제이다. 자세한 내용은 링크를 통해서..,

 

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

 

 

생각 흐름

---

우선, 글의 양에 압도되는 문제였다. 조금 당황했지만 천천히 읽어보며 문제를 제대로 한 번에 이해하기 위해 노력했던 것 같다. (한번 잘못 이해하면 코드 다시 작성하는 게 짜증 나니까,,)

 

먼저 단순한 음악 맞추기 게임이고, 음악과 음계가 주어지면 이를 비교하는 문제라는 점을 대충 알아보았던 것 같다.

 

이를 보고 해시 자료구조가 생각이 났지만 지금까지 풀어왔던 방법과는 다른 문자열과 또 다른 문자를 저장하는 형태라는 점에서 살짝 망설였었다. 하지만 일단 뭐라도 작성해 보자라는 생각에 코드를 한 줄 한줄 써나갔던 것 같다.

 

먼저 확실한 간단한 반복문을 구현하고 받아오는 문자열과 문자들을 저장할 unordered_map을 먼저 선언하였다.

그리고 unordered_map <string, char [7]> um에 각각의 노래 정보들을 저장하였다.

 

(unorderd_map 안에 char []과 같은 배열을 저장할 수 있다는 것을 처음 알았다. 그리고 노래제목 길이는 쓸모도 없는데 왜 알려주는데!)

 

그리고 새로 음계 3개를 저장할 배열 c [3]을 선언하고 이를 um의 원소들과 일일이 비교하며 조건문을 작성해 주었다.

 

그리고 출력 조건에 맞는 조건문을 설정해 주어 마무리하였다.

 

#include <bits/stdc++.h>
using namespace std;

int main () {
    ios_base::sync_with_stdio();
    cin.tie(); cout.tie();

    int n, m, mlen; // 알고 있는 노래 개수 n, 들어야 할 노래 개수 m, 노래 길이 mlen
    string music; // 노래 이름 문자열 music
    char c[3]; // 음 3개를 받아올 배열 c[3] 선언
    unordered_map<string, char[7]> um; // 노래와 음계를 저장할 map 선언

    cin >> n >> m;

    for (int i = 0; i < n; i++) {
        cin >> mlen >> music; // 음악 노래 길이 mlen과 음악이름 music을 받고
        for (int j = 0; j < 7; j++) {
            cin >> um[music][j]; // 음악별로 시작하는 음 7개 저장
        }
    }

    for (int i = 0; i < m; i++) {
        for (int j = 0; j < 3; j++) {
            cin >> c[j];
        }

        int cnt = 0;
        string ans;


        for (auto it : um) {
            bool check = true;
            for (int j = 0; j < 3; j++) {
                if (c[j] != it.second[j]) {
                    check = false;
                    break;
                }
            }

            if (check) { // 앞 음 3개 맞으면
                cnt++; // 아는 음악 개수 1개 추가

                if (cnt == 2) { // 2개 이상이면 더이상 검사 x
                    break;
                }

                ans = it.first; // ans에 음악 이름 저장
            }
        }

        if (cnt > 1) { // cnt가 2면 ? 출력
            cout << "?" << "\n";
        }

        else if (cnt == 1) { // cnt가 1이면 음악 제목 출력
            cout << ans << "\n";
        }

        else { // 맞는게 없다면 ! 출력
            cout << "!" << "\n";
        }
    }

    return 0;

}

 

 

공부한 내용 정리

---

1.  unordered_map

• map보다 더 빠른 탐색을 하기 위한 자료구조입니다.
• unordered_map은 해시테이블로 구현한 자료구조로 탐색 시간복잡도는 O(1)입니다.
• map은 Binary Search Tree로 시간복잡도는 O(log n)입니다.
• unordered_map을 사용하기 위해서는 #include < unordered_map >을 선언해야 합니다.
• unordered_map은 중복된 데이터를 허용하지 않고 map에 비해 데이터가 많을 시 월등히 좋은 성능을 보입니다. 하지만, key가 유사한 데이터가 많을 시 해시 충돌로 인해 성능이 떨어질 수도 있습니다.

 

함수

empty( )

• 맵이 비어있는지 확인하는 함수
• if unordered_map is empty, then return 1 else 0

size( )

• 맵의 크기를 확인하는 함수
• return size_type ( unsigned int )

operator [ ]

• 맵에서 key를 통해 value를 지정하는 operator
• map_name [key] = value

find( key )

• 맵에서 key에 해당하는 원소를 찾는 함수
• if key is contained, then iterator else map_name.end()

count( key )

• 맵에서 key에 해당하는 원소의 개수를 반환하는 함수
• if key is contained, return 1 else 0

insert( {key, value} )

• 맵에 pair <key,value> 를 추가하는 함수
• if key is contained, then not insert

erase( key )

• 맵에서 key에 해당하는 원소를 제거하는 함수
• erase 하는 방법 : 특정 position의 pair 삭제, key를 통해 삭제, 범위 삭제

clear( )

• 맵을 초기화하는 함수

operator =

• 대입연산자 가능

 

탐색방법

• index로 접근할 수 없고 iterator로 접근하여야 한다.
• 시작 : begin( ), 끝 : end( )
• key : iter->first, value : iter->second
• 반복문 사용 시 auto 활용 or pair< key_type, value_type > 사용

 

 

너무 피곤해서 일단 내일 공부하고 복붙하고 갈게요. 내일 다시 보기!