아래 모든 문제들은 프로그래머스에서 제공 되는 문제를 이용하였습니다, 감사합니다.
- 3번 방문길이 못품
1. 땅따먹기
문제 설명
땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.
예를 들면,
| 1 | 2 | 3 | 5 |
| 5 | 6 | 7 | 8 |
| 4 | 3 | 2 | 1 |
로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.
마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.
제한사항
- 행의 개수 N : 100,000 이하의 자연수
- 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
- 점수 : 100 이하의 자연수
입출력 예
풀이
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int> > land)
{
int answer = 0;
// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
int s_len = land.size();
int i = 0;
while(i < s_len - 1)
{
land[1+i][0] += max(max(land[i][1], land[i][2]), land[i][3]);
land[1+i][1] += max(max(land[i][0], land[i][2]), land[i][3]);
land[1+i][2] += max(max(land[i][0], land[i][1]), land[i][3]);
land[1+i][3] += max(max(land[i][0], land[i][1]), land[i][2]);
i++;
}
answer = *max_element(land[s_len - 1].begin(), land[s_len-1].end());
return answer;
}설명
- 이문제 나는 이렇게 못풀었다..
- ai부캠 코테 준비할떄 스터디 동료분이 이렇게 풀었던거 같아 풀어보았는데 잘 풀렸다.
- 풀이는, 2 번쨰 행부터, 위의 값들을 보면서 고를수 있는 최대값들을 골라준다.
- 배열 끝까지 최대값들을 골라주며 내려가고 마무리로 최대값을 고르면, answer 이다.
2. 게임 맵 최단거리
문제 설명
ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.
지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.
위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.
게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.
제한사항
- maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
- n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
- maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
- 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
입출력 예
풀이
첫 번쨰 풀이
#include<vector>
#include <iostream>
using namespace std;
int dfs(vector<vector<int>> maps, int max_n, int max_m, int &answer, int n, int m, int count)
{
if (answer != -1 && answer <= count)
return 0;
maps[n][m] = 0;
if(n == max_n - 1 && m == max_m - 1)
{
if(answer == -1 || answer > count)
answer = count;
return 0;
}
if(n - 1 >= 0 && maps[n - 1][m])
dfs(maps, max_n, max_m, answer, n - 1, m, count + 1);
if(n + 1 < max_n && maps[n + 1][m])
dfs(maps, max_n, max_m, answer, n + 1, m, count + 1);
if(m - 1 >= 0 && maps[n][m - 1])
dfs(maps, max_n, max_m, answer, n, m - 1, count + 1);
if(m + 1 < max_m && maps[n][m + 1])
dfs(maps, max_n, max_m, answer, n, m + 1, count + 1);
return 0;
}
int solution(vector<vector<int>> maps)
{
int n = 0;
int m = 0;
int answer = -1;
dfs(maps, maps.size(), maps[0].size(), answer, n, m, 1);
return answer;
}
두 번쨰 풀이
#include<vector>
#include <queue>
#include <iostream>
using namespace std;
typedef struct t_pos_nm{
int n;
int m;
int c;
} s_pos_nm;
void bfs(vector<vector<int>> &maps, s_pos_nm &pos_nm, queue<s_pos_nm> &q, int *max_n, int *max_m, int &answer, s_pos_nm &tmp)
{
if(q.size() == 0)
return ;
pos_nm = q.front();
if(pos_nm.n == (*max_n) - 1 && pos_nm.m == (*max_m) - 1)
{
answer = pos_nm.c + 1;
return ;
}
q.pop();
if (maps[pos_nm.n][pos_nm.m]) {
maps[pos_nm.n][pos_nm.m] = 0;
if(pos_nm.n - 1 >= 0 && maps[pos_nm.n - 1][pos_nm.m])
{
tmp.n = pos_nm.n - 1;
tmp.m = pos_nm.m;
tmp.c = pos_nm.c + 1;
if(tmp.n == (*max_n) - 1 && tmp.m == (*max_m) - 1)
{
answer = tmp.c + 1;
return;
}
q.push(tmp);
}
if(pos_nm.n + 1 < (*max_n) && maps[pos_nm.n + 1][pos_nm.m])
{
tmp.n = pos_nm.n + 1;
tmp.m = pos_nm.m;
tmp.c = pos_nm.c + 1;
if(tmp.n == (*max_n) - 1 && tmp.m == (*max_m) - 1)
{
answer = tmp.c + 1;
return;
}
q.push(tmp);
}
if(pos_nm.m - 1 >= 0 && maps[pos_nm.n][pos_nm.m - 1])
{
tmp.n = pos_nm.n;
tmp.m = pos_nm.m - 1;
tmp.c = pos_nm.c + 1;
if(tmp.n == (*max_n) - 1 && tmp.m == (*max_m) - 1)
{
answer = tmp.c + 1;
return;
}
q.push(tmp);
}
if(pos_nm.m + 1 < (*max_m) && maps[pos_nm.n][pos_nm.m + 1])
{
tmp.n = pos_nm.n;
tmp.m = pos_nm.m + 1;
tmp.c = pos_nm.c + 1;
if(tmp.n == (*max_n) - 1 && tmp.m== (*max_m) - 1)
{
answer = tmp.c + 1;
return;
}
q.push(tmp);
}
}
bfs(maps, pos_nm, q, max_n, max_m, answer, tmp);
return ;
}
int solution(vector<vector<int>> maps)
{
queue<s_pos_nm> q;
s_pos_nm pos_nm = {0,0,0};
s_pos_nm tmp = {0,0,0};
//문제는 이렇게 접근하게 되면, pos_nm와 tmp를 vector로 넘겨주었을때 시간초과가 나온다.
// 젤 좋은 방법은 세진님이 하신 방법대로 pair로 포스 위치를 넘기고,
// 지나온 맵인지 확인하는 값은, pos_nm의 c나 3번쨰 인덱스가 아니라, 따로 맵을 을 만들어서 넘기는게 좋을거 같다.
// queue<vector<int>> q;
// vector<int> pos_nm (3,0);
// vector<int> tmp(3,0);
int answer = -1;
int n = maps.size();
int m = maps[0].size();
q.push(pos_nm);
bfs(maps, pos_nm, q, &n, &m, answer , tmp);
return answer;
}
세 번쨰 풀이
typedef struct t_pos_nm{
int n;
int m;
int c;
} s_pos_nm;
//wndrksdptj 11 까지 가는거, 마지막까지 가는거
int solution(vector<vector<int>> maps)
{
queue<s_pos_nm> q;
s_pos_nm pos_nm = {0,0,0};
q.push(pos_nm);
s_pos_nm tmp = {0,0,0};
int answer = -1;
// bfs(maps, pos_nm, q, maps.size(), maps[0].size(), answer , tmp);
int max_m = maps[0].size();
int max_n = maps.size();
while(!q.empty())
{
pos_nm = q.front();
if(pos_nm.n == max_n - 1 && pos_nm.m == max_m - 1)
{
answer = pos_nm.c + 1;
break;
}
if (maps[pos_nm.n][pos_nm.m]) {
maps[pos_nm.n][pos_nm.m] = 0;
// q.pop();
if(pos_nm.n - 1 >= 0 && maps[pos_nm.n - 1][pos_nm.m])
{
tmp.n = pos_nm.n - 1;
tmp.m = pos_nm.m;
tmp.c = pos_nm.c + 1;
// if(tmp.n == max_n - 1 && tmp.m == max_m - 1)
// {
// answer = tmp.c + 1;
// break;
// }
q.push(tmp);
}
if(pos_nm.n + 1 < max_n && maps[pos_nm.n + 1][pos_nm.m])
{
tmp.n = pos_nm.n + 1;
tmp.m = pos_nm.m;
tmp.c = pos_nm.c + 1;
// if(tmp.n == max_n - 1 && tmp.m == max_m - 1)
// {
// answer = tmp.c + 1;
// break;
// }
q.push(tmp);
}
if(pos_nm.m - 1 >= 0 && maps[pos_nm.n][pos_nm.m - 1])
{
tmp.n = pos_nm.n;
tmp.m = pos_nm.m - 1;
tmp.c = pos_nm.c + 1;
// if(tmp.n == max_n - 1 && tmp.m == max_m - 1)
// {
// answer = tmp.c + 1;
// break;
// }
q.push(tmp);
}
if(pos_nm.m + 1 < max_m && maps[pos_nm.n][pos_nm.m + 1])
{
tmp.n = pos_nm.n;
tmp.m = pos_nm.m + 1;
tmp.c = pos_nm.c + 1;
// if(tmp.n == max_n - 1 && tmp.m == max_m - 1)
// {
// answer = tmp.c + 1;
// break;
// }
q.push(tmp);
}
}
q.pop();
}
return answer;
}
설명
첫 번쨰 코드
- 첫 번쨰 코드는 bfs로 접근을 했었다.
- 문제는 이렇게 bfs로 접근을하게 되면, 정말 답을 찾을떄까지 끝도없이 돌릴경우가 생긴다. 예를들면 하나의 길이 엄청 길면 그길의 끝에 닿을떄 까지 계속해서 진행한뒤에 정답인 길을 탐색할수 있다.
두 번쨰 코드
- bfs로 풀이를 진행했다.
- 한번 길을 진행할떄 갈수 있는 모든 길 들을 같이 하나씩 증가시키면서 탐색해 본다.
- 방법은, 입력으로 주어지는 maps를 통해, 동서남북 으로 인접한 길중 갈수 있는 길을 탐색하고, 큐에 넣는다.
- 그리고 큐를 하나씩 빼면서 담은 순서대로 뺴면서, 그 인덱스에서 다시 갈수 잇는 길들을 탐색하고 저장하는 식으로 진해한다.
- 문제는 여기서 나는 재귀로 돌렸기때문에, 메게변수를 레퍼런스나 주소 처리안해주면, 계속해서 새로운 값들을 생성하기 떄문에 속도가 느려진다.
세 번째 코드
- 두번쨰 코드와 비슷하다.
- 하지만 이번엔 재귀를 쓰지 않고 마무리 지었다.
* 그외 정리
- 원래 bfs는 방문한 배열을 새로 생성해서 방문한 곳을 기록해야하는데, 나는 그 기록을 초기 입력으로 준 maps에 저장하면서 진행하고, deep의 값은 큐에 같이 저장하는 식으로 정리를 했다. 떄문에 더 어려웟던거 같다.
- 다음번에 새로운 maps를 만들어 주어, 방문 기록을 남기면 좋을거 같다.
3. 방문 길이(못품)
문제 설명
게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다.
-
U: 위쪽으로 한 칸 가기
-
D: 아래쪽으로 한 칸 가기
-
R: 오른쪽으로 한 칸 가기
-
L: 왼쪽으로 한 칸 가기
캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다.
제한사항
- dirs는 string형으로 주어지며, 'U', 'D', 'R', 'L' 이외에 문자는 주어지지 않습니다.
- dirs의 길이는 500 이하의 자연수입니다.
입출력 예
풀이
#include <string>
#include <iostream>
#include <vector>
using namespace std;
int solution(string dirs) {
int answer = 0;
// vector<int> vec(3,-1)
vector<int> vec(2,0);
vector<vector<int>> row_LR(10, vector<int>(10, 0));
for (int i = 0; i < dirs.size(); i++)
{
if(dirs[i] == 'L')
{
if (vec[0] == -5)
continue;
vec[0]--;
if(row_LR[vec[1] + 5][vec[0] + 5] != 1)
{
row_LR[vec[1] + 5][vec[0] + 5] = 1;
answer++;
}
}
else if(dirs[i] == 'R')
{
if(vec[0] == 5)
continue;
vec[0]++;
if(row_LR[vec[1] + 5][vec[0] + 5] != 1)
{
row_LR[vec[1] + 5][vec[0] + 5] = 1;
answer++;
}
}
else if(dirs[i] == 'U')
{
if(vec[1] == 5)
continue;
vec[1]++;
if(row_LR[vec[1] + 5][vec[0] + 5] != 1)
{
row_LR[vec[1] + 5][vec[0] + 5] = 1;
answer++;
}
}
else if(dirs[i] == 'D')
{
if(vec[1] == -5)
continue;
vec[1]--;
if(row_LR[vec[1] + 5][vec[0] + 5] != 1)
{
row_LR[vec[1] + 5][vec[0] + 5] = 1;
answer++;
}
}
}
for(int i = 0; i < row_LR.size(); i++)
{
for(int j = 0; j < row_LR[i].size(); j++)
{
cout << row_LR[i][j];
}
cout << "\n";
}
return answer;
}설명
- 이 문제 못풀었다.
- 실패한 접근 방법은, 현재 위치를 배열로 저장하고, 이동했던 경로를 저장하기위해 벡터라는 배열을 만들어 저장할려고 했는데, 생각보다 인덱스가 복잡하고 계산하기 까다로워서 포기했다.
4. 숫자의 표현
문제 설명
Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.
1 + 2 + 3 + 4 + 5 = 15
4 + 5 + 6 = 15
7 + 8 = 15
15 = 15
자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.
제한사항
- n은 10,000 이하의 자연수 입니다.
입출력 예
풀이
#include <string>
#include <vector>
using namespace std;
int solution(int n) {
int answer = 0;
int i = 0;
int j= 1;
int result = 0;
int flag = 0;
while(i <= n)
{
j = 1;
while(j + i <=n && result < n)
{
result += i+j;
j++;
}
if(result == n)
flag++;
result = 0;
i++;
}
return flag;
}설명
- 1부터 더해서 타겟 값이 나올떄마다 count해주면 되는거라 쉽게 문제를 해결햇다.
5. 이진 변환 반복하기
문제 설명
0과 1로 이루어진 어떤 문자열 x에 대한 이진 변환을 다음과 같이 정의합니다.
x의 모든 0을 제거합니다.
x의 길이를 c라고 하면, x를 "c를 2진법으로 표현한 문자열"로 바꿉니다.
예를 들어, x = "0111010"이라면, x에 이진 변환을 가하면 x = "0111010" -> "1111" -> "100" 이 됩니다.
0과 1로 이루어진 문자열 s가 매개변수로 주어집니다. s가 "1"이 될 때까지 계속해서 s에 이진 변환을 가했을 때, 이진 변환의 횟수와 변환 과정에서 제거된 모든 0의 개수를 각각 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- s의 길이는 1 이상 150,000 이하입니다.
- s에는 '1'이 최소 하나 이상 포함되어 있습니다.
입출력 예
풀이
#include <string>
#include <vector>
using namespace std;
vector<int> solution(string s) {
vector<int> answer;
answer.push_back(0);
answer.push_back(0);
int sum = 0;
while(s.size() > 1)
{
sum = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '1')
sum++;
}
answer[1] += s.size() - sum;
s = "";
while (sum != 0)
{
s += (sum % 2) + '0';
sum = sum / 2;
}
answer[0] += 1;
}
return answer;
}설명
- 1의 개수를 카운트해서 정수로 변환해주고, 변환한 값을 다시 2진수로 변환해주는 과정을 거쳤다.
- 코드를 다시 봤는데, 왜이렇게 어렵게 짯을까?
- s.size를 안쓰고 break를 할 방법은 없었을까 생각이 들었다.
~_~