minjgziii

📍 문제

📍 풀이

자료구조 deque 사용

deque에 입력 받은 원소들 삽입

첫 번째 for문에서

먼저,

deque의 첫번째 원소를 변수 a에 저장 (a에 저장된 값이 현재 계산할 주식 price)

deque의 첫번째 원소 pop

그리고 두 번째 for문에서

1) a (현재 비교를 할 price)보다 deque의 i번째 원소보다 크거나 같으면 cnt++ 를 해 준다 (가격이 떨어지지 않은 경우)

2) 그렇지 않으면, 가격이 떨어졌으므로, cnt++를 해 주고 break로 반복문을 빠져나간다

여기서 cnt++를 해 주는 이유는 [ 1, 2, 3, 2, 3 ] 의 예에서 3->2 에서 가격이 떨어지지 않은 시간은 1이다.

🤔 여기서 잠깐!

이 문제는 prices의 길이는 10,000 이하이다.

따라서 보통의 문제에서는 이중 for문을 돌리게 되면, O(N^2)으로 시간초과가 나게 된다.

하지만 특이하게도 이 문제에서는 시간초과가 나지 않는다.

O(N)의 시간복잡도로 푸는 방법에 대해서도 생각해 보아야 한다. => 이후 글 참고~!

📍 코드

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

vector<int> solution(vector<int> prices) {
    vector<int> answer;
    
    deque<int> d;

    for (int i{ 0 }; i < prices.size(); i++) {
        d.push_back(prices[i]);
    }

    for (int i{ 0 }; i < prices.size(); i++) {
        int cnt = 0;
        int a = d.front();
        d.erase(d.begin());

        for (int i{ 0 }; i < d.size(); i++) {
            if (a <= d[i]) {
                cnt++;
            }
            else {
                cnt++;
                break;
            }
        }
        answer.push_back(cnt);
    }
    return answer;
}

📍 문제

📍 풀이

• 자료구조 스택 활용
• '(' 를 담을 stack<char> open 선언

 올바른 괄호가 아닌 조건 2가지 

 1)  ')' 가 들어왔는데 스택이 비어있는 경우

 2)  마지막에 스택에 데이터가 남아있는 경우

입력 받은 string s의 길이만큼 반복문을 돌며

▶️ '(' 일 때 => 스택에 push

▶️ ')' 일 때 => 스택에서 pop

    이 때,  1)  스택이 비어있어서 pop을 하지 못하는 경우 => 올바르지 않은 괄호

반복문을 다 돌고도,  2)  마지막에 스택에 데이터가 남아있는 경우 => 올바르지 않은 괄호

📍 코드

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

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

    stack<char> open;

    for (int i{ 0 }; i < s.size(); i++) {
        // '(' 일 때
        if (s[i] == '(') {
            open.push(s[i]);
        }
        // ')' 일 때
        else {
            // ')'일 때, pop을 하려고 하는데 스택이 비어있다 -> 올바르지 않은 괄호
            if (open.size() == 0) {
                return false;
            }
            else {
                open.pop();
            }
        }
    }

    // 마지막에 스택에 데이터가 남아있다 -> 올바르지 않은 괄호
    if (open.size() != 0) {
        answer = false;
    }

    return answer;
}

📍 문제

📍 풀이

• 자료구조 스택 활용
• 입력 받은 원소들을 스택에 담아, top(가장 마지막으로 입력 받은 원소)부터 오큰수를 구한다 => 역순으로!
• 구한 오큰수들도 스택에 담기 때문에 답을 출력할 때, [ top 원소 출력, pop ] 를 반복하면 순서대로 출력됨

☑️ 맨 마지막에 입력 받은 원소 (스택에서 top에 있는 원소)는 항상 오큰수가 없다.

따라서, 반복문을 돌기 전에

s1(오큰수 후보들)에 마지막 원소를 push하고,

s(오큰수를 구할 원소들)에서 pop하고,

answer(답을 담을 stack)에 -1을 삽입한다.

☑️ 반복문을 돌며 다음 조건문들에 따라 경우가 나뉜다.

