문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/87390
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제
코드 및 풀이 (시간초과 해결)
개념
n^2 배열 자르기
1행 1열부터 i행 i열 까지 모든 숫자를 i로 채움
문제의 예시 처럼
n = 3이면
1 2 3
2 2 3
3 3 3 이 되는것을
1 2 3 2 2 3 3 3 3인 한 배열로 저장을 한다. 그리고 left의 인덱스 부터 right의 인덱스 까지 배열을 자른다.
2 5 -> 3 2 2 3 이 되는것이다.
생각을 해보면 left가 2일때 right가 5일때 이차원 배열에 대해서
i,j라고 하면 i* n + j값이 left부터 i * n + j의 값이 right까지로 생각을 하면 되지 않을까 싶다.
즉, left <= i * 3 + j && i*3 + j <= right 라는 경우를 생각을 하면 안에 들때에 대해서면 push_back을 하면 되지 않나 싶다.
우선 맞는 코드긴하지만 시간 초과한코드를 보면서 설명 진행하겠습니다.
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int n, long long left, long long right) {
vector<int> answer;
for(int i = 0; i < n; i ++){
for(int j = 0; j < n ; j++){
//left~right의 범위 안에 들을 때
if(left <= i * n + j && i * n + j <= right){
if(j > i){
//인덱스 + 1을 해야 1행일때 1 2행일때 2가 된다.
answer.push_back(j + 1);
}else{
//마찬가지
answer.push_back(i + 1);
}
}
if(i * n + j > right){
//right보다 크다는 것은 더이상 연산이 필요가 없음 그냥 return을 해버리면 됨
return answer;
}
}
}
return answer;
}
이렇게 열이 행보다 크다면 j+1 push_back을 하고
열이 크다면 i + 1을 push_back을 해줬습니다.
예시의 1번을 보시면
1 2 3
2 2 3
3 3 3 을 보시게 되면 따로 배열로 만들지 말고 이것에 대한 이해를 할 수 있습니다.
하지만?
뭐가 문제였을까?
이중 반목문을 도는데 j>i라면 j+1을 push_back 아니라면 i+1을 해주는것에 대해서는 문제가 없다.
하지만 left가 예시로 22222222이런 숫자가 들어왔을때 우리는
이중 반복문에 대해서 0~22222221까지의 불필요한!!! 반복문을 돌게 되어 시간을 낭비합니다.
이것을 해결한 코드입니다.
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int n, long long left, long long right) {
vector<int> answer;
//15~20 시간 초과로 인한 left에서 부터 연산을 시작하기 위해 설정
//해당하는 행에 대해서면 연산을 진행하는 것으로 설정
int left_i,left_j,right_i,right_j;
left_i = left / n;
right_i = right / n;
for(int i =left_i;i<=right_i;i++){
for(int j =0;j<n;j++){
//left~right의 범위 안에 들을 때
if(left <= i * n + j && i * n + j <= right){
if(j > i){
//인덱스 + 1을 해야 1행일때 1 2행일때 2가 된다.
answer.push_back(j + 1);
}else{
//마찬가지
answer.push_back(i + 1);
}
}
if(i * n + j > right){
//right보다 크다는 것은 더이상 연산이 필요가 없음 그냥 return을 해버리면 됨
return answer;
}
}
}
return answer;
}
left_i와 right_i를 계산 하였습니다.
예시를 들어드리자면 n = 5, left가 20 right가 22일때
1 2 3 4 5
2 2 3 4 5
3 3 3 4 5
4 4 4 4 5
5 5 5 5 5
구하게 된다면 위의 반복문을 통해 5 5 5 5 5가 포함된 5행에 대해서만 반복문이 돌게 되는 것입니다.
또한 right가 23이 되었을때 이것은 이제 반복문을 더 돌 필요가 없으니 return answer을 진행해주었습니다.
해결 완료!
댓글