D-1

1. sw expert 사칙연산 유효성 검사

그냥 dfs가 아니라 순회는 탈출 조건이 return이 아니라 지나치도록 해야함.

아니면 방문처리.

+ stringstream ss로 문자열 분리하는 법 이해.

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

using namespace std;

struct node {
	int left = -1;
	int right = -1;
	string value;
};

vector<node> N;

int is_ok = 1;
int is_operator = 0;

void DFS(node cur_node) {
	if (is_ok == 0) {
		return;
	}

	if (cur_node.left == -1) {
	}
	else {
		DFS(N[cur_node.left]);
	}


	//cout << cur_node.value << " ";

	if (cur_node.value == "+" || cur_node.value == "-" || cur_node.value == "*" || cur_node.value == "/") {
		if (is_operator == 0) {
			is_ok = 0;
		}
		is_operator = 0;
	}
	else {
		is_operator = 1;
	}

	if (cur_node.right == -1) {
	}
	else {
		DFS(N[cur_node.right]);
	}
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 10;
	
	//총 테스트 케이스의 갯수는 입력으로 주어지지 않는다. 10개 고정
	//cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		int num;
		cin >> num;
		cin.ignore();
		int answer;

		//중위 순회 자체는 어렵지 않은데, 트리 구조와 함께 만들어야 함.
		//1차원 벡터에 저장하고 이동할 때 두배로 이동하는 방법 사용하기.
		//왼쪽 자식 = 현재 노드 * 2, 오른쪽 자식 = 현재 노드 * 2 + 1
		//근데 여기는 괴상하게도 input data가 자식 노드까지 다 알려줌.

		N = vector<node>(num + 1);

		string temp;
		for (int i = 1; i <= num; i++) {
			node temp_N;
			int index;

			getline(cin, temp);
			stringstream ss(temp);
			string temp_str;
			int cnt = 1;
			
			while (ss >> temp_str) {
				if (cnt == 1) {
					index = stoi(temp_str);
				}
				else if (cnt == 2) {
					temp_N.value = temp_str;
				}
				else if (cnt == 3) {
					temp_N.left = stoi(temp_str);
				}
				else if (cnt == 4) {
					temp_N.right = stoi(temp_str);
				}
				cnt++;
			}
			//cout << index << ": " << temp_N.value << " " << temp_N.left << " " << temp_N.right << "\n";
			N[index] = temp_N;
		}

		is_ok = 1;
		is_operator = 0;
		DFS(N[1]);

		answer = is_ok;
		
		cout << "#" << test_case << " " << answer << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

다른 기호로 나누는 법은 이렇다.

while(getline(ss,subs1,' ')){
    v.push_back(subs1); // v = {"012" , "34567" , "89"}
}

 

2. 프로그래머스 입국심사

풀이를 보고 푼 문제. 이분탐색으로 나누는게 시간이라는 발상이 되게 특이했다.

마치 배낭 문제의 발상을 보는 느낌.

long long 자료형을 중간에 쓰지 않은 변수 때문에 오류가 났었다.

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

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    
    sort(times.begin(), times.end());
    
    int times_num = times.size();
    
    //한명이 최소, n 명이 최대
    long long min = times[0] * 1;
    //long long 변환?
    long long max = n * (long long)times[times_num - 1];
    
    //cout << min << " " << max << endl;
    
    //middle시간을 기준으로 가능한 최대 사람.
    long long total_num;
    long long middle;
        
    while(min <= max){
        middle = (min + max) / 2;
        total_num = 0;
        
        for(int i=0; i<times_num; i++){
            total_num = total_num + middle / times[i];
            //cout << total_num << endl;
        }
        
        //cout << min << " " << middle << " " << max << endl;
        
        //여유로우면
        if(total_num >= n){
            max = middle - 1;
            answer = middle;
        }
        else{
            min = middle + 1;
        }
    }
    
    return answer;
}

 

 

3. sw expert 괄호 짝짓기

스택을 사용하여 품.

#include<iostream>
#include<string>
#include<stack>
 
using namespace std;
 
int main(int argc, char** argv)
{
    int test_case;
    int T = 10;
     
 
    /*
       여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
    */
 
    char open[] = { '(', '{', '[', '<'};
    char close[] = { ')', '}', ']', '>'};
     
    for (test_case = 1; test_case <= T; ++test_case)
    {
        int num;
        cin >> num;
 
        string arr;
        cin >> arr;
 
        stack<char> st;
 
        int is_ok = 1;
 
        for (int i = 0; i < arr.size(); i++) {
            if (is_ok == 0) {
                break;
            }
 
            for (int j = 0; j < 4; j++) {
                if (open[j] == arr[i]) {
                    st.push(arr[i]);
                    break;
                }
                else if (close[j] == arr[i]) {
                    //닫는 기호가 짝이 맞아야 하기 때문에
                    if (st.empty() || (st.top() != open[j])){
                        is_ok = 0;
                        break;
                    }
                    st.pop();
                    break;
                }
            }
        }
 
        cout << "#" << test_case << " " << is_ok << "\n";
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

 

4. sw expert ladder1

bfs인데 좌 또는 우로만 가도록해서 구했음

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

struct info {
	int y;
	int x;
};

vector<vector<int>> visited;

//좌우 먼저 확인
int dy[] = { 0, 0, 1 };
int dx[] = { -1, 1, 0 };

int BFS(vector<vector<int>> board,int y, int x) {
	queue<info> q;
	q.push({ y, x });
	visited[y][x] = 1;

	info position;

	int ny;
	int nx;

	while (!q.empty()) {
		position = q.front();
		q.pop();

		if (position.y == 99) {
			return position.x;
		}

		for (int i = 0; i < 3; i++) {
			int ny = position.y + dy[i];
			int nx = position.x + dx[i];

			if (ny < 0 || nx < 0 || ny >= 100 || nx >= 100 || board[ny][nx] == 0 || visited[ny][nx] == 1) {
				continue;
			}
			else {
				q.push({ ny, nx });
				visited[ny][nx] = 1;
				//하나만 넣어줘야 함.
				break;
			}
		}
	}

	return -1;
}

int main(int argc, char** argv)
{
	int test_case;
	int T = 10;

	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{
		int test;
		cin >> test;

		vector<vector<int>> board(100, vector<int>(100, 0));
		for (int y = 99; y >= 0; y--) {
			for (int x = 0; x < 100; x++) {
				cin >> board[y][x];
			}
		}

		info start;
		for (int x = 0; x < 100; x++) {
			if (board[0][x] == 2) {
				start.y = 0;
				start.x = x;
				break;
			}
		}

		visited = vector<vector<int>>(100, vector<int>(100, 0));
		
		int x;

		x = BFS(board, start.y, start.x);

		cout << "#" << test << " " << x << "\n";
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}