개발뚱땅

괄호문제처럼 스택을 사용한다.

여는 괄호 ' ( '가 나오면 스택에 넣고

닫는 괄호 ' ) '가 나오면 두가지 케이스로 구분해 처리한다.

1. 레이저인 경우
   ()인 경우 레이저인데, 레이저로 잘리는 경우 스택에 넣었던 여는 괄호 하나를 제거해줘야한다.
   그리고 스택에 들어있는 쇠막대기의 수를 확인하여 답에 더해준다. 레이저로 자르는 순간 그만큼 갯수가 추가되기 때문이다.
2. 쇠막대기의 끝부분인 경우
   ))인 경우 쇠막대기의 끝이다. 왜냐하면 문제에 쇠막대기에는 하나 이상의 레이저가 포함된다고 했기 때문이다.
   그래서 그 경우 스택에서 pop해주고 답에 1을 더해주면 된다.

스택 자료구조를 쓰지 않고, 괄호를 세주는 변수를 사용해도 된다.

#include <string>
#include <vector>
#include <stack>
using namespace std;

int solution(string arrangement) {
    int answer = 0;
    stack<char> s;
        
    for(auto iter = arrangement.begin(); iter != arrangement.end(); ++iter){
        if(*iter == '('){
            s.push(*iter);
        }else{
            s.pop();
            if(*(iter-1) == '('){//laser
                answer += s.size();
            }else{
                answer++;
            }
        }
    }
    
    return answer;
}

괄호로 이루어진 문자열이 들어온다.

스택을 이용해서 괄호를 확인해주면 된다.

'('이 나온경우 스택에 넣고 ')'이 나오면 스택에 있던 '('을 빼주면 된다.

스택에 뺄'('가 없는데 ')'이 먼저 들어오는 경우도 잘못된 경우이며,

이제 문자열 확인이 끝났는데 스택에 '('이 남아있는 경우도 잘못된 경우이다.

여기서 스택을 직접 사용할 필요는 없고 괄호 카운팅용 정수 변수를 사용해서 구현한다.

#include<string>
#include <iostream>
using namespace std;

bool solution(string s)
{
    bool answer = true;
    int cnt = 0;
    
    for(auto el : s){
        if(el == '('){
            cnt++;
        }else{
            cnt--;
        }
        if(cnt<0){
            return false;
        }
    }
    
    if(cnt==0){
        answer=true;
    }else{
        answer=false;
    }

    return answer;
}

카운터를 0으로 초기화하고,

'('인 경우 +1

')'인 경우 -1

그리고 카운터가 음수로 변하면 ')'가 먼저 나온게 되므로 false를 반환한다.

문자열 전체 순회가 끝나고

카운터가 0이 아니라면 '('이 더 많은 것이므로 false

카운터가 0인 경우 true를 반환한다.

동적계획법으로 풀었다.

memset에서 초기화 해줄 때 크기에 자료형 크기만큼 해주지 않아 초기에 오답이 발생했다.

메모이제이션.

base case 초기에 넣어주고 이미 기록 되어있는지 확인. 그 위치에 간 기록이 있고 결과가 있는지.

있다면 바로 반환, 없다면 계산을 하기위해 다시 문제를 작은문제로 분할.

아래로 가는경우와 오른쪽으로 가는 경우.

https://algospot.com/judge/problem/read/JUMPGAME

#include <bits/stdc++.h>

using namespace std;

int board[100][100];
int cache[100][100];

int sol(int x, int y, int size){
	if(x>=size || y>=size){
		//넘침 
		return 0;
	}
	if(x == size-1 && y == size -1){
//		도착 
		return 1;
	} 
	
	if(cache[x][y] != -1){
		return cache[x][y];
	} 
	int jum = board[x][y];
	int &ret = cache[x][y];
	//오른쪽으로 가능 경우
	return ret = max(sol(x+jum, y, size), sol(x, y+jum, size));
	//아래로 가는 경우 
}

int main(){
  int n;
  cin>>n;
  for(int _times = 0; _times < n; ++_times)
  {
  	memset(cache, -1, 10000*sizeof(int));
	int _size;
	cin>>_size;
	for(int i=0; i<_size; ++i){
	  for(int j=0; j<_size; ++j){
		cin>>board[i][j];
	  }
	}
	if(sol(0, 0, _size)==1){
		cout<<"YES"<<endl;
	}else{
		cout<<"NO"<<endl;
	}
  }
 return 0;
}

완전탐색 유형에 있는 숫자 야구 문제이다.

