뚝딱뚝딱

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

💡 뒤집기

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.예를 들어 S=0001100 일 때,전체를 뒤집으면 1110011이 된다.4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.

[입력]
첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.

[출력]
첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.

✅ 문제 풀이

• 문자열의 첫 문자를 기준으로 해서 문자열을 앞에서부터 순회한다.
• 첫 문자를 now에 저장해두고, 비교하다가 문자가 다르면 count를 해주고 now에 그 문자로 바꾸어준다.
• 위 과정을 반복하고 나면 최종 count값이 설정된다.
• count값이 홀수이면 0을1로, 1을 0으로 바꾸는 횟수가 똑같기 때문에, count를 2로 나눈 몫에 1을 더한 것과 같다.
• count값이 짝수이면, 0을 1로, 1을 0으로 바꾸는 횟수가 둘 중 하나가 더 적기 때문에, count를 2로 나눈 몫과 같다.

✏ 코드 전문

#include<iostream>
#include<string>

using namespace std;

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

	string str;
	cin >> str;

	int count=0;
	char now = str[0];
	for (int i = 1; i < str.length(); i++) {
		if (now != str[i]) {
			count++;
			now = str[i];
		}
	}

	if (count % 2 == 1) {
		count /= 2;
		count++;
	}
	else {
		count /= 2;
	}

	cout << count;

	return 0;
}

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

💡 명령 프롬프트

시작 -> 실행 -> cmd를 쳐보자. 검정 화면이 눈에 보인다. 여기서 dir이라고 치면 그 디렉토리에 있는 서브디렉토리와 파일이 모두 나온다. 이때 원하는 파일을 찾으려면 다음과 같이 하면 된다.
dir *.exe라고 치면 확장자가 exe인 파일이 다 나온다. "dir 패턴"과 같이 치면 그 패턴에 맞는 파일만 검색 결과로 나온다. 예를 들어, dir a?b.exe라고 검색하면 파일명의 첫 번째 글자가 a이고, 세 번째 글자가 b이고, 확장자가 exe인 것이 모두 나온다. 이때 두 번째 문자는 아무거나 나와도 된다. 예를 들어, acb.exe, aab.exe, apb.exe가 나온다.
이 문제는 검색 결과가 먼저 주어졌을 때, 패턴으로 뭘 쳐야 그 결과가 나오는지를 출력하는 문제이다. 패턴에는 알파벳과 "." 그리고 "?"만 넣을 수 있다. 가능하면 ?을 적게 써야 한다. 그 디렉토리에는 검색 결과에 나온 파일만 있다고 가정하고, 파일 이름의 길이는 모두 같다.

=> 주어지는 파일들을 한번의 패턴 명령으로 모두 조회할 수 있도록 만드는 것이다.

✅ 풀이 방법

• 이 문제를 풀기 위해 "두 가지"를 생각했다.
• 한가지는 , 첫 번째로 받는 문자열을 "기준"으로 잡아야 겠다는 것
• 또 다른 한가지는, 인덱스 정보를 저장할 자료 구조로 중복을 허용하지 않는 "set"을 이용해야겠다는 것

이 두가지를 유념해 두고 풀이를 보자.

• 첫번 째 문자열을 먼저 받고, 만약 입력 받은 문자열이 하나가 끝이라면, 패턴은 그 문자열 자체가 될 수 있다.
  따라서 그 문자열 자체를 출력하고 return 0을 통해 프로그램을 종료한다.
• 문자열의 길이와, 인덱스를 저장할 set 자료구조를 생성해 놓는다.
• 만약 입력 받는 문자열이 하나가 아니라면, T-1번 문자열을 받는다.
• 문자열을 받을 때마다, 받고 난 뒤, 기준 문자열인 첫번째 문자열과 한 글자씩 비교한다.
• 문자가 다르면, 해당 문자 위치인 인덱스를 set에 넣는다.
• 문자열을 모두 받고 나면, set에는 패턴에서 ?가 되어야 할 인덱스들이 들어 있는 것과 같다.
• set을 순회하면서, 첫번 째 문자열에 replace함수를 사용하여, set에 있는 인덱스의 문자는 모두 ?로 대체해준다.
• 최종 패턴 문자열이 된 첫번 째 문자열을 출력해준다.

전체 코드는 아래와 같다.

#include<iostream>
#include<string>
#include<set>

using namespace std;

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

	int T;
	cin >> T;

	string str;//기준이 되는 str
	cin >> str;

	if (T == 1) {
		cout << str;
		return 0;
	}

	int len = str.length();

	//중복값을 넣지 않는 set을 선언해서, 값이 다른 인덱스를 넣는다
	set<int> index;

	for (int i = 1; i < T; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < len; j++) {
			if (str[j] != s[j]) {
				index.insert(j);
			}
		}
	}

	for (auto it = index.begin(); it != index.end(); it++) {
		str.replace(*it, 1, "?");
	}
	//replace(인덱스, 몇글자, "대체문자")

	cout << str;

	return 0;
}

✏ c++ 문법 알고 넘어가기

• set : 자료 구조 중 하나로, 중복 값을 허용하지 않는다.
  <set> 헤더에 정의되어 있다.
  insert로 값을 넣는다.
  set에 있는 값을 가져올 때는 iterator를 반환하기 때문에, 앞에 *을 붙혀서 값을 가져온다.
• string.replace() : string의 문자열 대체 함수이다.
  replace(인덱스, 문자개수, "대체 문자")의 인자를 갖는다. 

앞의 달리기 경주를 풀고 난 뒤 이 문제를 보니, 어떻게 풀어야 할지 바로 감이 잡혔다.

