WantAirpod

문제

TC

자료구조 흐름

SOL 코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#define PP pair<int,int>

using namespace std;

bool cmp(PP a, PP b)
{
   if (a.second > b.second)
      return true;
   else if (a.second == b.second)
   {
      if (a.first < b.first)
         return true;
      else
         return false;
   }
   else
      return false;
}

bool cmp2(pair<string, vector<pair<int, int>>> a, pair<string, vector<pair<int, int>>> b)
{
   if (a.second[0].second > b.second[0].second)
      return true;
   else
      return false;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
   vector<int> answer;
   map<string, vector<pair<int,int>>> m;
   for (int i = 0; i < genres.size(); i++)
   {
      if (m.find(genres[i]) == m.end())
      {
         vector<pair<int, int>> v;
         v.push_back(make_pair(i, plays[i]));
         m.insert(make_pair(genres[i], v));
      }
      else
         m[genres[i]].push_back(make_pair(i, plays[i]));
   }

   vector<pair<string, vector<pair<int, int>>>> v;
   v.assign(m.begin(), m.end());
   
   for (int i = 0; i < v.size(); i++)
   {
      int cnt = 0;
      for (int j = 0; j < v[i].second.size(); j++)
         cnt += v[i].second[j].second;
      v[i].second.push_back(make_pair(cnt, cnt));
   }
   
   for (int i = 0; i < v.size(); i++)
      sort(v[i].second.begin(), v[i].second.end(), cmp);

   sort(v.begin(), v.end(), cmp2);

   for (int i = 0; i < v.size(); i++)
   {
      for (int j = 0; j < v[i].second.size(); j++)
      {
         if (v[i].second[j].first == v[i].second[j].second)
            continue;
         answer.push_back(v[i].second[j].first);
         if (j == 2)
            break;
      }
   }

   return answer;
}

int main()
{
   solution({ "classic", "pop", "classic", "classic", "pop", "AG" }, { 500, 600, 150, 800, 2500, 300 });
}

SHP

• 행정구역, 산, 강, 하천 등 다양한 지도 데이터를 저장한다.
• vector형식으로 저장되며 점, 선, 도형으로 표현하고 그 속성을 지니고 있다.
• 오해
  • shapefile을 하나의 파일 포맷이라고 생각하지만 사실, 3개의 확장 포맷을 통틀어 shapefile이라고한다.
  • ex) shp, shx, dbf가 해당 포맷을 뜻함.
• shp 파일은 국가공간정보포털 오픈마켓에 있음. 가보면 shp, shx, dbf로 구성된 것을 확인가능함.
• tool : QGIS 

• 각 건물에 대한 속성 값 테이블 형식 (tidy data) : .dbf 

shp, shx = data (공간 데이터)
dbf = infomation (속성 정보)

• 만약 Web/App에서 데이터를 시각화하려면 Shp는 웹에서 인식하지 못함
  • 따라서 웹의 형식에 맞게 json 또는 xml 형식 변경 필요
  • JavaScript는 json이 적절
    • 많은 free-converter가 존재함 ex) https://ogre.adc4gis.com

1. 단일 pair assign

assign은 (자료구조->자료구조)로 동일한 구조일 때 복사 붙여 넣기가 가능하다.

map이나 set으로 중복제거, 정렬 후 vector(간편한)를 이용하여 코드를 작성할 때 assign이 유용해 보인다.

코드

	vector<int> first;
	vector<int> second;
	vector<int> third;
	int myints[] = { 1776,7,4 };

	//1
	first.assign(7, 100);//100을 7번 반복해서 집어넣음.
	vector<int>::iterator it;
	it = first.begin() + 1;

	//2
	second.assign(it, first.end() - 1); // first의 처음과 끝을 제외한 원소들 넣는다.

	//3
	third.assign(first.begin(), first.end());

	//4
	third.assign(myints, myints + 4);

2. 다중 pair assign 

코드

	map<string, int> m;
	vector<pair<string, int>> v;
	map<string, vector<pair<int, int>>> mm;
	vector<pair<string, pair<int, int>>> vv;

	//5
	m.insert({ "1", 1 });
	m.insert({ "2", 2 });
	m.insert({ "3", 3 });
	m.insert({ "4", 4 });
	v.assign(m.begin(), m.end());

	//6
	vector<pair<int, int>> vm;
	vm.push_back({ 1,2 });
	mm.insert({ "str",vm });

	vv.push_back({ "str",{1,2} });
	vv.push_back({ "str",{ 1,2 } });
	vv.push_back({ "str",{ 1,2 } });
	vv.push_back({ "str",{ 1,2 } });
	vv.push_back({ "str",{ 1,2 } });
	vv.push_back({ "str",{ 1,2 } });

	int temp = vv.front().second.first;

	vv.assign(mm.begin(), mm.end());

