⭐️ 나중에 잊을 때쯤 다시 풀어볼 문제 ⭐️
초기 접근 방법
❗️처음에 생각한 방향
스택을 사용하는 것이 가장 적합하다고 판단되어
stack array를 따로 만들고
해당 stack[sp]와 주어진 배열 asteroids[i]의 비교를 통해서 구현하려고 함
[ 처음 코드 ]
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
int top=-1;
int* stack = (int*)malloc(asteroidsSize*sizeof(int));
stack[++top] = asteroids[0];
for(int i=1; i<asteroidsSize; i++){
if(stack[top]*asteroids[i]<0){
if(abs(stack[top])<abs(asteroids[i])){
stack[top]=asteroids[i];
}
}
else{
stack[++top] = asteroids[i];
}
}
*returnSize = top + 1;
int* ret = (int*) malloc((*returnSize)*sizeof(int));
for(int i=0; i<returnSize-1; i++){
ret[i] = stack[i];
}
return ret;
}
🚫 어디가 문제였는 지 🚫
위 부분을 고민해서 새로운 코드 구현
[ 두 번째 코드 ]
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
int sp = -1;
int* stack = (int*)malloc(asteroidsSize*sizeof(int));
stack[++sp] = asteroids[0];
for(int i=1; i<asteroidsSize; i++){
stack[++sp] = asteroids[i];
while(stack[sp]*stack[sp-1]<0 && sp>0){
if(abs(stack[sp]) > abs(stack[sp-1])){
stack[sp-1] = stack[sp];
sp--;
}
else if(abs(stack[sp]) == abs(stack[sp-1])){
sp -= 2;
}
else{
sp--;
}
}
}
*returnSize = sp+1;
int* ret = (int*)malloc((*returnSize)*sizeof(int));
for(int i=0; i<(*returnSize); i++){
ret[i] = stack[i];
}
free(stack);
return ret;
}🚫 어디가 문제였는 지 🚫
힙 버퍼 오버플로우 발생
알고리즘 자체가 틀렸다고 생각하지 않았고
배열의 범위 밖으로 나가지 않게 충분히 조건을 잡았다고 생각
하나하나 디버깅해본 결과
while(stack[sp]*stack[sp-1]<0 && sp>0)
이 반복문의 조건 부분이 문제였던 것으로 파악
저 부분의 무엇이 문제였나?
sp>0 이라는 조건을 넣은 이유는, sp>=0 이 되면,
stack[sp-1] 부분에 오버플로우 문제가 발생하기 때문 ( 예: stack[-1] )
하지만 조건의 순서가
(1) stack[sp]*stack[sp-1]<0
(2) sp>0 였던 것이 문제..
sp>0 이 조건을 앞으로 빼야지 그 뒤의 계산으로 넘어가지지 않음
예를 들어, sp = 0 인 경우,
(1) stack[sp]*stack[sp-1]<0 && sp>0
이 경우, stack[0]*stack[-1] < 0 에 대한 계산을 먼저 하게 됨으로써 오버플로우 발생
(2) sp>0 && stack[sp]*stack[sp-1]<0
반대로 이경우, sp > 0에서 조건을 벗어나므로 그 뒤의 계산까지 하지 않고, 오버플로우 발생하지 않음
이 부분을 간과해 굉장히,, 고생한 문제ㅠ
[ 세 번째 코드 ]
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
int sp = -1;
int* stack = (int*)malloc(asteroidsSize*sizeof(int));
stack[++sp] = asteroids[0];
for(int i=1; i<asteroidsSize; i++){
stack[++sp] = asteroids[i];
while(sp>0 && stack[sp]*stack[sp-1]<0){
if(abs(stack[sp]) > abs(stack[sp-1])){
stack[sp-1] = stack[sp];
sp--;
}
else if(abs(stack[sp]) == abs(stack[sp-1])){
sp -= 2;
}
else sp--;
}
}
*returnSize = sp+1;
int* ret = (int*)malloc((*returnSize)*sizeof(int));
for(int i=0; i<(*returnSize); i++){
ret[i] = stack[i];
}
free(stack);
return ret;
}
따라서 위와 같이 수정했으나
Testcase asteroids = [-5, -2, 5, 6] 부분에서 오류 문제 발생
🚫 어디가 문제였는 지 🚫
위의 경우, -5와 -2는 왼쪽으로, 5와 6은 오른쪽으로 이동하기 때문에
가운데 -2와 5는 부호가 달라도 방향까지 다르기 때문에 충돌하지 않음
하지만 내 코드는 방향을 고려하지 않았기 때문에
무조건 부호가 다르면 충돌이라고 판단하도록 구현됨
따라서 방향까지 신경쓰기 위해 조건을 수정함
단 한 줄만 추가하면 됨!
최종 접근
✅ stack을 정석으로 구현하기 보다는 그 개념만 차용하려고 함
stack pointer (대게 top 변수 / 본인은 sp 변수로 사용)를 두고 사용
✅ 파악한 문제해결규칙은
1. stack에 하나씩 쌓고 쌓인 stack의 stack[sp]와 stack[sp-1]를 비교함
2. 모든 배열의 원소에 대해 조회해야하는데, 배열의 원소를 먼저 stack에 쌓고
stack[sp]와 stack[sp-1]가 충돌하지 않을 때까지 연산해야함
즉, for 문안에 while 문을 넣는 구조
✅ 만약, 오른쪽(즉 sp가 더 큰 쪽)이 양수라면, 왼쪽과 부호가 달라도 충돌할 일은 없음
이 부분을 조건으로 명시해주기
✅ stack의 sp를 옮기면서 연산을 수행하기 때문에 sp보다 큰 인덱스를 가진 부분도 여전히 남아있을 수 있음
따라서 깔끔한 배열을 만들기 위해 모든 연산이 끝난 후
return array를 sp+1 크기로 따로 할당하고
옮긴 뒤, free(stack)을 하는 방법을 선택
구현
Runtime : 8ms
Beats 96.73% of users with C
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
int sp = -1;
int* stack = (int*)malloc(asteroidsSize*sizeof(int));
stack[++sp] = asteroids[0];
for(int i=1; i<asteroidsSize; i++){
stack[++sp] = asteroids[i];
while(sp>0 && stack[sp]<0 && stack[sp]*stack[sp-1]<0){
if(abs(stack[sp]) > abs(stack[sp-1])){
stack[sp-1] = stack[sp];
sp--;
}
else if(abs(stack[sp]) == abs(stack[sp-1])){
sp -= 2;
}
else sp--;
}
}
*returnSize = sp+1;
int* ret = (int*)malloc((*returnSize)*sizeof(int));
for(int i=0; i<(*returnSize); i++){
ret[i] = stack[i];
}
free(stack);
return ret;
}런타임과 메모리 사용량 모두 나쁘지 않았음!
(사실 리트코드 가끔 이상하게 측정돼서 의미가 있나 싶지만,,)
더 좋은 코드를 구현할 수 없을까 고민하며
다른 사람들의 코드도 보며
정석 스택 구현 코드인 거 같아서 가져옴
int push(int a,int top,int * stack)
{
top++;
stack[top]=a;
return top;
}
int pop(int top)
{
top--;
return top;
}
int peek(int top,int *stack)
{
return stack[top];
}
int* asteroidCollision(int* asteroids, int asteroidsSize, int* returnSize){
int a;
int i=0;
int stack[10000];
int top=-1;
while(i<asteroidsSize)
{
printf("*");
a=asteroids[i];
if(top==-1)
{
top=push(a,top,stack);
i++;
}
else if((peek(top,stack)<0 && a<0 )||(peek(top,stack)>0 && a>0))
{
top=push(a,top,stack);
i++;
}
else if(peek(top,stack)<0 && a>0)
{
top=push(a,top,stack);
i++;
}
else
{
if(abs(peek(top,stack))>abs(a))
{
i++;
}
else if(abs(peek(top,stack))==abs(a))
{
top=pop(top);
i++;
}
else
{
top=pop(top);
}
}
}
int *ans=malloc((top+1)*sizeof(int));
for(int i=0;i<=top;i++)
{
ans[i]=stack[i];
}
*returnSize=top+1;
return ans;
}
Take aways
✅ 반복적으로 확인해야 하는 경우, 어쩔 수 없이 반복문이 중첩되는 경우 있음
✅ C언어 절댓값 abs / fabs 함수
- abs
<stdlib.h> 헤더 파일에 존재하고 int 타입에 대한 절대값을 반환
- fabs
<math.h> 헤더 파일에 존재하고 double 타입에 대한 절대값을 반환
✅ C언어는 라인 안에서도 순서대로 코드를 읽고 구현한다는 것을 잊지말자
만약에 무조건 먼저 봐야하는 조건이면 맨 앞에서 확인해주면 됨
예를 들어,
i < 0 && arr[i] >10 에서 i < 0 을 만족하지 않으면 애초에 뒤의 조건을 보지 않음
왜냐면 위에는 && 연산이기 때문에 하나만 만족하지 않아도 끝
✅ 두 수의 부호가 같은 지 판단하기 위한 가장 쉬운 방법 : 곱한 값이 양수인지 확인!
'Algorithm > LeetCode' 카테고리의 다른 글
| LeetCode 2390. Removing Stars From a String (0) | 2023.08.16 |
|---|---|
| LeetCode 1657. Determine if Two Strings Are Close (1) | 2023.08.16 |
| LeetCode 1207. Unique Number of Occurrences (1) | 2023.08.16 |
| LeetCode 2215. Find the Difference of Two Arrays (0) | 2023.08.16 |
| LeetCode 1679. Max Number of K-Sum Pairs (0) | 2023.08.15 |