1. s1(오큰수 후보들) 사이즈가 0인 경우 즉, s1에 원소가 하나도 없는 경우 => 오큰수가 없는 경우
2. s(현재 오큰수를 구하고 있는 원소)의 top보다 s1(오큰수 후보들) 의 top이 큰 경우 => 오큰수 후보가 됨
3. 현재 비교한 값은 오큰수가 아니지만, s1(오큰수 후보들) 사이즈가 0이 아닌 경우 => 아직 오큰수가 될 수 있는 후보가 있음 (아직 비교할 원소가 남아 있다!)

✥ 각 조건문마다 실행되는 과정은 코드 주석 참고

다음 그림에서 [ 파랑 -> 빨강 -> 초록 -> 보라 -> 노랑 ] 순으로 실행된다.

📍 코드

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int A = 0; // 수열 A의 크기
	int number;
	stack<int> s; // 오큰수를 구할 원소들
	stack<int> s1; // 현재 원소의 오큰수 후보들
	stack<int> answer; // 구한 원소들 (답)
	

	cin >> A;
	
	for (int i{ 0 }; i < A; i++) {
		cin >> number;
		s.push(number);
	}

	s1.push(s.top()); // s1에 s의 top(마지막 원소) 삽입
	s.pop(); // s에서 top 원소 삭제
	answer.push(-1); // 맨 마지막 원소는 항상 오큰수 없음 (즉, -1)

	while (s.size() > 0) {
		// s1에 원소가 하나도 없는 경우 -> 오큰수가 없음
		if (s1.size() == 0) {
			answer.push(-1); // 오큰수 없기 때문에 답을 넣을 스택에 -1 push
			s1.push(s.top()); // 다음 원소 비교를 위해 s1에 s의 top 원소 삽입
			s.pop();
		}
		// s의 top보다 s1의 top이 큰 경우 -> 오큰수 후보/
		else if (s.top() < s1.top()) {
			answer.push(s1.top());
			s1.push(s.top());
			s.pop();
		}
		// 오큰수가 없지만, s1의 size가 0이 아닌 경우 (아직 오큰수가 될 수 있는 후보가 있음)
		else {
			s1.pop();
		}
	}

	for (int i{ 0 }; i < A; i++) {
		cout << answer.top() << " ";
		answer.pop();
	}
}

📍 문제

📍 풀이

'('를 저장할 stack s1과

')'를 저장할 stack s2를 만든다.

입력 받은 string s를 첫번째 index부터 돌면서 '('과 ')'를 각각의 stack에 삽입한다.

그런데, ')'일 때,

만약 s1의 size가 0이면 false이다.

예를 들어 "())"의 경우 마지막 ')'와 대응되는 '('가 없다.

즉, ')'일 때는 이와 대응되는 '('가 있어야 하기 때문에 s1의 사이즈가 0이면 false가 된다.

s1의 size가 0보다 크면,

s1과 s2 둘 다 pop 한다.

이렇게 for문을 돌고 난 후,

s1과 s2의 size는 둘 다 0이어야 true가 된다. (남아있는 원소가 없어야 한다)

테스트케이스 추가

"())(()" -> false

📍 코드

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

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

    stack<char> s1; // (
    stack<char> s2; // )

    for (int i{ 0 }; i < s.size(); i++) {
        if (s[i] == '(') {
            s1.push('(');
        }
        else {
            s2.push(')');
            if (s1.size() <= 0) {
                return false;
            }
            else {
                s1.pop();
                s2.pop();
            }
        }
    }

    if (s2.size() == 0 && s1.size() == 0) {
        answer = true;
    }
    else {
        answer = false;
    }

    return answer;
}

📍 문제

📍 풀이

길이가 같은 2개의 배열에서 각 원소들을 하나씩 매칭시켜 곱해 더했을 때 누적값이 최솟값을 구하려면,쉽게 말해, 두 수를 곱해 최소가 되려면  최대값 * 최소값  을 하면 된다.

따라서A 배열을 오름차순 정렬을 하고B 배열을 내림차순 정렬을 해서

for문을 돌며 각 배열의 같은 index 원소를 곱해 answer에 누적해 주면 된다.

📍 코드

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

int solution(vector<int> A, vector<int> B)
{
    int answer = 0;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    reverse(B.begin(), B.end());

    for (int i{ 0 }; i < A.size(); i++) {
        answer += A[i] * B[i];
    }

    return answer;
}

📍 문제

📍 코드

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

