오늘 할일
1. 창의엔트리조교 1일차
2. LeetCode
3. 대기업&중경기업 취업 준비전략 과제완성
오늘 한일
1. LeetCode
- Asteroid Collision는 숫자배열에서 부호와 크기를 고려하여 충돌시킨 결과를 구하는 문제이다.
문제를 이해하는데에 어려움이 있었고, 이해한 문제를 구현하는 데에 문제가 있다. 우선 문제를 살펴보자.
앞에와 다른 부호의 수가 나오면 앞의 원소와 비교하여 절댓값이 작은 쪽을 지운다. 이 때 새로 나온 부호가 다른 숫자가 지워졌다면 계속 탐색을 이어나가지만, 앞의 숫자가 지워졌다면 다른 숫자와의 비교를 새로 나온 부호가 다른 숫자가 지워질 때 까지 반복한다. 만약 마지막까지도 이어졌다면 음수 수 하나가 남게된다. 처음 절댓값 비교 시 절댓값이 서로 같다면 둘 다 지우고 탐색을 이어나간다.
첫번째 접근으로, 생각보다 복잡하여 TDD방식으로 접근해보겠다
public int[] asteroidCollision(int[] asteroids) {
int size= asteroids.length;
Stack<Integer> stack=new Stack();
for(int i=0; i<size; i++){
int num=asteroids[i];
if(num>=0){
stack.push(num);
} else {
int sum=0;
int pop_num=stack.pop();
if(pop_num*-1==num){
} else{
//num음수, pop_num양수
if(-1*num>pop_num)
sum=num;
else
sum=pop_num;
stack.push(sum);
}
}
}
int[] result=new int[stack.size()];
for(int i=stack.size()-1; i>=0; i--){
result[i]=stack.pop();
}
return result;
}
현재 테스트 케이스 3번에서 막혔는데, 방법은 대략 가늠이 가나 어떻게 구현을 해야할지 코딩 부분에서 부족함을 느끼고 있다.
무작정 for나 do while, if문으로 상황을 분류하기보다 조금 시간을 두고 효율적인 처리방법을 고민해봐야겠다.
두번째 접근으로, 문제를 보다 쉽게 접근해보고자 LinkedList를 사용해보았다.
public int[] asteroidCollision(int[] asteroids) {
int size= asteroids.length;
//1. 연결리스트화
List<Integer> list=new LinkedList<>();
for(int i=0; i<size; i++)
list.add(asteroids[i]);
//2. 로직
for(int i=0; i<list.size()-1; i++){
int elem1=list.get(i);
int elem2=list.get(i+1);
if(elem2<0){//둘이 부호가 다르다면
if(Math.abs(elem1)<Math.abs(elem2)){//뒤의 절댓값이 우세하다면
while(Math.abs(elem1)<Math.abs(elem2)){//앞이 우세할 때 까지
list.remove(i);
}
}
}
}
return;
}하지만 음수가 상쇄될 때 까지 반복하여 돌리는 부분에서, list의 원소를 지울 인덱스값의 갱신을 위해 추가적인 변수가 사용됨을 알 수 있었다. 이를 Stack으로 접근하면 해결이 될 듯 하다. 이 참에 Stack을 정복해보기로 하자.
세번째 접근으로, Stack을 사용하기로 결정했다. 두개의 피연산자처리는 Stack으로 가능할 듯 하다.
public int[] asteroidCollision(int[] asteroids) {
int size= asteroids.length;
//1. 스택
Stack<Integer> stack=new Stack<>();
//2. 로직 시작
for(int i=0; i<size; i++){
int current_num=asteroids[i];
if(current_num>0){
stack.push(current_num);
} else{//3. 음수 발견 시 충돌발생
//반복문을 사용하기 이전, 종료조건 설정_양수의 절댓값이 더 큰 경우.
//같은 경우 둘 다 사라지며, 음수의 절댓값이 더 큰 경우 스택에서 원소를 추가적으로 꺼낸다.
int abs_current_num=current_num*-1;//4. 만난 음수의 절댓값
for(int poped_num=stack.pop(); poped_num>abs_current_num; poped_num=stack.pop()){
if(poped_num==abs_current_num){
break;
} else if(poped_num<abs_current_num){
} else{
stack.push(poped_num);
break;
}
}
}
}
//5. 반환 타입으로 변환
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;
}
세번째 테스트 케이스를 통과했다! 4번째에서 문제가 발생한 이유는 초기 시작 부호를 -만 나온 경우를 고려하지 않았기 때문이다. 조금 더 범용적으로 바꾸어보자.
class Solution {
public int[] asteroidCollision(int[] asteroids) {
int size= asteroids.length;
//1. 스택
Stack<Integer> stack=new Stack<>();
//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 {//만약 부호가 다르다면
int pop_num = stack.pop();
int abs_current_num = Math.abs(current_num);
int abs_pop_num = Math.abs(pop_num);
//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;
}
}
그 결과 135번 테스트 케이스까지 통과하였다. 다만 문제는 테스트케이스 4번에 대하여 왜 빈 배열이 나와야하는지 잘 이해가 되지 않는다. 아직 문제이해를 잘 못한 듯 한데, {-2, -1, 1, 2}에서 기존의 생각은 -는 좌측방향, +는 우측방향이라 음수가 좌측에 양수가 우측에 몰려있기에 충돌하지 않는다! 였는데 내 알고리즘으로 나온 빈 배열이 통과한 것으로 보아 좌우방향구분 없이 절댓값으로만 판별하는 듯 하다. 그렇기에 {-2, -1, 1, 2}->{-2, 2}->{}가 되어 빈 배열이 도출되는 것이다.
그런데 엄청난 반전이 존재한다. 135번 테스트 케이스 역시 {-2, -1, 1, 2}인데, 이번에는 빈 배열이 아닌 {-2, -1, 1, 2}가 나와야 한다는 것이다. 문제의 오류를 발견하였다! 테스트 케이스 4번과 테스트 케이스 135번의 입력이 같은데 출력이 다르다. 고로 discussion을 참고하니 빈 배열이 나와야 하는 듯 하다?! 아마 위에 testcase4번은 LeetCode에서 잘못눌러 추가된 입력..?인듯하다. 그래서 TDD 느낌으로 좌측에 음수가 모여있고, 우측의 양수가 모여있는 경우 기존의 함수입력값을 그대로 리턴하게끔 전환 횟수를 카운트 하는 변수 diversion_count를 추가하였다.
class Solution {
public int[] asteroidCollision(int[] asteroids) {
int size= asteroids.length;
int diversion_count=0;
//1. 스택
Stack<Integer> stack=new Stack<>();
//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 {//만약 부호가 다르다면
diversion_count++;
int pop_num = stack.pop();
int abs_current_num = Math.abs(current_num);
int abs_pop_num = Math.abs(pop_num);
//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();
}
if(diversion_count==1 && asteroids[0]<0)
return asteroids;
return result;
}
}
그런데 이번에도 같은 입력 {-2, -1, 1, 2}인데 테스트케이스 153번까지 통과하였다. 우선 확인해보니, diversion_count 값이 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 {//만약 부호가 다르다면
int pop_num = stack.pop();
int abs_current_num = Math.abs(current_num);
int abs_pop_num = Math.abs(pop_num);
//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;
}
}
184번 케이스까지 통과하였다. 현재 알고리즘은 첫번째부터 마지막 인덱스까지의 순서로만 보아, current_num다음에 부호만 다른 같은 절댓값의 수가 있다면 둘 다 삭제해야하는 부분을 처리하지 못한다. 이를 더블체크로 확인해주자.
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 {//만약 부호가 다르다면
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;
}
}
문제를 잘못 이해한 듯 하다. 184위의 코드에서 {-2, -2, 1, -1}이 {-2, -2, -1}이 아닌 {-2, -2}가 되어야 한다는 점에서, 뒤에 절댓값이 같지만 부호가 다른 경우 우선순위가 그 뒤에 있다는 줄 았았는데, 현재 Testcase 172에서는 {-2, -2, 2, -1}가 {-2, -1}이 아닌 {-2, -2, 2}가 된다는 것을 알 수 있다. 우선을 여기까지 하고 내일을 도모해봐야겠다.
