프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제!
n행 m열의 격자가 있습니다. 격자의 각 행은 0, 1, ..., n-1번의 번호, 그리고 각 열은 0, 1, ..., m-1번의 번호가 순서대로 매겨져 있습니다. 당신은 이 격자에 공을 하나 두고, 그 공에 다음과 같은 쿼리들을 날리고자 합니다.
- 열 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(0, dx))
- 열 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(1, dx))
- 행 번호가 감소하는 방향으로 dx칸 이동하는 쿼리 (query(2, dx))
- 행 번호가 증가하는 방향으로 dx칸 이동하는 쿼리 (query(3, dx))
단, 공은 격자 바깥으로 이동할 수 없으며, 목적지가 격자 바깥인 경우 공은 이동하다가 더 이상 이동할 수 없을 때 멈추게 됩니다. 예를 들어, 5행 × 4열 크기의 격자 내의 공이 3행 2열에 있을 때 query(3, 10) 쿼리를 받은 경우 공은 4행 2열에서 멈추게 됩니다. (격자의 크기가 5행 × 4열이므로, 0~4번 행과 0~3번 열로 격자가 구성되기 때문입니다.)
격자의 행의 개수 n, 열의 개수 m, 정수 x와 y, 그리고 쿼리들의 목록을 나타내는 2차원 정수 배열 queries가 매개변수로 주어집니다. n × m개의 가능한 시작점에 대해서 해당 시작점에 공을 두고 queries 내의 쿼리들을 순서대로 시뮬레이션했을 때, x행 y열에 도착하는 시작점의 개수를 return 하도록 solution 함수를 완성해주세요.
N*M의 보드위의 위치에서 queries 순서대로 이동했을때 목적지에 도착할수있는 모든 좌표의 수를 구하는 문제!
모든영역을 탐색하기에는....
- 1 ≤ n ≤ 109
- 1 ≤ m ≤ 109
이라서 불가능해 보입니다....
그래서 먼가 줄일수 있는 방법이 있지 않을까! 하다가
벽에 부딪히는 부분부터 경우의 수가 여러갈래로 나뉜다는것을 알게되었습니다!
>>벽에 안 부딪힌다면? 목적지부터 거꾸로 이동했을때 출발지는 무조건 하나!
이점을 이용해 부딪히는 부분, 테두리 부분을 탐색하고 + 목적지에서 거꾸로 탐색해 나오는 지점
이렇게 부딪히는 출발지 + 안부딪히는 출발지를 따로 구해보기로 했습니다.....
하지만..... 코드는 점점 길어지고 여러번 부딪히는 경우를 처리하지 못해서 실패...
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int> move(vector<int> queries,vector<int> my_point, int n, int m){
if(queries[0]==0){
my_point[1]-=queries[1];
}
else if(queries[0]==1){
my_point[1]+=queries[1];
}
else if(queries[0]==2){
my_point[0]-=queries[1];
}
else{
my_point[0]+=queries[1];
}
if(my_point[0]<0){
my_point[0]=0;
}
if(my_point[1]<0){
my_point[1]=0;
}
if(my_point[0]>=n){
my_point[0]=n-1;
}
if(my_point[1]>=m){
my_point[1]=m-1;
}
return my_point;
}
long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {
long long answer = 0;
// queries| 0 : 왼 | 1 : 오른 | 2 : 위 | 3 : 아래 |
vector<int>my_point={0,0};
int list[4]={0,0,0,0};
int point[4]={-1,-1,-1,-1};// 왼 오 위 아래
vector<vector<int>>point_4={{0,0}, {0,m-1}, {n-1,0}, {n-1,m-1}};
for(int i=queries.size()-1;i>=0;i--){//마지막 이동체크
if(point[queries[i][0]]==-1){
point[queries[i][0]]=i;
}
}
for(int i=0;i<4;i++){
my_point=point_4[i];
for(int j =point[0]+1;j<queries.size();j++){// 여기서 시작!
my_point=move(queries[j],my_point,n,m);
if(my_point[0]==0 or my_point[1]==0){
break;
}
}
cout<<i<<","<<my_point[0]<<","<<my_point[1]<<endl;
if(my_point[0]==x and my_point[1]==y){
answer+=1;
}
}
//테두리들
int memo=0;
//왼
if(point[0]!=-1){
for(int i =1;i<n-1;i++){// [i,0]
my_point[0]=i;
my_point[1]=0;
for(int j =point[0]+1;j<queries.size();j++){// 여기서 시작!
my_point=move(queries[j],my_point,n,m);
if(my_point[0]==0 or my_point[1]==0){
break;
}
}
if(my_point[0]==x and my_point[1]==y){
answer+=1;
list[0]+=1;
}
}
}
//오
if(point[1]!=-1){
for(int i =1;i<n-1;i++){// [i,m-1]
my_point[0]=i;
my_point[1]=m-1;
for(int j =point[1]+1;j<queries.size();j++){// 여기서 시작!
my_point=move(queries[j],my_point,n,m);
if(my_point[0]==0 or my_point[1]==0){
break;
}
}
if(my_point[0]==x and my_point[1]==y){
answer+=1;
list[1]+=1;
}
}
}
//위
if(point[2]!=-1){
for(int i =1;i<m-1;i++){// [0,i]
my_point[0]=0;
my_point[1]=i;
for(int j =point[2]+1;j<queries.size();j++){// 여기서 시작!
my_point=move(queries[j],my_point,n,m);
if(my_point[0]==0 or my_point[1]==0){
break;
}
}
if(my_point[0]==x and my_point[1]==y){
answer+=1;
list[2]+=1;
}
}
}
//아래
if(point[3]!=-1){
for(int i =1;i<m-1;i++){// [n-1,i]
my_point[0]=n-1;
my_point[1]=i;
for(int j =point[3]+1;j<queries.size();j++){// 여기서 시작!
my_point=move(queries[j],my_point,n,m);
if(my_point[0]==0 or my_point[1]==0){
break;
}
}
if(my_point[0]==x and my_point[1]==y){
answer+=1;
cout<<i<<endl;
list[3]+=1;
}
}
}
cout<<list[0]<<","<<list[1]<<","<<list[2]<<","<<list[3]<<endl;
return answer;
}
실패를 맛보고... 찾아보니
[월간 코드 챌린지 시즌3] 10월 문제 해설
코딩이 재미있는 사람들을 위한 챌린지! 프로그래머스에서 2021년 9월 9일, 10월 7일 두 번에 걸쳐 월간 코드 챌린지 시즌3가 진행되었습니다. 2021년 10월 7일 19시 30분부터 22시 30분까지 진행된 시즌
prgms.tistory.com
역시 거꾸로 탐색하는 문제였습니다..! 여기까지는 생각을 했었는데
끝까지 탐색하면 목적지 - 출발지 한쌍이 만들어 질것이라 생각했었는데....
출발지의 범위를 만들어버리네요;;
문제의 핵심은 모든칸에 공을 넣어두고 문제에서 주어진 순서로 진행하여 마지막에 목적지칸 안에 있는 공의 갯수가 정답!
이지만 이 방법또한 10의 9승 * 10의 9승 을 생각하면 해결할수 없기에
이방법을 거꾸로!
목적지에서 점차 늘려가며 실제로 공들을 움직이는것이 아닌 사각 범위의 위치만 체킹하도록 푸는 문제!
다시시작!
먼저 기본적인것들부터 선언해준뒤
long long answer = 0;
int size = queries.size();
long long row_start = x, row_end = x;
long long col_start = y, col_end = y;
각각의 이동 값에 따라
row_start, col_start, row_end, col_end 들을 이동시켜주는 부분!
for(int i=queries.size() - 1; i >= 0; i--) {
int dir = queries[i][0];
int dist = queries[i][1];
if(dir == 0) { // 출발지기준 오른쪽으로 범위이동
if(p2_s != 0){//최대위치까지 공이 퍼졌다고 생각!
p2_s = p2_s + dist;
}
p2_e = p2_e + dist;
if(p2_e > m - 1){
p2_e = m - 1;
}
}
else if(dir == 1){ // 출발지기준 왼쪽으로 범위이동
p2_s = p2_s - dist;
if(p2_s < 0){
p2_s = 0;
}
if(p2_e != m - 1){
p2_e = p2_e - dist;
}
}
else if(dir == 2) { // 출발지기준 아래로 범위이동
if(p1_s != 0){
p1_s = p1_s + dist;
}
p1_e = p1_e + dist;
if(p1_e > n - 1){//범위체크
p1_e = n - 1;
}
}
else if(dir == 3) { // 출발지기준 위로 범위 이동
p1_s = p1_s - dist;
if(p1_s < 0){//범위체크
p1_s = 0;
}
if(p1_e != n - 1){//범위체크
p1_e = p1_e - dist;
}
}
if(p1_s > n - 1 || p1_e < 0 || p2_s > m - 1 || p2_e < 0) {
return answer;
}
}
위 코드중 아래 부분이 제일 이해가 되지 않았습니다..
if(p2_s != 0){//최대위치까지 공이 퍼졌다고 생각!
p2_s = p2_s + dist;
}
....
if(p2_e != m - 1){
p2_e = p2_e - dist;
}하지만 그림을 그려보고나서야 이해할수있었습니다.
지금 구하는 값은 공이 어디까지 퍼질수있는지!
그렇다면 최대치까지 이동한 범위의 좌표는 이동시켜주지 않는것이 맞겠죠!
요약하면
1. 최대한 펼치기 위해 한계값에 범위가 도달하면 멈춰두고 이동시키지 않습니다.
2. 나머지, 한계에 도달하지 않은 값들은 계속해서 이동시켜주어 범위를 점차 늘려줍니다.
3. 최대 범위 사각형의 넓이가 출발지의 갯수 이 문제에서 원하는 답 입니다!
굉장히 어려운 문제네요.... 먼가 수학적? 창의성을 시험하는 문제...
끝!
ALL
#include <string>
#include <vector>
#include <iostream>
using namespace std;
long long solution(int n, int m, int x, int y, vector<vector<int>> queries) {
long long answer = 0;
int size = queries.size();
long long p1_s = x, p1_e = x;
long long p2_s = y, p2_e = y;
for(int i=queries.size() - 1; i >= 0; i--) {
int dir = queries[i][0];
int dist = queries[i][1];
if(dir == 0) { // 출발지기준 오른쪽으로 범위이동
if(p2_s != 0){//범위체크
p2_s = p2_s + dist;
}
p2_e = p2_e + dist;
if(p2_e > m - 1){
p2_e = m - 1;
}
}
else if(dir == 1){ // 출발지기준 왼쪽으로 범위이동
p2_s = p2_s - dist;
if(p2_s < 0){
p2_s = 0;
}
if(p2_e != m - 1){
p2_e = p2_e - dist;
}
}
else if(dir == 2) { // 출발지기준 아래로 범위이동
if(p1_s != 0){
p1_s = p1_s + dist;
}
p1_e = p1_e + dist;
if(p1_e > n - 1){//범위체크
p1_e = n - 1;
}
}
else if(dir == 3) { // 출발지기준 위로 범위 이동
p1_s = p1_s - dist;
if(p1_s < 0){//범위체크
p1_s = 0;
}
if(p1_e != n - 1){//범위체크
p1_e = p1_e - dist;
}
}
if(p1_s > n - 1 || p1_e < 0 || p2_s > m - 1 || p2_e < 0) {
return answer;
}
}
answer = (p1_e - p1_s + 1) * (p2_e - p2_s + 1);//전체 넓이
return answer;
}
틀린점이 있다면 댓 달아주세요!
'코딩테스트!(프로그래머스 & 백준) > 프로그래머스-C++' 카테고리의 다른 글
| 코딩테스트 -- 선입 선출 스케줄링 - (프로그래머스 / C++) (0) | 2022.08.22 |
|---|---|
| 코딩테스트 -- 스티커 모으기(2) - (프로그래머스 / C++) (0) | 2022.08.19 |
| 코딩테스트 -- 파괴되지 않은 건물 - (프로그래머스 / C++) / 누적합 (4) | 2022.08.17 |
| 코딩테스트 -- 야근 지수 - (프로그래머스 / C++) (0) | 2022.08.14 |
| 코딩테스트 -- 거스름돈 - (프로그래머스 / C++) (0) | 2022.08.12 |
댓글