8주차 가장큰정사각형찾기/단체사진찍기/올바른괄호

가장 큰 정사각형 찾기 문제

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

int solution(vector<vector<int>> board)
{
    int answer = 1234;
    vector<vector<int>> map(board.size()+1, vector<int> (board[0].size()+1, 0));
    
    for(int i = 0; i < board.size(); i++){
        for(int j = 0; j < board[0].size(); j++){
            map[i+1][j+1] = board[i][j];
        }
    }
    
    for(int i = 1; i <= board.size(); i++){
        for(int j = 1; j <= board[0].size(); j++){
            if(map[i][j] && map[i-1][j] && map[i][j-1] && map[i-1][j-1]){
                int temp = map[i-1][j];
                if(temp > map[i][j-1])
                    temp = map[i][j-1];
                if(temp > map[i-1][j-1])
                    temp = map[i-1][j-1];
                map[i][j] = temp + 1;
            }
        }
    }
    
    int leng = 0;
    for(int i = 1; i <= board.size(); i++){
        for(int j = 1; j <= board[0].size(); j++){
            leng = max(leng, map[i][j]);
            // cout << map[i][j] << " ";
        }
        // cout << "\n";
    }
    
    return leng * leng;
}

어렵다. 구현이야 괜찮은데, 이렇게도 풀수있구나하는걸 몰라서 답안을 찾아봤어야했다. 

설명이 잘된 블로그

 

단체사진찍기

간단한 문제이나 char, int 변환을 잘못해서 한참 걸림

char n = '0' -> int n_int = n - '0'

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

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    int answer = 0;   
    vector<char> arr = {'A', 'C', 'F', 'J', 'M', 'N', 'R', 'T'};
    int ccc = 0; 
    int match['Z' + 1];
    do{ 
        for(int i = 0; i < arr.size(); i++){
            match[arr[i]] = i;
        }
        int flag = true;
        for(int i = 0; i < data.size(); i++){
            string temp = data[i];
            int start = match[temp[0]];
            int end = match[temp[2]];
            char eq = temp[3];
            int n = temp[4] - '0';
            int len = end - start;
            if(len < 0){
                len *= -1;
            }
            len--;
        
            if(eq == '='){ 
                if(len != n){
                    flag = false;
                    break;
                }
            }else if(eq == '>'){
                if(len <= n){
                    flag = false;
                    break;
                }
            }else if(eq == '<'){
                if(len >= n){
                    flag = false;
                    break;
                }     
            }
        }
        
        if(flag)
            answer++;
        
    }while(next_permutation(arr.begin(), arr.end()));
    
    return answer;
}

모든 경우의 수를 만든다.

그다음 그 경우의 수에서 각각의 문자의 위치를 확인한다. 나는 match라는 배열에 인덱스를 넣어주었다.

그리고 모든 명령에 대해서 처리

1) 시작하는 문자 start : match['A'] 이렇게 하면 'A'의 인덱스를 가져올수있다. 

2) 끝나는 문자 end: 위와 같다. 

3) eq: 부호

4) n: 여기서 망했다. char형과 int형의 차이를 제대로 처리안해줬다. 

n = '문자형태 숫자' - '0'을해야 숫자가 된다. 

5) len: 인덱스를 통해서 거리를 구해준다. 

 

조건이 안맞으면 flag=false 처리하고 포문을 탈출한다. 

 

 

올바른 괄호

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

bool solution(string s)
{
    bool answer = true;

    stack<char> st;
    
    for(int i = 0; i < s.size(); i++){
        if(s[i] == '('){
            st.push(s[i]);
        }else{
            if(st.empty()){
                return false;
            }
                
            st.pop();
        }
    }
    
    if(st.empty()){
        return true;
    }
    
    return false;
}

완전기초문제!

 

후기

이번주에는 평일에 공부를 하나도 안해서 일욜밤에 몰아서 세문제 풀었다! 꾸준히 해야하는데, 어떤때에는 주중에는 퇴근하고 코딩이 잘안된다. 그리고 이제 새로관심이 생긴분야가 있다보니, 앞으로도 꾸준히 주말에 몰아서라도 풀어야겠다. 언제한번은 대박쳐보자!