괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다. '(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.
제한 사항
문자열 s의 길이 : 100,000 이하의 자연수 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
입출력 예시
s
answer
"()()"
true
"(())()"
true
")()("
false
"(()("
false
접근방식
s에서 '('가 나오면 스택에 push
만약 다른 문자 ( ')' )가 나오고 스택에 요소가 존재하면 pop
그 외의 것은 false 출력
반복문이 끝난 후 스택이 남아 있지 않으면 true 출력
코드
#include <string>
#include <iostream>
#include <stack>
using namespace std;
bool solution(string s)
{
bool answer = false;
stack<char> stk;
for (int i = 0; i < s.length(); i++)
{
if (s[i] == '(')
{
stk.push(s[i]);
}
else if (stk.size())
{
stk.pop();
}
else
{
return answer;
}
}
if (!stk.size())
{
answer = true;
}
return answer;
}
회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다.Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요.
제한 사항
works는 길이 1 이상, 20,000 이하인 배열입니다.
works의 원소는 50000 이하인 자연수입니다.
n은 1,000,000 이하인 자연수입니다
입출력 예시
works
n
result
[4, 3, 3]
4
12
[2, 1, 2]
1
6
[1,1]
3
0
접근방식
n만큼 반복 하면서 벡터를 내림 차순으로 정렬 후 가장 높은 수 만큼 빼는 것으로 접근
1. n이 0이 될 때 까지 반복하다가 n이 0이 되거나 내림 차순으로 정렬한 벡터의 맨 앞(Max 값)이 0이면 반복 종료
2. works에서 front를 미리 뽑아 놓고 works의 벡터를 순회해서 미리 뽑아 놓은 front와 해당 순차의 works값이 같으면 n값과 함께 빼주기
3. 그렇지 않고 works의 다음 값이 있으면 다시 내림 차순 정렬, 해당 반복문 종료
4. works에 남아 있는 값 제곱해서 answer에 더해주기
코드
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
long long solution(int n, vector<int> works)
{
long long answer = 0;
sort(works.rbegin(), works.rend());
while(n)
{
if (!works.front())
{
break;
}
int front = works.front();
for (int i = 0; i < works.size(); i++)
{
if (!n)
{
break;
}
if (front == works[i])
{
works[i]--;
n--;
}
else
{
if (i != works.size() - 1)
{
if (works[i] < works[i + 1])
{
sort(works.rbegin(), works.rend());
}
break;
}
}
}
}
for (int i = 0; i < works.size(); i++)
{
answer += pow(works[i], 2);
}
return answer;
}
구현한 기능들 1. 광고 리워드 지급 2. 능력치 성장 (공격력, 체력, 체력 회복량) 3. 스테이지 정보 (번호, 이름) 4. 메인 퀘스트 (적 처치, 능력치 향상, 스테이지 클리어) + 보상 5. 적 여러명 구현 (기존 예제는 1명) 6. 적 오브젝트 풀링 구현 (기존 예제는 풀링 사용 X) 7. 랜덤 뽑기 (중복 보상 지급) 8. 전투 추가 (기존 예제는 적이 공격안함)
일주일동안만 진행해서 코드가 많이 정리되어 있지 않음, 애드몹 SDK를 붙히는 과정에서 인지 모르겠지만 안드로이드 빌드 오류 발생
강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다.
강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의 블루레이에 모든 기타 강의 동영상을 녹화하기로 했다. 이때, 블루레이의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 단, M개의 블루레이는 모두 같은 크기이어야 한다.
강토의 각 강의의 길이가 분 단위(자연수)로 주어진다. 이때, 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 강의의 수 N (1 ≤ N ≤ 100,000)과 M (1 ≤ M ≤ N)이 주어진다. 다음 줄에는 강토의 기타 강의의 길이가 강의 순서대로 분 단위로(자연수)로 주어진다. 각 강의의 길이는 10,000분을 넘지 않는다.
출력
첫째 줄에 가능한 블루레이 크기중 최소를 출력한다.
예제 입력
9 3
1 2 3 4 5 6 7 8 9
예제 출력
17
접근방식
범위를 봤을때 10만인데 단순 2중 for문으로 하면 시간 복잡도가 n^20만이라 이분 탐색으로 접근했다.
블루레이에 하나씩 담는 처리를 할건데 담는 처리는 중앙 값에서 값을 하나씩 빼는 것으로 처리하고 중앙 값에서 요소의 값을 빼면서 진행하는데 0보다 작다면 (음수가 된다면) 중앙 값을 바꾸고 블루레이 갯수를 추가하는 식으로 했다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, a[100004], low, high, mid, sum, _max, result;
bool check(int mid)
{
if (_max > mid)
{
return false;
}
int num = mid;
int cnt = 0;
for (int i = 0; i < n; i++)
{
if (mid - a[i] < 0)
{
mid = num;
cnt++; // 블루레이 갯수 증가
}
mid -= a[i]; // 블루레이에 담음
}
if (mid != num)
{
cnt++;
}
return cnt <= m;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> a[i];
sum += a[i];
_max = max(_max, a[i]);
}
low = 0, high = sum;
while (low <= high)
{
mid = (low + high) / 2;
if (check(mid))
{
high = mid - 1;
result = mid;
}
else
{
low = mid + 1;
}
}
cout << result;
return 0;
}
보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다.
한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석을 나누어 주려고 한다.
상자에 빨간 보석이 4개 (RRRR), 파란 보석이 7개 (BBBBBBB) 있었고, 이 보석을 5명의 아이들에게 나누어 주는 경우를 생각해보자. RR, RR, BB, BB, BBB로 보석을 나누어주면 질투심은 3이 되고, 이 값보다 작게 나누어 줄 수 없다.
상자 안의 보석 정보와 학생의 수가 주어졌을 때, 질투심이 최소가 되게 보석을 나누어주는 방법을 알아내는 프로그램을 작성하시오.
입력
첫째 줄에 아이들의 수 N과 색상의 수 M이 주어진다. (1 ≤ N ≤ 10^9, 1 ≤ M ≤ 300,000, M ≤ N)
다음 M개 줄에는 구간 [1, 10^9]에 포함되는 양의 정수가 하나씩 주어진다. K번째 줄에 주어지는 숫자는 K번 색상 보석의 개수이다.
출력
첫째 줄에 질투심의 최솟값을 출력한다.
예제 입력
5 2
7
4
7 5
7
1
7
4
4
예제 출력
3
4
접근방식
질투심이 x일 때, 충족이 되는지만 구하면 된다. 즉, 이분 탐색으로 풀 수 있다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, m;
long long a[300004], low = 1, high = 0, mid, result = 99999999;
bool check(long long mid)
{
long long num = 0;
for (int i = 0; i < m; i++)
{
num += a[i] / mid;
if (a[i] % mid)
{
num++;
}
}
return n >= num;
}
int main()
{
cin >> n >> m;
for (int i = 0; i < m; i++)
{
cin >> a[i];
high = max(high, a[i]);
}
while (low <= high)
{
mid = (low + high) / 2;
if (check(mid))
{
result = min(result, mid);
high = mid - 1;
}
else
{
low = mid + 1;
}
}
cout << result;
return 0;
}
반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀있고, i번째 원판에 적힌 j번째 수의 위치는 (i, j)로 표현한다. 수의 위치는 다음을 만족한다.
(i, 1)은 (i, 2), (i, M)과 인접하다.
(i, M)은 (i, M-1), (i, 1)과 인접하다.
(i, j)는 (i, j-1), (i, j+1)과 인접하다. (2 ≤ j ≤ M-1)
(1, j)는 (2, j)와 인접하다.
(N, j)는 (N-1, j)와 인접하다.
(i, j)는 (i-1, j), (i+1, j)와 인접하다. (2 ≤ i ≤ N-1)
아래 그림은 N = 3, M = 4인 경우이다.
원판의 회전은 독립적으로 이루어진다. 2번 원판을 회전했을 때, 나머지 원판은 회전하지 않는다. 원판을 회전시킬 때는 수의 위치를 기준으로 하며, 회전시킨 후의 수의 위치는 회전시키기 전과 일치해야 한다.
다음 그림은 원판을 회전시킨 예시이다.
원판을 아래와 같은 방법으로 총 T번 회전시키려고 한다. 원판의 회전 방법은 미리 정해져 있고, i번째 회전할때 사용하는 변수는 xi, di, ki이다.
번호가 xi의 배수인 원판을 di방향으로 ki칸 회전시킨다. di가 0인 경우는 시계 방향, 1인 경우는 반시계 방향이다.
원판에 수가 남아 있으면, 인접하면서 수가 같은 것을 모두 찾는다.
그러한 수가 있는 경우에는 원판에서 인접하면서 같은 수를 모두 지운다.
없는 경우에는 원판에 적힌 수의 평균을 구하고, 평균보다 큰 수에서 1을 빼고, 작은 수에는 1을 더한다.
원판을 T번 회전시킨 후 원판에 적힌 수의 합을 구해보자.
입력
첫째 줄에 N, M, T이 주어진다.
둘째 줄부터 N개의 줄에 원판에 적힌 수가 주어진다. i번째 줄의 j번째 수는 (i, j)에 적힌 수를 의미한다.
원판을 x배수 만큼 돌리고 인접한 수는 0으로 만들고 나머지 숫자들만 더하고 평균을 냈다.
원판을 돌릴때는 rotate함수를 사용하였다.
코드
#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,1,0,-1 };
int n, m, t, x, d, k, circle[54][54], visited[54][54], result;
bool flag = 1;
void _rotate(int y, int direction, int k)
{
vector<int> v;
for (int i = 0; i < m; i++)
{
v.push_back(circle[y][i]);
}
if (direction == 1)
{
rotate(v.begin(), v.begin() + k, v.end());
}
else
{
rotate(v.begin(), v.begin() + m - k, v.end());
}
for (int i = 0; i < m; i++)
{
circle[y][i] = v[i];
}
return;
}
void dfs(int y, int x)
{
for (int i = 0; i < 4; i++)
{
int ny = y + dy[i];
int nx = (x + dx[i] + m) % m;
if (ny < 0 || ny >= n || visited[ny][nx]) continue;
if (circle[y][x] == circle[ny][nx])
{
visited[y][x] = visited[ny][nx] = 1;
flag = 0;
dfs(ny, nx);
}
}
}
bool findAdj()
{
flag = 1;
memset(visited, 0, sizeof(visited));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (circle[i][j] == 0 || visited[i][j]) continue;
dfs(i, j);
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (visited[i][j])
{
circle[i][j] = 0;
}
}
}
return flag;
}
void setAverage()
{
int sum = 0;
int cnt = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (circle[i][j] == 0) continue;
sum += circle[i][j];
cnt++;
}
}
double average = (double)sum / (double)cnt;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (circle[i][j] == 0) continue;
if ((double)circle[i][j] > average)
{
circle[i][j]--;
}
else if ((double)circle[i][j] < average)
{
circle[i][j]++;
}
}
}
return;
}
int main()
{
cin >> n >> m >> t;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
cin >> circle[i][j];
}
}
for (int i = 0; i < t; i++)
{
cin >> x >> d >> k;
for (int j = x - 1; j < n; j += x)
{
_rotate(j, d, k);
}
if (findAdj())
{
setAverage();
}
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
result += circle[i][j];
}
}
cout << result;
return 0;
}
