23.08.02. 풀었던 문제들 복기

Leetcode 46. Permutations, 7분

 어제와 마찬가지로 순열만 하면 되는 backtracking 문제. 마찬가지로 같은 포스팅에 작성해 두었다. 리트코드는 한 번 주제가 나오면 계속 그걸로 하는 느낌이라.. 뭔가 아쉽다. daily challenge가 분류 3개정도 나눠서 랜덤으로 하면 좋을 것 같다.

// Runtime 3 ms Beats 67.29%
// Memory 8 MB Beats 29.89%

class Solution {
public:
    vector<vector<int>> answer;
    vector<int> nums, result;
    vector<bool> isUsed;
    int N;
    void permutation(int cur_depth, int max_depth){
        if(cur_depth == max_depth){
            answer.push_back(result);
            return;
        }

        for(int i = 0; i<N; i++){
            if(!isUsed[i]){
                isUsed[i] = true;
                result[cur_depth] = nums[i];
                permutation(cur_depth + 1, max_depth);
                isUsed[i] = false;
            }
        }
    }
    vector<vector<int>> permute(vector<int>& num) {
        N = num.size();
        nums = num;
        isUsed.resize(N); result.resize(N);
        fill(isUsed.begin(), isUsed.end(), false);

        permutation(0, N);
        return answer;
    }
};

 

 

 

BOJ 3613. Java vs C++, 50분

 문제는 잘 접근했는데, 반례 2개랑 출력 형식 때문에 계속 틀렸다.

1. 첫 글자나 마지막 글자가 _인 경우
2. 첫 글자가 대문자인 경우
3. _가 연속으로 오는 경우
4. _와 대문자가 동시에 오는 경우
5. 나머지는 java이거나, cpp인 경우이다. java인 경우는 대문자 유무로 판단, cpp는 _ 유무로 판단한다. 이 때, 그러면 오직 소문자로 된 문자열은 필터링 못하므로 이 경우에 대한 특이 케이스로 모든 문자가 소문자일 때는 cpp로 리턴한다.

 

 그리고 뭐.. java2cpp나 cpp2java는 그냥 짜면 된다.

 출력 형식! Error!인데 ERROR!로 출력했다. 하,,

int JAVA = 0, CPP = 1, ERROR = 2;

int judge(string s){
	if(s[0] == '_' || s[s.length()-1] == '_' || isupper(s[0])) return ERROR;
	for(int i = 1; i<s.length(); i++){
		if(s[i] == '_' && s[i-1] == '_') return ERROR;
	}

	bool isJava = false, isCPP = false;
	for(char c : s){
		if(isupper(c)) isJava = true;
		if(c == '_') isCPP = true;
	}

	if(isJava && isCPP) return ERROR;
	if(isJava) return JAVA;

	string s_backup = s;
	for(char &c : s_backup) c = tolower(c);
	if(s == s_backup) return CPP;

	if(isCPP) return CPP;
	return ERROR;
}

	string java2cpp(string s){
		string result = "";
		for(char c : s){
			if(isupper(c)){
				result += "_";
				result += tolower(c);
			}
			else result += c;
		}
		return result;
	}

	string cpp2java(string s){
		string result = "";
		for(int i = 0; i<s.length(); i++){
			if(s[i] == '_'){
				result += toupper(s[i+1]);
				i++;
			}
			else result += s[i];
		}
		return result;
	}

void solve(){
	string s; cin>>s;
	int type = judge(s);
	if(type == JAVA) s = java2cpp(s);
	else if(type == CPP) s = cpp2java(s);
	else s = "Error!";
	cout<<s;
}

 

 

 

BOJ 5534, 20분

• 모든 문자열들(버린 간판들)에 대해
  • 할 수 있는 모든 간격에 대해 - 목표 문자열 길이가 3이고 간격이 1이라면 총 문자열 길이는 5. 간격이 2면 7, ...
    • 시작할 수 있는 모든 위치에 대해
      • 목표 문자열을 만들 수 있으면 OK.

 실수했던 점은, 각 문자열들에서 목표 문자열을 만들 수 있으면 빼야 했는데, 그 부분을 신경쓰지 못했다.