string solution(string s) {
    string answer = "";

    string tmp = "";
    vector<string> v;


    for (int i{ 0 }; i < s.size(); i++) {
        // 공백이 아닐 때
        if (s[i] != ' ') {
            tmp += s[i];
        }
        // 공백일 때
        else {
            tmp += ' ';
			if (s[i + 1] != ' ') {
				if (tmp[0] >= 'a' && tmp[0] <= 'z') {
					tmp[0] = toupper(tmp[0]);
				}
				for (int i{ 1 }; i < tmp.size(); i++) {
					if (tmp[i] >= 'A' && tmp[i] <= 'Z') {
						tmp[i] = tolower(tmp[i]);
					}
				}
				answer += tmp;
				tmp.clear();
			}
        
		}
	}

    if (tmp[0] >= 'a' && tmp[0] <= 'z') {
        tmp[0] = toupper(tmp[0]);
    }
    for (int i{ 1 }; i < tmp.size(); i++) {
        if (tmp[i] >= 'A' && tmp[i] <= 'Z') {
            tmp[i] = tolower(tmp[i]);
        }
    }
    answer += tmp;

    return answer;
}

🧐 더 간단한 코드

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

string solution(string s) {
    string answer = "";

    answer += toupper(s[0]);

    for (int i{ 1 }; i < s.length(); i++) {
        // 만약 공백 뒤의 문자라면, 단어의 첫글자 -> 대문자로 변환
        if (s[i - 1] == ' ') {
            answer += toupper(s[i]);
        }
        else {
            answer += tolower(s[i]);
        }
    }

    return answer;
}

📍 문제

📍 풀이

입력받은 string의 사이즈 만큼 for문을 돌며

공백이 아니라면
➔ tmp에 삽입

공백이라면 (즉 하나의 숫자가 끝났다는 뜻)
➔ tmp를 int로 변환 후(stoi 함수 사용) v에 삽입
➔ tmp 비운다 (다음 숫자를 위해)

💡 이렇게 하는 이유는 -1과 같은 음수를 적절하게 int로 변환하기 위해서 

마지막 원소는 공백이 아니기 때문에 for문에서 삽입되지 않는다.

따라서, 마지막 숫자는 for문이 완료된 후에 따로 넣어주어야 한다.

그 후, sort 함수를 사용해 오름차순으로 정렬한다.

그리고 answer에 vector의 첫번째 원소(최솟값) + " " + vector의 마지막 원소(최댓값) 을 삽입한다.

📍 코드

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

using namespace std;

string solution(string s) {
    string answer = "";

    vector<int> v;
    string tmp;

    for (int i{ 0 }; i < s.length(); i++) {
        // 공백이 아니면 
        if (s[i] != ' ') {
            tmp += s[i];
        }
        // 공백이면 (즉, 숫자 하나가 끝남)
        else {
            v.push_back(stoi(tmp));
            tmp.clear();
        }
    }

    // 마지막 원소가 공백이 아니기 때문에
    // for문에서 vector에 삽입되지 않음
    // 따로 넣어주어야 함
    v.push_back(stoi(tmp));

    sort(v.begin(), v.end());

    answer = to_string(v.front()) + " " + to_string(v.back());

    return answer;
}

📍 문제

📍 코드

#include<iostream>
using namespace std;

char arr[51][51];

string WB[8] = {
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW"
};

string BW[8] = {
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB",
        "BWBWBWBW",
        "WBWBWBWB"
};

// 처음이 W
int f_white(int x, int y) {
	int result = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (arr[x + i][y + j] != WB[i][j]) {
				result++;
			}
		}
	}
	return result;
}

// 처음이 B
int f_black(int x, int y) {
	int result = 0;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			if (arr[x + i][y + j] != BW[i][j]) {
				result++;
			}
		}
	}
	return result;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
    cout.tie(0);

	int N = 0;
	int M = 0;

    int result = 64;
	int white;
    int black;

	cin >> N >> M;

    // 체스판 입력 받기
	for (int i{ 0 }; i < N; i++) {
		for (int j{ 0 }; j < M; j++) {
			cin >> arr[i][j];
		}
	}
    

    for (int i = 0; i <= N - 8; i++) {
        for (int j = 0; j <= M - 8; j++) {
			white = f_white(i, j);
			black = f_black(i, j);
			if (white < black) {
				result = (white < result) ? white : result;
			}
			else {
				result = (black < result) ? black : result;
			}
        }
    }
    
	cout << result << '\n';

}