[백준] 17219번_알고리즘_자료구조_비밀번호 찾기

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

17219번: 비밀번호 찾기

자료구조와 트리의 의미

자료구조란, 자료들을 정리하여 보관하는 여러 가지 구조인데 그 예로 정수, 실수, 리스트, 트리 등이 있다.

17219번_비밀번호 찾기 문제는 트리라는 자료구조를 이용한 알고리즘이다.

트리란, 나무를 거꾸로 세워놓은 것처럼 생긴 그래프인데, 자료를 정해진 방식에 따라 분류하여 저장하기 때문에 일렬로 자료를 저장하는 연결 리스트보다 검색이 빠르다는 장점이 있다.

단, 정해진 규칙에 따라 자료를 삽입, 삭제하기 때문에 삽입과 삭제가 리스트만큼 간단하진 않다.

 

오답 코드

17219번_비밀번호 찾기 문제는 map에 대한 이해가 필요하다.

map에 대해 모를 때, 나는 이 문제를 배열을 이용해서 풀었다.

하지만, 100,000개의 주소와 100,000개의 비밀번호를 찾기에는 매우 비효율적인 프로그램이었다.

자료의 수를 100,000개가 아닌 10,000개로 하면 출력은 제대로 나왔지만, 백준 채점에서는 틀렸다고 나왔다.

나의 오답 코딩은 다음과 같다.

//오답 코딩
#include <iostream>
#include <cstring>
using namespace std;

int main()
{
   cin.tie(NULL);
   ios::sync_with_stdio(false);

   int n, m;
   string site, password, find;
   cin >> n >> m;
   string siteList[100000], passwordList[100000], findList[100000];
   
   for (int i = 0; i < n; i++) {
      cin >> site >> password;
      siteList[i] = site;
      passwordList[i] = password;
   }

   for (int i = 0; i < m; i++) {
      cin >> find;
      findList[i] = find;
   }

   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         if (findList[i] == siteList[j]) cout << passwordList[j] <<"\n";
      }
   }
   return 0;
}

 

 

 

---

https://www.hanbit.co.kr/channel/category/category_view.html?cms_code=CMS9990721111

About STL : C++ STL 프로그래밍(7)-맵(Map)

map에 대한 내용은 위 사이트를 참고했다.

map에 대한 더 자세한 내용이 담겨 있으므로, map에 대해 더 알고 싶다면 위 사이트를 추천한다.

 

map

map의 자료구조는 트리이다.

map은 파이썬에서의 딕셔너리와 비슷하다. 파이썬에서 딕셔너리에 대해 배웠던 적이 있어서 map도 쉽게 이해할 수 있었다.

map은 key와 value로 이루어져 있다.

key와 value가 순서쌍 형태로 저장된다.

예를 들어 key가 학번이고 value가 이름이라면, (20200202, 양우너)처럼 한 쌍으로 저장된다.

key는 value를 가리키는 의미고, value는 저장할 자료이다.

key는 중복되지 않는 고유한 값이어야 한다. (만약 중복을 허용하고 싶다면, multimap이 있다.)

 

■ map을 사용할 때

- 정렬해야 할 때

- 많은 자료를 저장하고, 검색을 빨리해야 할 때

- 삽입, 삭제를 빈번하게 하지 않아도 될 때

 

■ map을 쓰기 위한 라이브러리

#include <map>

 

라이브러리(library)는 말 그대로 도서관이라는 의미인데,

주로 도서관은 모르는 지식을 깨닫기 위해, 전문가로부터 쓰인 문서를 읽기 위함이다.

마찬가지로, 다른 사람들의 지식으로부터 만들어진 코드를 재사용하고, 개발 시간을 단축하기 위해 라이브러리를 사용한다.

내가 만드는 코드들은 거의 라이브러리에 저장되어 있기 때문에 라이브러리를 충분히 활용할 수 있는 능력을 더 키울 것이다.

 

■ map 선언 형식

map<key의 type, value의 type>변수 이름;

//예) 
map<int,int>map1;
map<int, string>map2;
map<string, string>map3;

 

■ map 자료 추가 형식

변수 이름[key] = value;

 

+) 특정 위치에 추가할 때 :

변수 이름. insert(map<key의 type, value의 type>::value_type(key에 넣을 요소, value에 넣을 요소));

 

■ map 멤버 함수

멤버	설명
begin	첫 번째 원소의 랜덤 접근 반복자를 반환한다.
clear	저장하고 있는 모든 원소를 삭제한다.
empty	저장하고 있는 요소가 없으면 true를 반환한다.
End	마지막 원소 다음의(미 사용 영역) 반복자를 반환한다.
erase	특정 위치의 원소나 지정 범위의 원소들을 삭제한다.
Find	key와 연관된 원소의 반복자를 반환한다.
insert	원소를 추가한다.
lower_bound	지정한 key의 요소를 가지고 있다면 해당 위치의 반복자를 반환한다.
operator[]	지정한 key 값으로 원소를 추가하고 접근한다.
rbegin	역방향으로 첫 번째 원소의 반복자를 반환한다.
rend	역방향으로 마지막 원소 다음의 반복자를 반환한다.
size	원소의 개수를 반환한다.
upper_bound	지정한 key 요소를 가지고 있다면 해당 위치 다음 위치의 반복자 반환한다.

 

---

코드 설명

1. 사용한 라이브러리

#include <cstring>

문자열을 사용하기 위해 사용한다.

#include <map>

map함수를 이용하기 위해 사용한다. map에 대해서는 위에서 설명했다.

 

2. 입출력 시간을 줄이기 위한 함수

cin.tie(NULL);

ios::sync_with_stdio(false);

이 내용은 아래 주소에서 자세히 설명했다.

https://blog.naver.com/yangnony01/222242242475

[백준] 15552번_단계별로 풀어보기_ for 문_빠른 A+B

3. map

map<string, string> site_password;

map<key의 type, value의 type>변수 이름;

site_password라는 변수에 string type의 key와 string type의 value를 지정했다.

 

4. site와 password 입력 받기

site_password[site] = password;

//site_password.insert({ site,password });

site_password라는 변수에 site와 password를 저장한다.

 

5. site 찾기

for (int i = 0; i < m; i++) {

cin >> findSite;

cout << site_password[findSite] << "\n";

}

사용자가 찾고 싶은 site의 개수 m만큼 입력을 받는다.

site_password[findSite]

를 통해 입력받은 site의 password를 출력한다.

---

정답 코드

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

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int n, m;
	string site, findSite, password;

	cin >> n >> m;
	
	map<string, string> site_password;

	for (int i = 0; i < n; i++) {
		cin >> site >> password;

		site_password[site] = password;
		//site_password.insert({ site,password }); 
	}

	for (int i = 0; i < m; i++) {
		cin >> findSite;
		cout << site_password[findSite] << "\n";
	}

	return 0;
}