오늘 할일
1. 창의엔트리 2일차
2. LeetCode
3. 대기업&중견기업 취업전략 과제
오늘 한일
1. LeetCode
- Asteroid Collision를 아직 해결중이다.
첫번째 시도로, 문제를 다시금 이해하기 위해 정리해보았다.
- Asteroid Collision를 아직 해결중이다.
/*
소행성들의 배열을 받는다. 절댓값은 크기를, 부호는 방향을 나타낸다.
모든 소행성들은 같은 속도로 움직인다. 모든 충돌이 발생한 후의 상태를 알아내어라.
충돌 시 작은 것이 파괴되며 같을 시 둘 다 파괴된다.
같은 방향으로 움직이는 두 소행성은 만나지 않는다.
*/testcase {-2, -2, 2, -1}에서 {-2, -2, 2}가 반환돼야하는 것을 이해하였다. 처음에 이해했을 때에는 -2, 2에서 둘 다 파괴돼서 {-2, -1}이 되어야한다고 생각했는데 -는 좌측으로 움직이고 +는 우측으로 움직여 2와 -1이 만나 -1이 사라지고 {-2, -2, 2}가 된다. 즉 부호의 방향성을 처리하지 않았던 것을 알아차렸다.
부호의 방향성을 어떻게 확인할 수 있을까? 지금까지는 충돌의 조건으로 부호의 전환을 사용해왔다. 다만 이때 부호의 전환이 음수->양수로 되는 경우 음수는 좌측으로 양수는 우측으로 이동하기에 충돌하지 않는 다는 미처리 상황이 존재했다. 그럼 기존의 코드에서 부호의 전환이 발생했을 때 음수->양수인 경우 별도의 처리를 진행하지 않게 조건문을 수정해보아야겠다.
class Solution {
public int[] asteroidCollision(int[] asteroids) {
int size= asteroids.length;
//1. 스택
Stack<Integer> stack=new Stack<>();
//1-2. 예외처리, 이미 완료된 경우 testcase 153
int count=0;
for(int i=0; i<size-1; i++){
int cur=asteroids[i];
int next=asteroids[i+1];
if(cur*next<0){
count++;
}
}
if(count==1&& asteroids[0]<0)
return asteroids;
//2. 로직 시작
for(int i=0; i<size; i++) {
//2-1. 해당하는 값 읽기
int current_num = asteroids[i];
//2-2. 스택이 비어있다면 별도의 확인 없이 푸시
if (stack.isEmpty()) {
stack.push(current_num);
continue;
}
//2-3. 스택의 값 부호와 현재의 값 부호가 같다면 푸시
if (current_num * stack.peek() > 0) {
stack.push(current_num);
continue;
} else {//만약 부호가 다르다면
//TDD 172_부호 방향성 고려
if(current_num>0){
stack.push(current_num);
continue;
}
int pop_num = stack.pop();
int abs_current_num = Math.abs(current_num);
int abs_pop_num = Math.abs(pop_num);
//TDD 184
if(i<size-1){
int next_num=asteroids[i+1];
if(Math.abs(next_num)==Math.abs(current_num)
&& next_num*current_num<0){
i+=2;
stack.push(pop_num);
continue;
}
}
//2-4. 기존의 값이 더 크다면 무시하고 다시 원래의 값 스택에 복구(푸시)
if (abs_pop_num > abs_current_num) {
stack.push(pop_num);
continue;
} else if (abs_pop_num < abs_current_num) {//2-5. 기존의 값이 더 작다면 이길 때 까지 pop
for (; Math.abs(pop_num) < abs_current_num && !stack.isEmpty(); pop_num = stack.pop()) {
}
//2-6. 결국 졌다면 current_num을 푸시
if (Math.abs(pop_num)<abs_current_num) {
stack.push(current_num);
continue;
} else{//2-7. 결국 이겼다면 다시 원래의 값 스택에 복구(푸시)
stack.push(pop_num);
}
} else {//2-8. 두 수의 크기가 같다면 둘 다 삭제(pop값을 다시 넣지 않음)
continue;
}
}
}
//3. 반환 타입으로 변환
int stack_size=stack.size();
int[] result=new int[stack_size];
for(int i=0; i<stack_size; i++){
result[stack_size-i-1]=stack.pop();
}
return result;
}
} 
220번 테스트케이스까지 통과하였다. {-2, -2, 1, -2}는 1, -2에서 절댓값이 큰 -2가 승리하여 {-2, -2, -2}가 되는 것이 내 이해에도 맞다. 디버깅을 통해 문제 발생 원인을 찾아보자.
for(; Math..abs(pop_num)<abs_current_num && !stack.isEmpty(); pop_num=stack.pop(){}에서 문제가 발생했는데, {-2, -2, 1}까지 잘 stack에 push되다가 -2를 만나 {-2, -2}가 되고 1과 -2를 다루는 과정에서 스택에 있는 -2가 pop되고 1과 -2에서 승리한 -2가 push되어 {-2, -2}가 되었던 것이다. 즉 위의 명령어에서 불필요한 pop작업이 1회 일어나고 있었다. 이 문제를 해결하기 위하여 위 반복문 이전에 예외처리 코드를 추가하였다.
if(Math.abs(pop_num)<abs_current_num && current_num<0){
stack.push(current_num);
continue;
}223번 테스트 케이스까지 통과하였다. 하지만 해당 케이스를 예외처리하니 앞의 테스트케이스에서 문제가 발생하기 시작했고, 보다 근본적인 해결책이 필요하다고 생각하여 처음부터 다시 접근해보기로 결정하였다.
알고리즘을 생각해보자.
Q1. Stack이 필요한가?
A1. 처음에 LinkedList로 원소의 삭제 & 추가로만 접근해보았지만 여러 원소의 인덱스를 접근해야하기에 코드가 복잡해진다. Stack을 사용하면 피연산자 하나마다 연산을 처리할 수 있어 보다 간단해진다(pop한 값과 현재 값의 연산)
Q2. 부호의 방향성은 어떻게 처리할 것인가?
A2. 현재 음수는 좌측값과, 양수는 우측값과 연산하기에 부호에 따라 계산해야하는 값이 달라지게 된다. 좌측으로 가다가 우측값을 만날 경우, 우측으로 가다가 좌측값을 만나는 경우를 따로 처리해야할 듯 하다.
그렇다면, 처음에는 순회를 이용하여 부호가 바뀌는 부분의 index들을 얻어내고, 그 사이의 구간들에 한하여 정보를 처리하는 방법은 어떨까? 이 경우 부분 계산에 있어서는 용이할 수 있어보이지만 결과적으로 다른 구간들을 똑같이 고려해야한다는 단점이 존재한다.
좌측방향의 연산과 우측방향의 연산을 따로따로 stack을 두어 분리하여 처리하면 어떨까? 우선 우측 방향으로 진행되는 계산을 먼저 처리해보자. 좌측값의 절댓값이 큰 경우 오른쪽으로 순회하며 우측값의 절댓값이 더 커지거나 같은 부호가 나올 때 까지 계산을 진행하게 된다. 반대로 좌측 방향으로 진행되는 연산은 우측의 절댓값이 큰 경우 좌측으로 순회하며 좌측값의 절댓값이 더 커지거나 같은 부호가 나올 때 까지 계산을 진행하게 된다. 문제는 이 때 같은 부호가 등장해서 멈추면 정말 순조로운데, 다른 부호의 절댓값이 더 큰 수가 나오면 또 방향을 역행해야하는 단점이 존재한다.
현재의 문제를 작은 케이스들로 문제를 분리하여 접근해보면 어떨까? 현재 문제는 두 수의 절댓값과 방향으로 인해 복잡하게 느껴진다. 방향은 절댓값으로 결정되기에 우선 부호가 바뀌는 경우 앞의 수의 절댓값이 큰지 뒤에 수의 절댓값이 큰지를 나누어 생각해보자. 앞의 수의 절댓값이 큰 경우 같은 부호의 숫자나 뒤의 수의 절댓값이 커질 때 까지 뒤의 수를 제거하게 된다. 뒤의 수의 절댓값이 큰 경우 마찬가지로 같은 부호의 숫자나 앞의 수의 절댓값이 더 커질 때 까지 앞의 수를 제거하게 된다. 문제는 결국 역행해야하는 문제가 생긴다는 것이다.
그럼 역행해야 하는 문제를 어떻게 해결할 수 있을까? stack과 array를 사용하는 현재의 코드에서 좌측이동은 stack.pop으로, 우측 이동은 array++로 쉽게 가능하긴하다. 역행까지 코드로 구현하면 될까? 아니면 이를 혹시 재귀적으로 해결할 수는 없을까?
우선 역행을 코드로 구현하는 것을 생각해보자. 원소를 부호에 따라 좌측으로 움직이기도, 우측으로 움직이기도 하는데 종료조건은 무엇일까? 같은 부호를 만날 때 까지 반복을 하게 될 것이다. 이때 잠시만. 좌측으로 움직이기도, 우측으로 움직이기도 하는 상황이 정말로 발생하는가? 좌측에 음수만 있고 우측에 양수만 있는 경우 아무것도 하지 않아도 된다.
전체 알고리즘의 종료조건인 추가충돌이 없는 경우를 정의할 수 있을 듯 하다. 음수는 좌측에, 양수는 우측에 남아있는 경우이다. 그렇다면, 음수는 조금씩 좌측으로, 양수는 조금씩 우측으로 옮기는 과정에서 swap조건으로 충돌을 고려하면 어떨까?
class Solution {
List<Integer> list=new LinkedList();
private void swap(int index1, int index2){//양->음
assert(index1<index2);
int num1=list.get(index1), num2=list.get(index2);
assert(num1>0);
int abs_num1=Math.abs(num1), abs_num2=Math.abs(num2);
//양->음
try {
list.get(index2);
} catch(IndexOutOfBoundsException e){
System.out.println("IOB Exception catching");
}
if (abs_num1 < abs_num2) {
list.remove(index1);
} else if (abs_num1 > abs_num2) {
list.remove(index2);
} else {
list.remove(index1);
list.remove(index1);//index2이나, 위의 remove로 index2가 index1위치가 됨
}
}
public int[] asteroidCollision(int[] asteroids) {
int size= asteroids.length;
for(int i=0; i<size; i++)
list.add(asteroids[i]);
for(int loop=0; loop<asteroids.length; loop++) {
for (int i = 0; i < list.size() - 1; i++) {
//양->음만 찾자
int num1 = list.get(i), num2 = list.get(i + 1);
if (num1 > 0 && num2 < 0)
swap(i, i + 1);
}
}
int result_size=list.size();
int[] result=new int[result_size];
for(int i=0; i<result_size; i++)
result[i]=list.get(i);
return result;
}
}
문제에서 얻을 수 있는 교훈?은 문제의 카테고리가 stack에 들어가있다고 반드시 stack을 사용하는 게 정답은 아닐 수 있다는 것이다. 아마 훨씬 빠른 시간에 풀어낸 코드들은 stack을 사용하지 않았을까 싶긴하다. 문제를 해결할 때 복잡한 문제인 경우 최종적으로 작업이 종료되는 조건, 반복 혹은 조건문의 종료 조건을 명확히만 해도 훨씬 코드 가독성이 좋아지는 것 같고, 문제를 해결하는데에 유사 swap관점으로 접근하여 함수를 별도로 분리한 것도 문제 해결에 큰 도움이 됐던 것 같다. 문제가 복잡하면 복잡할 수록 부분 기능을 함수화하여 사용하는 것이 좋아보인다.