문자열 집합

유니코드 : 문자 하나당 2바이트의 공간 확보

멀티바이트 : ANSI에서는 1바이트의 공간을 다국어에서 2바이트의 공간을 확보(영어1byte, 한글2byte)

결론 : 문자열 집합에 영향을 받기 싫다면 TCHAR를 쓰길 권장 

_T("")매크로

이 매크로의 역할은 문자집합으로 유니코드가 사용되면 유니코드 형식으로 바꾸어 주는 역할!!

1.new와 delete란?

C언어에서 동적할당 malloc과 free와 동일한 역할을 함.

new를 사용해서 힙에 동적할당하고 delete를 사용하여 해제

#include <iostream>

using namespace std;
struct  Po
{
	int a;
	int b;
};

int main()
{
	//C style
	Po* ptr = (Po*)malloc(sizeof(Po));
	free(ptr);

	//C++ style
	Po* ptr = new Po;
	delete ptr;

	return 0;
}

2.new와 delete란 ? 

하지만 malloc과 new는 같지 않다.

c++의 new는 훨씬 다양한 것을 해줌.

new는 힙에 메모리할당을 해주고 생성자를 호출해주며 해당 타입으로 변환.

new

• 메모리 할당
• 생성자 호출
• 타입변환

delete

• 소멸자 호출
• 메모리 해제

#include <iostream>

using namespace std;
struct  Po
{
	int a;
	int b;
};

class po2
{
public:
	po2()
	{
		cout << "2) new에 의해서 생성자 호출됨 " << endl;

	}
	~po2()
	{
		cout << "3) delete에 의해 소멸자 호출됨" << endl;
	}

};

int main()
{
	//C style
	Po* ptr = (Po*)malloc(sizeof(Po));
	free(ptr);

	//C++ style
	Po* ptr2 = new Po;
	delete ptr2;

	//C style
	po2* ptr3 = (po2*)malloc(sizeof(po2));
	cout << "1) malloc - 메모리 할당 끝 :생성자는 불름?" << endl;
	free(ptr3);
	 
	//C++ style 
	po2* ptr4 = new po2();
	cout << "1)malloc -= 메모리 할당끝 : 생성자는 ?" << endl;
	delete (ptr4);

	return 0;
}

출처 : https://blockdmask.tistory.com/302

파일 입력 코드

외울 코드는 아니고 필요할때마다 그냥 복붙하는게 답

CString m_strPath, str;

	CStdioFile rFile;

	CFileException ex;

	CFileDialog dlg(TRUE, _T("*.txt"), NULL, OFN_FILEMUSTEXIST | OFN_OVERWRITEPROMPT, _T("TXT Files(*.txt)|*.txt|"), NULL);
    	CString getFileString; 

	if (dlg.DoModal() == IDOK)

	{

		m_strPath = dlg.GetPathName();

		rFile.Open(m_strPath, CFile::modeReadWrite | CFile::typeText, &ex);



		while (rFile.ReadString(str))

		{

			getFileString += (str + _T("\r\n"));

		}

		rFile.Close();

                // edit control에 txt파일 쓰기

		mFileView.SetWindowTextW(getFileString);

	}


 

개념

조합(Combination) : 순서 바뀜 허용 안함, 중복 허용 안함, nCr = n! / r! * (n-r)!

순열(Permutation) : 순서 바뀜 허용,         중복 허용 안함, nPr = nCr x r!

*순서 바뀜

ex) 1 1 2 & 1 2 1 --> Per 허용, Com 허용X

ex) {1,2,3} 

조합(3C2): {1,2}, {2,3}, {3,1}

순열(3PC) : {1,2}, {2,1}, {2,3}, {3,2}, {3,1}, {1,3}

조합(3C2) : {1,2,3}

순열(3PC) : 3개의 우너소로 조합 가능한 모든 구성 : 3P3 (nPn = n!) 

{1,2,3}, {1,3,2}, {2,1,3}, {2,3,1}, {3,1,2}, {3,2,1} 

