전에 테스트때 풀었던 문제이다. 그런데 그때 구현이 틀렸다. 근데 틀린 원인이 내 생각에는 설계를 잘못한듯. 완전 탐색이긴 한데 , bfs도 어떻게 수행할지 조건들에 대한 내용을 결정하고 , 그것을 깔금하게 구현해야 할듯.
나는 이동할 수 있는 경우가 몇가지인지 제대로 파악 안하고 시작했다.
그리고 일단 로봇의 상태를 어떻게 표현할지 부터 정했어야 했다.
로봇의 상태를 어떻게 표현할지 정확히 생각하고, 배열의 범위 확인도 함수로 구현해서 확인 후 그 함수 내부에서 큐에 넣도록 하니까 깔금하게 금방 구현했는데, 예제만 맞고 테케는 한개만 맞는다..... 왜그러지 ㅠ
#include <string>
#include <vector>
#include<queue>
using namespace std;
enum {
ver = 1,
hori = 2
};
struct elem {
int r, c, dir,cnt;
};
int dir_r[4] = { 0,0,-1,1 };
int dir_c[4] = { 1,-1,0,0 };
queue<elem> q;
int R, C;
int arr[101][101];
int visit[3][101][101] = { 0 };
void checkAndPush(int r, int c, int dir,int cnt) {
if (!(r >= 0 && r < R && c >= 0 && c < C)) {
return;
}
if (dir == ver) {
if ( c+1 < C && arr[r][c] == 0 && arr[r][c + 1] == 0 && visit[dir][r][c] == 0) {
visit[dir][r][c] = 1;
q.push({ r,c,dir,cnt });
}
}
else if (dir == hori) {
if (r - 1 >= 0 && arr[r][c] == 0 && arr[r - 1][c] == 0 && visit[dir][r][c] == 0) {
visit[dir][r][c] = 1;
q.push({ r,c,dir,cnt });
}
}
}
int solution(vector<vector<int>> board) {
int answer= 0;
R = board.size();
C = board.size();
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
arr[i][j] = board[i][j];
}
}
q.push(elem{ 0, 0, ver,0 });
visit[ver][0][0] = 1;
while (!q.empty()) {
elem cur = q.front();
q.pop();
int r = cur.r;
int c = cur.c;
int dir = cur.dir;
int cnt = cur.cnt;
if (dir == ver && r == R - 1 && c == C - 2) {
answer = cnt;
break;
}
else if (dir == hori && r == R - 1 && c == C - 1) {
answer = cnt;
break;
}
int nr, nc,ndir,ncnt;
//move ver
for (int i = 0; i < 4; i++) {
nr = r + dir_r[i];
nc = c + dir_c[i];
ndir = dir;
ncnt = cnt + 1;
checkAndPush( nr,nc,ndir,ncnt );
}
if (dir == ver) {
ndir = hori;
ncnt = cnt+1;
checkAndPush(r,c,ndir,ncnt);
checkAndPush(r, c+1, ndir, ncnt);
checkAndPush(r+1, c, ndir, ncnt);
checkAndPush(r+1, c+1, ndir, ncnt);
}
else if (dir == hori) {
ndir = ver;
ncnt = cnt + 1;
checkAndPush(r, c, ndir, ncnt);
checkAndPush(r, c - 1, ndir, ncnt);
checkAndPush(r - 1, c, ndir, ncnt);
checkAndPush(r - 1, c - 1, ndir, ncnt);
}
}//while
return answer;
}
아 이 조건을 빼먹었었다.
#include <string>
#include <vector>
#include<queue>
using namespace std;
enum {
ver = 1,
hori = 2
};
struct elem {
int r, c, dir,cnt;
};
int dir_r[4] = { 0,0,-1,1 };
int dir_c[4] = { 1,-1,0,0 };
queue<elem> q;
int R, C;
int arr[101][101];
int visit[3][101][101] = { 0 };
void checkAndPush(int r, int c, int dir,int cnt) {
if (!(r >= 0 && r < R && c >= 0 && c < C)) {
return;
}
if (dir == ver) {
if ( c+1 < C && arr[r][c] == 0 && arr[r][c + 1] == 0 && visit[dir][r][c] == 0) {
visit[dir][r][c] = 1;
q.push({ r,c,dir,cnt });
}
}
else if (dir == hori) {
if (r - 1 >= 0 && arr[r][c] == 0 && arr[r - 1][c] == 0 && visit[dir][r][c] == 0) {
visit[dir][r][c] = 1;
q.push({ r,c,dir,cnt });
}
}
}
int solution(vector<vector<int>> board) {
int answer= 0;
R = board.size();
C = board.size();
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
arr[i][j] = board[i][j];
}
}
q.push(elem{ 0, 0, ver,0 });
visit[ver][0][0] = 1;
while (!q.empty()) {
elem cur = q.front();
q.pop();
int r = cur.r;
int c = cur.c;
int dir = cur.dir;
int cnt = cur.cnt;
if (dir == ver && r == R - 1 && c == C - 2) {
answer = cnt;
break;
}
else if (dir == hori && r == R - 1 && c == C - 1) {
answer = cnt;
break;
}
int nr, nc,ndir,ncnt;
//move ver
for (int i = 0; i < 4; i++) {
nr = r + dir_r[i];
nc = c + dir_c[i];
ndir = dir;
ncnt = cnt + 1;
checkAndPush( nr,nc,ndir,ncnt );
}
if (dir == ver) {
ndir = hori;
ncnt = cnt+1;
if(arr[r-1][c+1] == 0)
checkAndPush(r,c,ndir,ncnt);
if(arr[r-1][c]==0)
checkAndPush(r, c+1, ndir, ncnt);
if(arr[r+1][c+1]==0)
checkAndPush(r+1, c, ndir, ncnt);
if(arr[r+1][c] ==0)
checkAndPush(r+1, c+1, ndir, ncnt);
}
else if (dir == hori) {
ndir = ver;
ncnt = cnt + 1;
if( arr[r-1][c+1] == 0)
checkAndPush(r, c, ndir, ncnt);
if(arr[r-1][c-1] == 0)
checkAndPush(r, c - 1, ndir, ncnt);
if(arr[r][c+1] == 0)
checkAndPush(r - 1, c, ndir, ncnt);
if(arr[r][c-1]==0)
checkAndPush(r - 1, c - 1, ndir, ncnt);
}
}//while
return answer;
}
다른 사람들의 풀이를 좀 봤는데, 너무 다양하다. 난 내것이 가장 좋아보이는데 남의 코드에서 뭔가 배우고 싶은데 너무 ㅁ길고 뭐라 썼는지 모르겠다..... 그래도 읽어봐야겠...지?
문자열 압축
시험볼때 풀었긴한데, 다시 효율적으로 설계해서 빠르게 푸는 연습을 해보자.
음 다시봐도 잘 모르겠다.
aabbaccc -> 2a2ba3c 아 이렇게 못하고 정해진 길이로만 자를 수 있다.
문자열 길이가 1~1000 이니까 1000개의 길이에 대해서 자르고 문자열을 한번 순회하면서 자르겠지? 그러면 1000^2 시간 복잡도다.
그러면 구현해야 되는건 자르는 문자열의 길이가 정해지면 그 길이로 자르는 함수를 구현해야 한다.
문자열 길이를 size라 하자. 간단하게 생각하면 쭉 문자열을 가면서 해당 위치에서 뒤로 size만큼 반복될되는지 확인하면 된다.
그러면 해당 size만큼을 넣고 사이즈만 큼 인덱스를 이동해서 해당 문자열이 같은지 확인하고 아니면 인덱스를 1만큼 (1만큼 이동하면 새로 압출할 문자열에 문자 한개 넣고 새로운 확인 문자열을 size 크기로 생성한다.) 이동하고 일치하면 인덱스를 size만큼 이동 시킨다 (그리고 몇번 일치하는지 센다, 1만큼 이동시 cnt가 2이상이면 새로운 배열에 넣는다) . 이렇게 해서 압축한 문자열을 새로운 벡터에 저장한다. 그리고 min 배열로 최소 길이를 체크한다.
아 size만큼 확인하고 아니면 size만큼 다시 빼주고 그 다음 문자열 부터 확인한다.
음 이상하게 들어간다. 왜 설계를 못하는 걸까
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int capsulate(string s,int size) {
string check;
string capsulated;
int cnt=1;
check = s.substr(0, size);
int i;
for (i = size; i < s.size(); ) {
if (s.substr(i, size) == check) {
cnt++;
i += size;
}
else {
if (cnt >= 2) {
capsulated.push_back(cnt);
}
if (cnt >= 1) {
for (int j = 0; j < check.size(); j++)
capsulated.push_back(check[j]);
i -= (size - 1);
}
cnt = 0;
check = s.substr(i, size);
capsulated.push_back(s[i]);
}
}
if (capsulated.size() == 0)
capsulated = s;
return capsulated.size();
}
int solution(string s) {
int answer = 0;
int minv = 1000000;
for (int i = 1; i <= s.size(); i++) {
minv = min(capsulate(s, i),minv);
}
answer = minv;
cout << minv;
return answer;
}
int main() {
solution("aabbaccc");
}
내가 설계한대로 해보니까 문제가 체크 문자열을 만들고 그 위치 인덱스에서 틀리면 그냥 +1 하고 맞으면 +size인데, +size했을때 틀리면 다시 +2한곳에서 체크 문자열도 새로 만들고 거기서 다시 확인해야한다.
근데 이제 틀렸을때 체크 문자열이 맞은 횟수를 푸쉬해 줘야하는데, 틀렸다고 무조건 푸쉬하는게 아니라, 한번이상 맞으면 푸쉬하고 두번이상 맞으면 숫자까지 푸쉬한다.
근데 이제 틀리면 cnt가 0이면 한 글자만 넣는다.
1. check가 맞았었고 다음 size만큼이 틀리다
i -= size 하고
i += 1에서 check 문자열을 다시 만들어야 한다.
그리고 해당 i에서 size만큼이 체크랑 같은지 다시 확인해야 한다.
2. check가 맞았었고 다음 size만큼도 맞다.
i += size 해서 다시 size만큼이 같은지 확인하면 된다.
3. check가 틀리다
1. 체크가 연속해서 2번 나타나는지 -> 나타난다.
-> 3번 나타나는지 확인하고 나타나면 size만큼 더한다.
-> 3번은 아니다 그러면 i 변경없이 그냥 다시 1로.
->4번 '' -> n번에서 안나타나면 i = i - size + 1로 하고 다시 1로 온다.
2. 체크가 연속해서 2번 나타나는지 -> 안나타난다.
-> 현재 인덱스 문자열에서 한개만 그냥 푸쉬한다. -> i =+1 한다.
-> i+1 된 상태에서 체크를 새로 만들고 1로 다시 온다.
음 이렇게 했는데 아래 경우가 틀리다. 앞에서 부터 잘라야 되는건가?? 왜 문제에서는 못찾겠지 그 조건을. 자주 느끼는건데 예시를 다 보고 푸는게 맞는거 같다.
입출력 예 #5
문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.
문제는 앞에서 부터 그냥 자르고 같은 문자열이 몇번 반복되는지 확인하는 문제이다. 나는 다르게 해석해서 앞뒤로 같은 문자열을 그냥 압축해버리는 식으로 생각했다. 실전에서도 후자로 생각해서 푸는데 1시간 넘게 걸렸다...... 사실 틀렸던건가?
그렇게 구현했는데 72점이다....
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
int capsulate(string s, int size) {
vector<string> vec;
string ans="";
for (int i = 0; i < s.size();) {
if (i + size < s.size()) {
vec.push_back(s.substr(i, size));
i += size;
}
else
{
vec.push_back(s.substr(i, s.size() - i));
break;
}
}
int cnt = 1;
for (int i = 0; i < vec.size(); i++) {
if (vec[i] == vec[i + 1]) {
cnt++;
if (i == vec.size() -2) {
if (cnt >= 2) {
ans.push_back(cnt);
}
for (int j = 0; j<vec[i].size(); j++)
ans.push_back(vec[i][j]);
break;
}
}
else {
if (cnt >= 2) {
ans.push_back(cnt);
}
for(int j=0;j<vec[i].size();j++)
ans.push_back(vec[i][j]);
if (i == vec.size() - 2) {
for (int j = 0; j<vec[i+1].size(); j++)
ans.push_back(vec[i+1][j]);
break;
}
cnt = 1;
}
}
return ans.size();
}
int solution(string s) {
int answer = 0;
int minv = s.size();
for (int i = 1; i <= s.size(); i++) {
minv = min(capsulate(s, i), minv);
}
answer = minv;
//cout << minv;
return answer;
}
틀린 이유를 찾아야 한다.... 근데 모르겠다.
아 solution에서 size를 s.size()까지 넣어 준게 문제 같다. 그래서 vec에 1개 원소만 있는 경우도 있음..... 그러면 나는 최소 2개 이상일때로 구현한건데 문제가 생긴다.
그래도 여전히 틀렸다....아 문자열을 너무 못한다.
'알고리즘 문제 풀기' 카테고리의 다른 글
| 프로그래머스 - 카카오 2018 블라인드 테스트 (추석 트래픽) (0) | 2020.01.04 |
|---|---|
| 백준 - 1725번 히스토그램,6549 히스토그램에서 가장 큰 직사각형 (0) | 2020.01.03 |
| 프로그래머스 - 스택/큐 : 프린터, 쇠막대기, 주식 가격 (0) | 2019.12.30 |
| 프로그래머스 - 스택 : 탑, 다리를 지나는 트럭, 기능개발 (0) | 2019.12.27 |
| 프로그래머스 - 카카오 2020 블라인드 테스트 (자물쇠와 열쇠, 가사 검색) (0) | 2019.12.27 |