문제
정수 배열 arr와 2차원 정수 배열 queries이 주어집니다. queries의 원소는 각각 하나의 query를 나타내며, [s, e, k] 꼴입니다.
각 query마다 순서대로 s ≤ i ≤ e인 모든 i에 대해 k보다 크면서 가장 작은 arr[i]를 찾습니다.
각 쿼리의 순서에 맞게 답을 저장한 배열을 반환하는 solution 함수를 완성해 주세요.
단, 특정 쿼리의 답이 존재하지 않으면 -1을 저장합니다.
제한사항
1 ≤ arr의 길이 ≤ 1,000
0 ≤ arr의 원소 ≤ 1,000,000
1 ≤ queries의 길이 ≤ 1,000
0 ≤ s ≤ e < arr의 길이
0 ≤ k ≤ 1,000,000
입출력 예
arr queries result
[0, 1, 2, 4, 3] [[0, 4, 2],[0, 3, 2],[0, 2, 2]] [3, 4, -1]입출력 예 설명
입출력 예 #1
첫 번째 쿼리의 범위에는 0, 1, 2, 4, 3이 있으며 이 중 2보다 크면서 가장 작은 값은 3입니다.
두 번째 쿼리의 범위에는 0, 1, 2, 4가 있으며 이 중 2보다 크면서 가장 작은 값은 4입니다.
세 번째 쿼리의 범위에는 0, 1, 2가 있으며 여기에는 2보다 큰 값이 없습니다.
따라서 [3, 4, -1]을 return 합니다.
풀이
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#define INF 0x7fffffff
int* solution(int arr[], size_t arr_len, int** queries, size_t queries_rows, size_t queries_cols) {
int* answer = (int*)malloc(queries_rows * sizeof(int));
for(int i = 0; i < queries_rows; i++) {
int s = queries[i][0], e = queries[i][1], k = queries[i][2];
int min = INF;
for(;s <= e; s++) {
if(arr[s] <= k) continue;
if(arr[s] < min) min = arr[s];
}
if(min == INF) min = -1;
answer[i] = min;
}
return answer;
}코드 설명
처음에 min을 int 형에서 가장 큰 값인 0x7fffffff 으로 넣어준 후, 조건에 부합하면 min을 교체한다. 모든 실행이 끝난후에도 min 이 여전히 0x7fffffff 이면 해당값이 바뀌지 않았다는 것이므로 -1을 대입한다.
for 루프 간략하게 작성하는 방법
for(;s <= e; s++) {}위와 같이 변수가 이미 선언되어 있는 경우, 첫번째 조건을 생략할 수 있다.
if 문 보기 좋게 작성하는 방법
if(arr[s] <= k && arr[s] < min)
min = arr[s];조건 두 개가 &&로 연결되어 있어서 문장이 길어지고 가독성이 좋지 않다. 이럴 때에는 continue를 사용하여 조건 두개를 만족해야만 코드가 실행될 수 있음을 나타낼 수 있다.
if(arr[s] <= k) continue;
if(arr[s] < min) min = arr[s];int형 표현 가능 범위
-
0x7fffffff는 16진수(hexadecimal) 리터럴 표현식입니다. '0x' 접두사는 해당 값을 16진수로 표현하겠다는 것을 나타내며, 7fffffff는 16진수로 된 8자리 숫자입니다.
-
16진수에서는 0부터 9까지의 숫자와 A부터 F까지의 알파벳을 사용하여 0부터 15까지의 값을 표현합니다. A는 10을, B는 11을, C는 12를, ..., F는 15를 나타냅니다.
-
0x7fffffff는 이를 10진수로 변환하면 2,147,483,647이 되며, 이는 int형 변수에서 가장 큰 양수 값입니다. 이 값은 10진수로 2,147,483,647이며, 이는 부호 있는 32비트 정수형(int)에서 표현 가능한 가장 큰 값입니다.
-
int 형 변수에서 가장 큰 양수값이 왜 ffffffff 가 아닐까?
0xffffffff는 부호 없는 32비트 정수형(unsigned int)에서 가장 큰 값이다.
나의 풀이
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
int *solution(int arr[], size_t arr_len, int **queries, size_t queries_rows,
size_t queries_cols) {
int *answer = (int *)malloc(sizeof(int) * (queries_rows + 1));
for (int i = 0; i < queries_rows; i++) {
int s = queries[i][0];
int e = queries[i][1];
int k = queries[i][2];
int min = 1000001;
for (int j = s; j <= e; j++) {
if( arr[j]> k && arr[j] < min){
min = arr[j];
}
}
if(min == 1000001)
answer[i] = - 1;
else answer[i] = min;
}
answer[queries_rows] = '\0';
return answer;
}문제 출처