순열(Permutation)는 w=0

조합(Combination)은 w=num

단, 중복을 허용할 시 visit배열을 없애 준다.!!

코드

void Permutition(int ctttt, int num )
{
	if(ctttt==3)
	{
		vector <int > ans;		
		for(int i = 0 ; i < vvvvv_.size() ; i++)
		{
			cout <<" " <<vvvvv_[i]   ; 
		}
		cout<< endl;
		return ;
	}

//permu는 w=0 
	for(int w= 0 ; w<5 ;w ++)
	{
		if(!vii[w])
		{	vii[w]=true;
		vvvvv_.push_back(ex_Num[w]); //0	
		Permutition(ctttt+1,w);
		vvvvv_.pop_back(); 
		vii[w] =false;
		} 
	}

}
void Combination(int ctttt, int num )
{
	if(ctttt==3)
	{
		vector <int > ans;		
		for(int i = 0 ; i < vvvvv_.size() ; i++)
		{
			cout <<" " <<vvvvv_[i]   ; 
		}
		cout<< endl;
		return ;
	}

//combi는 w=num
	for(int w= num ; w<5 ;w ++)
	{
		if(!vii[w])
		{	vii[w]=true;
		vvvvv_.push_back(ex_Num[w]); //0	
		Combination(ctttt+1,w);
		vvvvv_.pop_back(); 
		vii[w] =false;
		} 
	}

}

문제

문제해석

• 4개이상 같은 문자이면 터짐
• 터진 자리에 .으로 채워짐

입출력

풀이

• 12*6 이라는 배열 크기보고 터지진 않겠다라는 생각을함
• 탐색은 세로로 하다가 처음 .이 아닌 문자를 만났을때 BFS를 수행하는게 좋을 것 같다.
• BFS진행 시 cnt값을 주어 4이상일 경우에만 문자->"." 으로 바꿔줘야 겠다고 생각함.

난이도

★★★☆☆

다시 풀어볼만함 약 45분 걸림

SOL코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;

struct cmp
{
	bool operator() (pair<int, int> a, pair<int, int> b)
	{
		if (a.first < b.first)
			return true;
		else if (a.first == b.first)
		{
			if (a.second > b.second)
				return true;
			else
				return false;
		}
		else
			return false;
	}
};

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
char ar[12][6];
int ans;
vector<char> v[6];
bool flag = false;
set<pair<int, int>, cmp> res;

void input()
{
	for (int i = 0; i < 12; i++)
	{
		for (int j = 0; j < 6; j++)
			cin >> ar[i][j];
	}

	for (int i = 0; i < 6; i++)
	{
		for (int j = 11; j >= 0; j--)
			v[i].push_back(ar[j][i]);
	}
}

void break_puyo(char c, int  i, int j)
{
	queue<pair<int, int>> q;
	vector<pair<int, int>> bre_pu;
	bool vi[6][12] = { false, };
	q.push(make_pair(i, j));
	vi[i][j] = true;

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		bre_pu.push_back(make_pair(x, y));

		for (int w = 0; w < 4; w++)
		{
			int nx = x + dx[w];
			int ny = y + dy[w];
			if (nx < 0 || nx >= 6 || ny < 0 || ny >= 12)
				continue;
			if (!vi[nx][ny] && v[nx][ny] == c)
			{
				vi[nx][ny] = true;
				q.push(make_pair(nx, ny));
			}
		}
	}

	if (bre_pu.size() >= 4)
	{
		for (int w = 0; w < bre_pu.size(); w++)
			res.insert(bre_pu[w]);
		flag = true;
	}
}

void solve()
{
	while (true)
	{
		if (res.size() > 0)
			res.clear();
		flag = false;
		for (int i = 0; i < 6; i++)
		{
			for (int j = 0; j < 12; j++)
			{
				if (v[i][j] == '.')
					break;
				break_puyo(v[i][j], i, j);
			}
		}
		if (!flag)
			break;

		ans++;
		for (set<pair<int, int>, cmp>::iterator iter = res.begin(); iter != res.end(); iter++)
		{
			pair<int, int> s = *iter;
			int x = s.first;
			int y = s.second;
			v[x].erase(v[x].begin() + y);
			v[x].push_back('.');
		}
	}
}

int main()
{
	input();
	solve();
	cout << ans << endl;
	return 0;
}