삼각 달팽이
문제 링크 : 삼각 달팽이
문제 설명
정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.
제한 사항
- n은 1 이상 1,000 이하입니다.
입출력 예
| n | result |
|---|---|
| 4 | [1,2,9,3,10,8,4,5,6,7] |
| 5 | [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] |
| 6 | [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] |
풀이 방법
- 먼저 삼각형으로 되어있는 달팽이를 이차원 배열로 구현한 후, 이차원 배열로 구현된 값을 일차원 배열로 변환하면 될 것으로 보인다. (시뮬레이션 문제)
- 문제 예시를 보니, 특정 방향을 기준으로 빙글빙글 돌면서 값을 넣는데, n개부터 n-1, n-2, ... , 1개가 될 때까지 이차원 배열에 넣으면 될 것으로 보인다. 방향은 (1,0),(0,1),(-1,-1) 순서대로 1개만 넣게 될 때까지 계속하면 될 것으로 보인다.
-> 예상 시간복잡도는 삼각형에 들어가는 총 원소의 개수로O(N*(N+1)/2)으로 제한 사항에도 적합한 알고리즘으로 보인다.
구현
#include <string>
#include <vector>
using namespace std;
vector<int> solution(int n) {
vector<vector<int>> arr(n, vector<int>(n, 0));
int dir[3][2] = {{1, 0}, {0, 1}, {-1, -1}};
int val = 1; int row = -1; int col = 0;
int dirIndex = 0;
// 삼각 달팽이 이차원 배열로 그리기
for(int i = n; i > 0; i--){
for(int j = 0; j < i; j++){
row += dir[dirIndex][0];
col += dir[dirIndex][1];
arr[row][col] = val++;
}
dirIndex = (dirIndex + 1) % 3;
}
// 이차원 배열로 그린 것을 일차원 배열로 변환
vector<int> answer(val - 1, 0);
int index = 0;
for(int i = 0; i < n; i++){
for(int j = 0; j <= i; j++){
answer[index++] = arr[i][j];
}
}
return answer;
}연속된 부분 수열의 합
문제 링크 : 연속된 부분 수열의 합
문제 설명
비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
- 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
- 부분 수열의 합은 k입니다.
- 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
- 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.
제한 사항
- 5 ≤ sequence의 길이 ≤ 1,000,000
-> 1 ≤ sequence의 원소 ≤ 1,000
-> sequence는 비내림차순으로 정렬되어 있습니다. - 5 ≤ k ≤ 1,000,000,000
-> k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.
입출력 예
| sequence | k | result |
|---|---|---|
| [1, 2, 3, 4, 5] | 7 | [2, 3] |
| [1, 1, 1, 2, 3, 4, 5] | 5 | [6, 6] |
| [2, 2, 2, 2, 2] | 6 | [0, 2] |
풀이 방법
- 처음에는 각 원소를 처음으로 하는 모든 부분 수열을 검사하고자 했으나, 최악의 경우
O(N^2)으로 시간초과가 발생할 것 같아서,O(N)의 시간복잡도를 가진 방법을 구색해보았다. - sequence가 오름차순으로 정렬되어 있는데, 이를 이용해 하나씩 더해가면서 k를 넘어갈 시에는 앞에서부터 다시 빼는 방법을 통해 구현하고자 했다. 자료구조 큐와 유사하나 굳이 큐를 사용할 필요 없이 인덱스 값을 통해서 구현하면 될 것 같다.
-> 합이 k보다 작은 경우 : 저장해놓은 인덱스 값을 넣기
-> 합이 k와 같은 경우 : 인덱스 차이를 통해서 비교한 후에, 더 작을 시에는 수정
-> 합이 k보다 큰 경우 : 앞에서부터 하나씩 빼기
구현
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> sequence, int k) {
int startIndex = 0;
int endIndex = sequence.size();
int start = 0; int end = 0;
int sum = 0;
while(end < sequence.size()){
if(sum < k){
sum += sequence[end++];
}else if(sum == k){
if(endIndex - startIndex > end - 1 - start){
startIndex = start;
endIndex = end - 1;
}
sum -= sequence[start++];
}else{
sum -= sequence[start++];
}
}
// end가 가장 끝 인덱스에 도달했을 경우, 마지막 검사
while(sum >= k){
if(sum == k){
if(endIndex - startIndex > end - 1 - start){
startIndex = start;
endIndex = end - 1;
}
}
sum -= sequence[start++];
}
return {startIndex, endIndex};
}
게임 개발자를 향해..