완전 탐색은 이 게시판을 보면 된다.

2019/12/30 - [알고리즘/문제해결전략] - 03 알고리즘 설계 패러다임 - (6)무식하게 풀기

모든 경우의 수를 만들 땐 재귀함수를 이용했다.

모든 경우의 수를 만들고, base case가 되면 조건에 맞는지 확인.

C++을 사용.

1부터 9까지 카드에서 3장을 뽑아 순열을 만들도록 했다.

그리고 모든 경우의 수에서 주어진 데이터와 비교해서 일치하는 경우에 카운팅하도록 구현했다.

20191230

#include <string>
#include <vector>
using namespace std;
string cards="0123456789";
bool pickedCard[10]; 

bool check(string& nums, vector<vector<int>>& baseball){
    for(int i=0; i<baseball.size(); ++i){
        string instring = to_string(baseball[i][0]);
        int ss=0, bb=0;
        
        for(int j=0; j<instring.size();++j){
            int nth = nums.find(instring[j]);
            if(nth== string::npos){
                continue;
            }
            else if(nth == j){
                ss++;
            }else if(nth != j){
                bb++;
            } 
        }
        if(baseball[i][1] !=ss || baseball[i][2] != bb){
            return false;
        }
    }
    return true;
}

void sol(string &picked, vector<vector<int>>& baseball, int &ans){
    if(picked.size() == 3){
        // 체크해서 값 상승
        if (check(picked, baseball)== true){
            ans++;
        }
        return;
    }
    for(int i = 1; i<10; i++){
        //만약 이미 선택된 카드라면 패스
        if(pickedCard[i]) continue;
        
        picked.push_back(cards[i]);
        pickedCard[i] = true;
        
        sol(picked, baseball, ans);
        
        picked.pop_back();
        pickedCard[i] = false;
    }
}

int solution(vector<vector<int>> baseball) {
    int answer = 0;
    string t = "";
    sol(t, baseball, answer);
    return answer;
}

#include <string>
#include <vector>

using namespace std;

string solution(string s) {
    string answer = "";
    //짝수인경우
    int ssize = s.size();
    if(ssize%2 == 0){
        answer.push_back(s[(ssize>>1)-1]);
        answer.push_back(s[(ssize>>1)]);
    }else{
        answer.push_back(s[(ssize>>1)]);
    }
    return answer;
}

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> answer;
    vector<int> a={1,2,3,4,5};
    vector<int> b={2, 1, 2, 3, 2, 4, 2, 5};
    vector<int> c={3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
    vector<int> count_vec = {0, 0, 0};
    for(int i=0; i<answers.size();i++){
        if(answers[i]==a[i%a.size()]){
            count_vec[0]++;
        }
        if(answers[i]==b[i%b.size()]){
            count_vec[1]++;
        }
        if(answers[i]==c[i%c.size()]){
            count_vec[2]++;
        }
    }
    //cout<<count_vec[0]<<", "<<count_vec[1]<<", "<<count_vec[2]<<endl;
    //cout<<max_element(count_vec.begin(), count_vec.end()) - count_vec.begin()<<endl;
    int max_v = *max_element(count_vec.begin(), count_vec.end());
    for(int i=0; i< count_vec.size();i++){
        if(count_vec[i] == max_v){
            answer.push_back(i+1);    
        }
        
    }
    return answer;
}

아직 파이썬 for문이 익숙치 않다.

C언어가 편하다...

def solution(heights):
    answer = [ 0 for x in heights]
    current_v=0
    heights.reverse()
    for i, v in enumerate(heights):
        current_v=heights[i]
        for j in range(i+1, len(heights)):
            if heights[j]>current_v:
                answer[i] = len(heights) - j
                break
    answer.reverse()
    print(answer)
            
    return answer

타인의 풀이

def solution(h):
    ans = [0] * len(h)
    for i in range(len(h)-1, 0, -1):
        for j in range(i-1, -1, -1):
            if h[i] < h[j]:
                ans[i] = j+1
                break
    return ans

큐를 사용해서 조건에 맞게 반복하고, 실행된 횟수를 출력

def solution(priorities, location):
    answer = 0
    wait_list = list(zip(priorities, list(i for i in range(len(priorities)))))
    c = 0
    while wait_list !=0:
        ex = wait_list.pop(0)
        if ex[0] == max(priorities):
            c += 1
            priorities.remove(max(priorities))
            if ex[1] == location:
                return c
        else:
            wait_list.append(ex)
    return answer