void solve(){
	int N; cin>>N;
	string name; cin>>name;
	vector<string> garbages(N);
	for(int i = 0; i<N; i++) cin>>garbages[i];

	int answer = 0;
	for(string garbage : garbages){
		int gap = 0;
		while(1){
			int sublen = name.length() + gap * ((int)name.length()-1); // gap일 때 문자열 길이
			if(sublen > garbage.length()) break;

			bool isMatch = true;
			for(int i = 0; i<garbage.length() - sublen + 1; i++){ // i부터 시작, 가능한 모든 시작점 검사
				isMatch = true;
				for(int k = 0; k<name.length(); k++){
					if(name[k] != garbage[i + (gap+1) * k]){
						isMatch = false;
						break;
					}
				}
				if(isMatch){
					answer++;
					break;
				}
			}

			if(isMatch) break;
			gap++;
			
		}
	}
	
	cout<<answer;
}

 

 

 

BOJ 23757. 아이들과 선물 상자

 pq를 쓰면 간단히 풀리는 문제. 항상 pq 쓸 때 유의할 점은, pq는 vector로 구현되기 때문에 vector의 마지막 element가 pq.top()이 된다. 즉슨 pq의 오름차순/내림차순을 위해서는 vector 정렬을 생각하면 된다는 뜻. 만약 vector 정렬을 less<int>로 하는 경우, 작은 수가 vector의 앞에 온다. (큰 수가 뒤로 간다!) 그러면 큰 수가 pq.top()이 된다.

int solve(){
	int N, M; cin>>N>>M;
	priority_queue<int, vector<int>, less<int>> pq;
	int input;
	for(int i = 0; i<N; i++){
		cin>>input;
		pq.push(input);
	}
	vector<int> wants(M);
	for(int i = 0; i<M; i++) cin>>wants[i];

	for(int want : wants){
		int t = pq.top(); pq.pop();
		if(t < want) return 0;
		t -= want;
		pq.push(t);
	}

	return 1;
}

//////////////////////

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

	cout<<solve();

	return 0;
}

 

시간복잡도

 pq 쓰니까 O(nlogn)

 

 

 

BOJ 4811. 알약, 18분

 딱 느껴지는 전형적인 DP 문제. 예시인 (2, 0)과 (3, 0)을 그려보면 subtree에 겹치는 부분이 나오는 것을 알 수 있다.

 그러면, DP의 기본인 memoization과 점화식을 작성해 주면 된다.

• memoization을 위해 dp 배열 작성. 예제에서 20억이 넘는 수치가 나왔으므로 long long으로.
• 점화식
  • 이 문제의 경우 top-down이 훨씬 쉬워 보인다. base case는 1개짜리가 없는 경우. 그러면 남은 문자열은 하나로 고정되기 때문.
  • 한개짜리 개수를 full, 반개짜리 개수를 half라 했을 때 점화식은 
  • dp[full][half] = dp[full-1][half+1] + dp[full][half-1]. 단, 뒤의 항에서 half-1은 1 이상이어야 한다.

ll UNVISITED = -1;
vector<vector<ll>> dp(31, vector<ll>(31, UNVISITED));

// 1개짜리 full개와 반개짜리 half개가 있을 때 가능한 경우의 수
ll recurse(int full, int half){
	if(full == 0) return 1; // base : 1개짜리 없는 경우
	if(dp[full][half] != UNVISITED) return dp[full][half];

	// dp[full][half] = recurse(full-1, half+1) + recurse(full, half-1). 단, 후자는 0개 이상일때
	dp[full][half] = recurse(full-1, half+1);
	if(half >= 1) dp[full][half] += recurse(full, half-1);
	return dp[full][half];
}

void solve(int N){
	cout<<recurse(N, 0)<<'\n';
}

//////////////////////

int main(void) {
	cin.tie(0);
	cout.tie(0);
	std::ios_base::sync_with_stdio(0);
	
	// number of test cases
	while(1){
		int N; cin>>N;
		if(N == 0) break;
		solve(N);
	}

	return 0;
}