개발뚱땅

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

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

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

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를 반환한다.

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

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

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

옷의 카테고리 별로 옷의 개수를 넣은 사전을 만들고 옷을 안입은 경우를 포함해서 1을 더해주고 모든 조합을 구한다.

안입은경우, 카테고리 내의 옷을 입은경우의 수 곱 반복.

그리고 모두 안입은 경우를 뺀다.

import collections 

def solution(clothes): 
    answer = 1 
    myCounter = collections.Counter(typ for name,typ in clothes) 
    print(myCounter) 
    for num in myCounter.values(): 
        answer *= num+1 
    return answer-1

collections라는 라이브러리를 쓰면 코드가 짧아진다.