프로그래머스
프로그래머스 n^2 배열 자르기
콩순이냉장고
2021. 11. 2. 00:35
문제 URL : https://programmers.co.kr/learn/courses/30/lessons/87390
코딩테스트 연습 - n^2 배열 자르기
정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부
programmers.co.kr
문제 접근법:
수학적으로 접근하면 바로 풀립니다.
그림을 그려보시면 아시겠지만
| 0,0 | 0,1 | 0,2 | 0,3 |
| 1,0 | 1,1 | 1,2 | 1,3 |
| 2,0 | 2,1 | 2,2 | 2,3 |
| 3,0 | 3,1 | 3,2 | 3,3 |
| 1 | 2 | 3 | 4 |
| 2 | 2 | 3 | 4 |
| 3 | 3 | 3 | 4 |
| 4 | 4 | 4 | 4 |
| 0 | 1 | 2 | 3 |
| 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 |
| 12 | 13 | 14 | 15 |
위테이블은 좌표를 나타냈고 아래쪽테이블은 숫자를 넣었는데
규칙을 보시면아시겠지만 x,y좌표중 큰것을 기준으로 +1값이 배열안에 들어간것을 알수있습니다.
배열 arr[x][y]=max(x,y)+1 이라는 거겠죠
그렇다면 자르는것 어떻게 자르냐?
몫과 나머지를 이용하면됩니다.
예를들어 7번째 자리는 어디인지 확인하실려면
번째 자리는 7/4 의 몫은 1이고 7%4의 나머지는 3이니 1,3이라는 정확한값을
한번에 구할수있습니다. 이런식으로 코드를 짜주면 쉽게 풀수있는 문제입니다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> solution(int n, long long left, long long right) {
vector<int> answer(right - left + 1);
int idx = 0;
for (ll i = left; i <= right; i++) {
ll r = i / n;
ll mod = i % n;
answer[idx++] = max(r, mod) + 1;
}
return answer;
}
|
cs |
궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.