알고리즘 스터디 3일차

박경록 저자님의 코딩 테스트 합격자 되기 c++ 편을 완독 하는 것을 목표로 남기는 공부 일지
(배열, 스택)

1. 나누어 떨어지는 숫자 배열

1) 문제

문제 설명
array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요.
divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요.

제한사항
arr은 자연수를 담은 배열입니다.
정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 입니다.
divisor는 자연수입니다.
array는 길이 1 이상인 배열입니다.

2) 문제 분석 및 풀이

1) 설계, 분석

• 제수가 1이면 바로 정렬해서 반환
• array 순회하며 각 원소가 divisor로 나누어 떨어지는지 확인
• 주어진 array를 오름차순으로 정렬
  
  
• $O(NlogN)$

2) 풀이

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

using namespace std;

vector<int> solution(vector<int> arr, int divisor) {
    vector<int> answer;

    if (divisor == 1)
    {
        sort(arr.begin(), arr.end());   
        return arr;
    }

    for (int i =0; i < arr.size(); i++)
    {
        if ((arr[i] % divisor) == 0) answer.push_back(arr[i]);
    }

    if ( answer.size() == 0 )
        answer.push_back(-1);

    sort(answer.begin(), answer.end());
    return answer;
}

2. $n^2$ 배열 자르기

1) 문제

문제 설명
정수 $n$, $left$, $right$가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.

$n$행 $n$열 크기의 비어있는 2차원 배열을 만듭니다.
$i = 1, 2, 3, ..., n$에 대해서, 다음 과정을 반복합니다.
1행 1열부터 $i$행 $i$열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
새로운 1차원 배열을 arr이라 할 때, arr[$left$], arr[$left+1$], ..., arr[$right$]만 남기고 나머지는 지웁니다.
정수 $n$, $left$, $right$가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

제한사항
$1 ≤ n ≤ 10^7$
$0 ≤ left ≤ right < n^2$
$right - left < 10^5$

2) 문제 분석 및 풀이

1) 설계, 분석

• $n$의 크기가 크기 때문에 행렬을 채우고 확인하는 방식 ( $O(N^2)$ ) 으로는 해결 불가.
• $right - left < 10^5$ 이 범위를 기준으로 해결 해야함. ( $O(NlogN)$ 이하의 알고리즘으로 해결해야.)
  
  
• $\begin{matrix}1&2&3&4\\2&2&3&4\\3&3&3&4\\4&4&4&4 \end{matrix}$
• 각 원소에 규칙이 있음
  • 대각을 포함한 좌하단 삼각형 구역
    • 값 = 행 번호 + 1
  • 대각을 제외한 우상단 삼각형 구역
    • 값 = 열 번호 + 1
      
      
• $i$행 $j$열 원소가 전체에서 몇번째인지 변환하는 법을 알면 쉽다.
  • 위의 규칙을 통해서 n번째 원소의 행,열 정보를 구하면 n번째 원소의 값을 낼 수 있음.
• 위의 정보를 종합해서 $left$ 부터 $right$ 까지 순회하여 해결 가능
• $O(N)$

2) 풀이

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;

    // i의 값을 2차원 배열의 인덱스들로 바꿔서 풀이
    for (auto i = left; i<=right; i++)
    {
        int row = i % n;
        int col = i / n;

        // Lower Triangle(x==y 포함)
        if (row >= col)
        {
            answer.push_back(row + 1);
        }
        // Upper Triangle

        else if (row < col)
        {
            answer.push_back(col + 1);
        }
    }
    return answer;
}

3. 괄호 회전하기

1) 문제

문제 설명
다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

(), [], {} 는 모두 올바른 괄호 문자열입니다.
만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.
대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
s의 길이는 1 이상 1,000 이하입니다.

2) 문제 분석 및 풀이

1) 설계, 분석

• 문자열을 회전 시키고 올바른지 판단 => $O(N^2)$
• $N = 10^3$, 가능!
  
  
• 문자열 크기만큼 반복
  • 왼쪽으로 한칸 회전
  • 문자열을 순회
    • 올바른 문자열인지 확인
      • 여는 괄호면 저장
      • 닫는 괄호
        • 괄호 저장소가 비어 있으면 올바르지 않은 문자열
        • 마지막에 저장된 여는 괄호와 비교
        • 같은 유형이면 마지막으로 저장된 여는 괄호 삭제
        • 다른 유형이면 올바르지 않은 문자열
  • 괄호 저장소가 비어 있으면 올바른 문자열

• $O(N^2)$

2) 풀이

#include <string>
#include <vector>
#include <stack>
#include <map>

using namespace std;

bool validation(const string& s , int startIndex)
{
    map <char, char> match_pair = {
        {')','('},
        {'}','{'},
        {']','['},
    };

    stack<char> leftOpen;
    for (int j=0; j < s.size(); j++)
    {
        // 왼쪽으로 j칸 회전
        int index = (startIndex + j) % s.size();
        char c = s[index];

        if (c == '(' || c == '[' || c == '{')
        {
            leftOpen.push(c);
        }
        else 
        {
            if (leftOpen.empty()) return false;
            if (leftOpen.top() != match_pair[c]) return false;

            leftOpen.pop();
        }
    }

    return leftOpen.empty();
}

int solution(string s) {
    int answer = 0;
    stack<char> leftOpen;

    for (int i = 0; i < s.size(); i++)
    {
       if (validation(s, i)) answer++;
    }

    return answer;
}