이 문제 역시 map을 사용하여 해결할 수 있다.

string과 int가 짝을 이루고, 주어진 string을 통해 탐색하는 과정이 필요하다면 map을 사용할 것!

풀이는 아래와 같다.

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<int> solution(vector<string> name, vector<int> yearning, vector<vector<string>> photo) {
    vector<int> answer;
    
    
	map <string, int> m1;

	for (int i = 0; i < name.size(); i++) {
		m1[name[i]] = yearning[i];
	}

	for (int i = 0; i < photo.size(); i++) {
		int cnt = 0;
		for (int j = 0; j < photo[i].size(); j++) {
			cnt += m1[photo[i][j]];
		}
		answer.push_back(cnt);
	}
    
    return answer;
}

string을 인덱스로 갖는 map을 하나 생성하여 주어진 값들을 대입해주었다.

그리고 photo를 한 줄 단위로 읽으며 값을 카운트 해주면 된다!

이 문제를 풀려고 했을 당시 처음엔 callings vector에 저장되어 있는 이름들을 players에서 찾아 내야 한다는 생각은 했으나, 이름과 등수를 바로바로 매치할 수 있는 방법이 떠오르지 않아서.. 단순히 while/for 반복문으로 하나씩 접근할 수 밖에 없었다.

그 코드는 아래와 같았고, 역시 몇개의 case에서 시간초과 문제가 발생하였다.

#include <string>
#include <vector>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {

	int sz = players.size();
	int cnt = 1;

	for (int i=0; i<callings.size(); i++){
		string temp = callings[i];

		if (i < callings.size() - 1 && temp == callings[i + 1]) {
			cnt++;
			continue;
		}

		for (int j = 0; j < sz; j++) {
			if (players[j] == temp) {
				int target = j - cnt;
				while (target < j) {
					swap(players[j], players[j - 1]);
					j--;
				}
				cnt = 1;
				break;
			}
		}
	}
	return players;
}

시간 초과가 발생한 부분은 [players를 일일이 탐색하는 부분]+[vector의 위치를 swap하는 부분] 이다. 

vector도 제법 빠른 자료구조라 생각했는데, 자리를 바꾸는 과정은 역시 O(N)이다.

이 문제의 핵심은 map을 사용하는 것이었다!!!!

map을 총 두개 사용하여 해결하였는데, 하나는 등수(int)를 기준으로 이름을 저장한 것과, 하나는 이름(string)을 기준으로 등수를 저장한 것이다.

이렇게 하면 반복문을 돌면서 callings에 있는 이름을 일일이 찾지 않고, 이름 자체를 인덱스로써 활용하여 현재 등수를 알아 낼 수 있다!!

해결한 코드는 아래와 같다.

#include <string>
#include <vector>
#include <map>

using namespace std;

vector<string> solution(vector<string> players, vector<string> callings) {
	//답 : vector라는 자료구조를 사용하는 것보다 map으로 정렬과정을 거친 후 vector에는 최종 결과 삽입만 하기.

	vector<string> answer;

	int sz = players.size();
	map <int, string> m1;//등수 별 이름 기억해두기
	map <string, int> m2;//이름 별 등수 기억해두기

	for (int i = 0; i<players.size(); i++) {
		m1[i] = players[i];
		m2[players[i]] = i;
	}

	for (int i = 0; i < callings.size(); i++) {
		string temp = callings[i];
		int tempIdx = m2[temp];
		m1[tempIdx] = m1[tempIdx - 1];//swap과정
		m1[tempIdx - 1] = temp;
		m2[temp] = tempIdx - 1;
		m2[m1[tempIdx]] = tempIdx;

	}

	for (auto temp : m1) {
		answer.push_back(temp.second);//m1의 두번째 요소(이름)들을 넣는다.
	}

	return answer;
}

그 결과 map을 활용해서 탐색 시간을 확실히 줄일 수 있었다!!

반환하고자 하는 것은 vector이므로, m1에 등수대로 적힌 이름들을 answer에 push_back하였고 이를 반환하도록 하였다.

1. 'strcpy()' vs '=' / 'assign()' 

c++로 문제를 해결하던 중 string 문자열을 복사하는 코드에서 'strcpy()'를 사용해서 문자열을 대입하려고 했더니, strcpy의 인자인 const char* 타입은 string과 어긋나면서 오류가 발생하였다!

c++에서 string문자열을 복사/대입하려면 std::string의 멤버 함수인 assign() 또는 = 연산자를 사용하면 해결된다!

확실히 c보다 c++은 문자열에서도 제약을 덜 받는 느낌이다,,

2. 'strcmp()' vs '=='

strcmp역시 c언어 스타일에서 사용하는 방식이다. 위에서와 동일한 오류가 발생한다.

c++에서는 단순히 ==을 통해 문자열을 비교할 수 있다!

3.vector의 맨 앞 원소를 삭제할 때

vector.erase(vector.front())

4.vector의 원하는 위치에 원소를 삽입할 때

vector.insert(vector.begin()+i, temp);

인덱스 정보를 넣는 곳에 정수를 입력해서 오류가 발생하였다!

iterator를 인자로 받기 때문에, 위와같이 vector.begin()으로 인덱스 정보를 가져와야 한다.

i는 원하는 인덱스번호라고 생각할 수 있고, temp는 넣고자 하는 값이다.

5. auto 자료형 추론

auto는 변수 선언 시 자료형을 명시하지 않아도, 대입된 값을 통해서 컴파일러가 알아서 자료형을 추론한다.

코드가 간결해지고 유지보수에는 좋으나, 가독성이 떨어질 수 있음!

vector의 기본 쓰임에 대해 복습할 필요가 있음을 느낀 문제..