문제에서 주어진대로 구현해주면 된다. 올바른 괄호를 체크할때 스택을 사용했다. 딱히 어려운 부분은 없고 문제를 정확히 읽고 구현해주면 되는 문제인데 u를 구할때 약간 생각이 필요했다. 문자열을 탐색하면서 '('의 개수와 ')'의 개수가 같아질 때가 u이고 나머지 문자열이 v가 된다.
아마 처음 긴장을 풀어주기 위해 1번 문제로 준비한 문제가 아닐까 싶다. 이 문제에서의 핵심은 스택을 사용하는 거라 생각한다. 바구니는 아래칸부터 인형이 순서대로 쌓이는 구조이며 이는 한쪽에서만 입력이 일어남을 알 수 있다. 크레인이 인형을 뽑고나서 스택의 top과 뽑은 인형이 같다면 스택을 pop하고 정답을 2 더해주면 되는 문제이다.
#include <cstdio>
#include <queue>
using namespace std;
int n, m;
const int dy[] = { -1, 0, 1, 0 };
const int dx[] = { 0, 1, 0, -1 };
int map[100][100];
int dist[100][100];
void bfs(int y, int x) {
queue<pair<int, int> > q;
q.push(make_pair(y, x));
dist[y][x] = 1;
while (!q.empty()) {
y = q.front().first;
x = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny < 0 || nx < 0 || ny >= n || nx >= m || dist[ny][nx] != 0 || map[ny][nx] != 1) continue;
q.push(make_pair(ny, nx));
dist[ny][nx] = dist[y][x] + 1;
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int y = 0; y < n; y++) {
for (int x = 0; x < m; x++) {
scanf("%1d", &map[y][x]);
}
}
bfs(0, 0);
printf("%d\n", dist[n - 1][m - 1]);
return 0;
}
1. ",{" 기준으로 문자열을 잘라 집합을 구한 후 집합의 크기를 기준으로 정렬한다. 2. i번째 집합에 속해있는 숫자묶음을 추출한뒤 answer 리스트에 없는 숫자만 추가해주면 된다.
c++로 풀면 꽤나 소스도 길어지고 빡빡했을거 같았다. 왜냐하면 숫자가 아닌 문자들을 다 제외하는 로직을 구현을 시작해야 해서 이참에 파이썬을 한번 써봤다. 왜 문자열은 파이썬을 사용하면 금방 풀 수 있다고 하는지 느꼈다. 문자열 문제에 항상 힘들어했는데 파이썬을 애용해봐야겠다
import re
def solution(s):
answer = [] # 정답
numberSet = s.split(',{') # 집합을 구함
numberSet.sort(key = len) # 집합 크기를 기준으로 정렬
for i in numberSet :
number = re.findall("\d+", i) # 숫자묶음을 추출
for j in number :
if int(j) not in answer :
answer.append(int(j))
return answer
완전탐색 문제인데 약간 생각할 부분이 있었다. n의 범위가 50만까지인데 채널은 무한이기 때문에 뒤에서 탐색하는 경우 버튼을 더 적게 누를수도 있기 때문이다. 또 숫자버튼을 누르고 + 또는 -버튼 1개만 계속 눌러야 한다. 왜냐하면 +버튼을 누르다 -버튼을 누르고 다시 +버튼을 누르면 중복이 발생하기 때문에 최소값이 될 수 없기 때문이다.
#include <iostream>
#include <algorithm>
using namespace std;
int n, m;
bool brokenButton[10];
// 숫자버튼을 누른 채널으로 이동 가능한지 확인하는 함수
bool checkButton(int channel) {
if (channel == 0) {
if (brokenButton[0]) return false;
else return true;
}
while (channel) {
if (brokenButton[channel % 10]) return false;
else channel /= 10;
}
return true;
}
// checkButton을 통과한 채널의 자릿수를 구하는 함수
int getChannelDigit(int channel) {
int ret = 0;
if (channel == 0) return 1;
while (channel) {
channel /= 10;
ret++;
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
cin >> n >> m;
int buttonNumber;
for (int i = 0; i < m; i++) {
cin >> buttonNumber;
brokenButton[buttonNumber] = 1;
}
int ans = 987654321;
// 뒤에서 탐색하는게 더 효과적인 경우도 있으므로 n의 범위를 2배 늘림
// 예를 들어 6버튼만 안고장나고 60만번 채널로 이동하고 싶은 경우
// 초기 100번 채널에서 +버튼만 누르는 것 보다 666,666채널에서 -버튼을 누르는 횟수가 더 적음
for (int i = 0; i <= 1000000; i++) {
int channel = i;
if (checkButton(channel)) {
// 숫자버튼을 눌러 이동할때 필요한 자릿수
int digit = getChannelDigit(channel);
// 숫자버튼 이동과 +버튼 또는 -버튼 클릭의 합을 비교
ans = min(ans, digit + abs(n - channel));
}
}
cout << min(ans, abs(n - 100));
return 0;
}
처음에 시간복잡도를 생각 안하고 구현했더니 시간초과가 났다. 다음부터는 문제풀이 이전에 꼭 시간복잡도를 먼저 계산하고 풀이해야겠다.
이 문제는 상어의 정보가 주어지고 낚시왕이 왼쪽에서 오른쪽으로 이동하면서 잡은 상어의 크기의 총 합을 출력하는 문제이다.
문제에서 요구하는 구현사항은 2가지인데 순서에 맞게 구현해줘야 한다.
나 같은 경우는 낚시왕이 (0, 0)에서 시작해 x축 이동을 하면서 1번을 구현했다.
2번 조건을 구현하기 위해 catchShark(int x) 함수를 만들었다.
catchShark(int x) 함수
낚시왕이 위치한 x좌표를 넘겨줘서 y축 탐색을 해 가장 가까운 상어를 잡는 함수이다.
int catchShark(int x) {
int ret = 0;
for (int y = 1; y <= r; y++) {
if (map[y][x] != 0) {
ret = v[map[y][x]].z;
v[map[y][x]].dead = 1;
map[y][x] = 0;
break;
}
}
return ret;
}
3번 조건이 가장 까다로웠다. 이 조건은 moveShark() 함수를 만들었다.
moveShark() 함수
살아있는 상어 수만큼 반복하면서 상어 좌표를 이동해주는 함수이다. 행 처리와 열 처리가 같기 때문에 열 처리를 기준으로 설명하겠습니다.
여기서 가장 중요한게 speed = speed % ((c - 1) * 2) 부분인데 이 처리를 하지 않으면 시간초과가 납니다.
만약 r=4, c=6인 경우 상어가 방향전환을 하고 움직일때 1번 열과 6번 열은 1번씩만 자리잡고 2, 3, 4, 5번 열은 2번씩 자리잡는다.
빨간 색을 1번만 위치하는 열이고 파랑색은 기존 위치 초록색을 방향전환을 했을때 자리잡는 위치이다. 이 표를 가지고 시뮬레이션을 해보면 규칙을 파악할 수 있다. 이 규칙을 이용해서 반복횟수를 줄여 시간초과를 벗어나면 된다.
이후 조건에 따라 구현해줬다. 상어가 이동한 자리가 빈칸이면 상어 번호를 map에 저장하고 움직인 상어가 위치한다면 크기를 비교해 먹거나 먹히도록 구현했다. 움직이지 않은 상어가 위치하는 경우는 반복문을 통해 나중에 처리하기 때문에 현재 위치한 상어를 위치시키면 된다.
void moveShark() {
for (int i = 1; i <= m; i++) {
// 죽은 상어는 건너뛴다
if (v[i].dead) continue;
// 움직일 상어 정보
int y = v[i].r;
int x = v[i].c;
int speed = v[i].s;
int dir = v[i].d;
int size = v[i].z;
// 현재 움직일 상어 기존 위치 초기화
if (map[y][x] == i) map[y][x] = 0;
// 위, 아래
if (dir == 0 || dir == 1) {
speed = speed % ((r - 1) * 2);
while (speed--) {
int ny = y + dy[dir];
if (1 > ny || ny > r) dir = 1 - dir;
y += dy[dir];
}
}
// 오른쪽 왼쪽
else {
speed = speed % ((c - 1) * 2);
while (speed--) {
int nx = x + dx[dir];
if (1 > nx || nx > c) dir = 5 - dir;
x += dx[dir];
}
}
// 이동한 상어 위치 최신화
v[i].r = y;
v[i].c = x;
v[i].d = dir;
// 이동한 위치가 빈칸인 경우 => 위치 이동
if (map[y][x] == 0) {
map[y][x] = i;
}
// 이동한 위치에 이미 이동을 완료한 상어가 있는 경우 => 잡아먹거나 잡아 먹힘
else if (i > map[y][x]) {
// 이동한 상어의 사이즈가 더 큰 경우
if (size > v[map[y][x]].z) {
v[map[y][x]].dead = 1;
map[y][x] = i;
}
// 이동한 상어의 사이즈가 더 작은 경우
else {
v[i].dead = 1;
}
}
// 이동한 위치에 아직 이동 안 한 상어가 있는 경우 => 이후에 재 처리하기 때문에 뒤집어 씌움
else {
map[y][x] = i;
}
}
}
기존에 시간초과했던 방법 즉, 문제대로 그냥 구현한 방법의 시간복잡도는 다음과 같다.
상어의수(10000) X 속도(1000) X 낚시왕이 움직이는 열의 수(100)
= 10^4 * 10^3 * 10^2 = 10^9 = 1,000,000,000 (10억) 번의 연산이 필요하다.
1초에 1억번 계산가능하다는 가정하에 이 문제는 단순 구현으로는 1초안에 해결할 수 없다.
시간 초과때문에 힘들었던 문제인데 진짜 시간복잡도를 먼저 계산하는게 왜 중요한지 다시 깨우친 문제이다. 시험장에서였으면 아마 시간초과로 탈락했을거 같다.
#include <iostream>
#include <vector>
using namespace std;
struct SHARK {
int r, c, s, d, z;
bool dead;
};
int r, c, m;
int map[101][101];
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0, 1, -1 };
vector<SHARK> v;
void init() {
cin >> r >> c >> m;
// 1번부터 시작
v.push_back({ 0,0,0,0,0,0 });
for (int i = 1; i <= m; i++) {
SHARK shark;
cin >> shark.r >> shark.c >> shark.s >> shark.d >> shark.z;
shark.dead = 0;
shark.d -= 1;
v.push_back(shark);
map[shark.r][shark.c] = i;
}
}
int catchShark(int x) {
int ret = 0;
for (int y = 1; y <= r; y++) {
if (map[y][x] != 0) {
ret = v[map[y][x]].z;
v[map[y][x]].dead = 1;
map[y][x] = 0;
break;
}
}
return ret;
}
void moveShark() {
for (int i = 1; i <= m; i++) {
// 죽은 상어는 건너뛴다
if (v[i].dead) continue;
// 움직일 상어 정보
int y = v[i].r;
int x = v[i].c;
int speed = v[i].s;
int dir = v[i].d;
int size = v[i].z;
// 현재 움직일 상어 기존 위치 초기화
if (map[y][x] == i) map[y][x] = 0;
// 위, 아래
if (dir == 0 || dir == 1) {
speed = speed % ((r - 1) * 2);
while (speed--) {
int ny = y + dy[dir];
if (1 > ny || ny > r) dir = 1 - dir;
y += dy[dir];
}
}
// 오른쪽 왼쪽
else {
speed = speed % ((c - 1) * 2);
while (speed--) {
int nx = x + dx[dir];
if (1 > nx || nx > c) dir = 5 - dir;
x += dx[dir];
}
}
// 이동한 상어 위치 최신화
v[i].r = y;
v[i].c = x;
v[i].d = dir;
// 이동한 위치가 빈칸인 경우 => 위치 이동
if (map[y][x] == 0) {
map[y][x] = i;
}
// 이동한 위치에 이미 이동을 완료한 상어가 있는 경우 => 잡아먹거나 잡아 먹힘
else if (i > map[y][x]) {
// 이동한 상어의 사이즈가 더 큰 경우
if (size > v[map[y][x]].z) {
v[map[y][x]].dead = 1;
map[y][x] = i;
}
// 이동한 상어의 사이즈가 더 작은 경우
else {
v[i].dead = 1;
}
}
// 이동한 위치에 아직 이동 안 한 상어가 있는 경우 => 이후에 재 처리하기 때문에 뒤집어 씌움
else {
map[y][x] = i;
}
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
init();
// 예외 처리
if (m == 0) {
cout << 0;
return 0;
}
int ans = 0;
for (int x = 1; x <= c; x++) {
ans += catchShark(x);
moveShark();
}
cout << ans;
return 0;
}
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
const int START_BUS_MINUTE = 9 * 60;
const int LAST_BUS_MINUTE = 24 * 60;
int getIntMinute(string time) {
int ret = ((time[0]-'0')*10 + (time[1]-'0')) * 60;
ret += (time[3]-'0')*10 + (time[4]-'0');
return ret;
}
string getStringTime(int time) {
string ret = to_string((time/600));
ret += to_string((time/60)%10);
ret += ':';
ret += to_string((time%60)/10);
ret += to_string((time%60)%10);
return ret;
}
string solution(int n, int t, int m, vector<string> timetable) {
string ret = "";
vector<int> v;
for (int i=0; i<timetable.size(); i++) v.push_back(getIntMinute(timetable[i]));
sort(v.begin(), v.end());
int boardCount = 0;
int startTime = START_BUS_MINUTE;
for (int i=0; i<n; i++) {
// 문제 조건 23:59까지만 가능
if (startTime > LAST_BUS_MINUTE) break;
int maxBoardCount = m;
for (int j=boardCount; j<v.size(); j++) {
if (maxBoardCount == 0 || v[j] > startTime) break;
boardCount++;
maxBoardCount--;
}
// 마지막 버스
if (i == n-1) {
// 탑승할 자리가 없는 경우 1분 일찍 나옴
if (maxBoardCount == 0) startTime = v[boardCount-1] - 1;
} else startTime += t;
}
ret = getStringTime(startTime);
return ret;
}
