[C++] 프로그래머스 :: n^2 배열 자르기

728x90

안녕하세요 뚜디 입니다:)

코딩테스트 연습 - n^2 배열 자르기 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - n^2 배열 자르기

< 프로그래머스 - n^2 배열 자르기 (LV2) >

---

1. 연습 문제

2. 문제 풀이 & 소스코드 & 결과

---

 

1. 연습 문제

※ 문제 설명

정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다.
1. n행 n열 크기의 비어있는 2차원 배열을 만듭니다.
2. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다.
   - 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다.
3. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다.
4. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다.
정수 n, left, right가 매개변수로 주어집니다. 주어진 과정대로 만들어진 1차원 배열을 return 하도록 solution 함수를 완성해주세요.

※ 제한 조건

1 ≤ n ≤ 10^7
0 ≤ left ≤ right < n^2
right - left < 10^5

※ 입출력 예

n	left	right	result
3	2	5	[3,2,2,3]
4	7	14	[4,3,3,3,4,4,4,4]

• 다음 애니메이션은 주어진 과정대로 1차원 배열을 만드는 과정을 나타낸 것입니다.

 

2. 문제 풀이 & 소스 코드 & 결과

※ 소스 코드#1 (생각없이 문제만 풀었을 경우 : 실패)

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    vector<int> temp;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i <= j) {
                temp.push_back(j + 1);
            } else {
                temp.push_back(i + 1);
            }
        }
    }

    for (int i = left; i < right + 1; i++) {
        answer.push_back(temp[i]);
    }

    return answer;
}

문제를 제대로 읽지않고 바로 풀었을때, 입력된 n만큼 2차원 배열(temp)을 만들어 추후 입력된 left부터 right까지 answer 에 대입하여 리턴하는 방식으로 소스코드를 구현하였더니 절반 이상 시간초과로 실패하였다. 

 

※ 소스 코드#2 (제한 조건을 다시 살피고 문제를 풀었을 경우 : 실패)

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    long long count = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (count >= right + 1) {
                return answer;
            } else if (left <= count) {
                if (i <= j) {
                    answer.push_back(j + 1);
                } else {
                    answer.push_back(i + 1);
                }
            }
            count++;
        }
    }

    return answer;
}

이때, 생각한 방법은 처음 푼 소스코드#1 에서 2차원 배열(temp) 를 통해 answer를 리턴을 해주었다면, 이 과정을 생략하고 반복문을 진행하는 동시에 left부터 right까지 값을 찾았다면 리턴해주는 방식으로 변경하였다.

그 결과, 아래와 같이 시간초과로 실패하는 case가 많이 줄어들었다.
문제를 풀어야 하는 방향은 맞았다는 소리임으로 소스코드#3을 통해 최종적으로 푼 소스코드를 같이 살펴보도록합니다.

 

※ 소스 코드#3 (오래 생각하고 풀었을 경우 : 성공)

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(int n, long long left, long long right) {
    vector<int> answer;
    int topvalue = 0;
    int bottomvalue = 0;


    for (long long i = left; i < right + 1; i++) {
        topvalue = i / n;
        bottomvalue = i % n;

        if (topvalue >= bottomvalue + 1) {
            bottomvalue += topvalue - bottomvalue;
        }

        answer.push_back(bottomvalue + 1);
    }

    return answer;
}

우리는 소스코드#1, 소스코드#2 를 통해 문제를 풀어야하는 방향은 확인하였습니다.
문제를 풀어야할 방향 : left부터 right까지 임의로 입력된 숫자를 보고 그에 해당하는 숫자를 바로 알수 있어야한다.

1. topvalue : 2차원 배열의 행 / bottomvalue : 2차원 배열의 열
2. left부터 right까지 반복문을 통해 진행한다.
3. 2차원 배열의 행의 값이 (2차원 배열의 열+1) 보다 크거나 같다면, bottomvalue += topvalue - bottomvalue를 통해 answer 벡터에 추가해준다.
4. 3번의 경우가 아닐경우 bottomvalue + 1(2차원 배열의 열(i%n)+1) 값을 추가해준다.
5. answer 벡터를 리턴한다.