잡다한 프로그래밍

https://swexpertacademy.com/main/main.do

1. 해결방법

벡터를 사용하여 방향 그래프를 저장하였고, 이를 DFS완전 탐색으로 해결하였다

2. 에러 사항

vector를 초기화해주지 않아서 탐색 시간이 길어져 시간 초과가 생겼는데 clear() 함수가 제대로 작동하지 않아서 dfs함수에 vector를 넘겨주고 vector를 전역 변수가 아닌 메인 함수 내부에 선언하는 방식으로 해결하였다

3. 코드

#include<iostream>
#include<vector>
using namespace std;
int test_case;
int T;
int num;
int x, y;
int result = 0;

void vector_dfs(int now, vector<int>* vector){
    if(now == 99){
		result = 1;
        return;
    }else{
        for(int i = 0; i < vector[now].size(); i++){
                        vector_dfs(vector[now][i], vector);    
        }
    }
}

int main(int argc, char** argv)
{
	for(test_case = 1; test_case <= 10; ++test_case)
	{
		cin >> T;
        cin >> num;
		vector<int> vec[100];
        
        for(int i = 0; i < num; i++){
            cin >> x;
            cin >> y;
            vec[x].push_back(y);
        }
        result = 0;
        vector_dfs(0, vec);
            cout << "#" << test_case <<" " << result << endl;
    }
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

https://programmers.co.kr/learn/challenges?tab=all_challenges

1. 해결방법

stack을 활용하여 올바른 괄호 문자열인지 확인하고, 나머지는 문제에서 제시한 방법대로 재귀함수를 진행한다

2. 코드

#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <iostream>
using namespace std;
    string answer = "";

bool check(string p){
    stack<char> st;
    for(int i = 0; i < p.length(); i++){
        if(!st.empty() && p[i] == ')'){
            if(st.top() == '(') {
                st.pop();
            }else {st.push(p[i]);} 
        }else {st.push(p[i]);}
    }

    if(st.empty()) return 1;
    else return 0;
}

string check_function(string p){
    if(p == "") return "";
    string u = "";
    string v = "";
    int left = 0;
    int right = 0;
    
    if(check(p)) {return p;}
    else{
        for(int i = 0; i < p.length(); i++){
            if(p[i] == '(') left++;
            else right++;
            if(left == right) {
                u = p.substr(0,left+right);
                v = p.substr(left+right, p.length());
                
                if(check(u)){ 
                    return u + check_function(v);
                }else{
                    string temp;
                    temp += "(";
                    temp += check_function(v);
                    temp += ")";
                    string temp2 = u.substr(1, u.length()-2);
                    for(int j = 0; j < temp2.length(); j++){
                        if(temp2[j] == '(') temp += ")";
                        else temp += "(";
                    }
                    return temp;
                }
                
            }
            
        }
    }
}

string solution(string p) {
    if(p == "") return "";
    answer = check_function(p);
    return answer;
}

https://programmers.co.kr/learn/challenges?tab=all_challenges

1. 해결방법

문제에서 제시한 개수만큼 글자를 자르고 이전과 다음으로 저장하여 비교하는 방식을 사용하였다.

2. 코드

#include <iostream>
#include <string>
#include <vector>

using namespace std;
int answer = 9999;
void check(int num, string s){
    int mok;
    if(s.length() % num == 0) mok = s.length() / num;
    else mok = s.length() / num + 1;
    string result = "";
    int check = 1;
    string pre; string next;
    for(int i = 0; i < mok-1; i++){
        pre = s.substr(i*num, num);
        next = s.substr((i+1) * num , num);
        
        if(pre == next) check++;
        else{
            if(check != 1) result += to_string(check) + pre;
            else result += pre;
            check = 1;
        }
    }
    if(check == 1) result += next;
    else result += to_string(check) + pre;
    if(result.length() < answer) answer = result.length();
    
}

int solution(string s) {
                answer = 9999;

    for(int i = 1; i <= s.length()-1; i++){
        check(i, s);
    }
    if(s.length() == 1) answer = 1;
        return answer;
}