문제 설명
배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다.
예를 들면,
arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return 하는 solution 함수를 완성해 주세요.
연속되는 같은숫자는 싫어!
제한사항
- 배열 arr의 크기 : 1,000,000 이하의 자연수
- 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수
처음에 떠오른 생각
처음엔 그냥 배열에서 중복되는 숫자를 다 지우는줄 알았는데 그게 아니고
'연속되는 중복되는 숫자를 지워라'
이 말인것 같다.
우선 --> 정렬 알고리즘처럼 2중 for문을 돌리면서 --> 현재 위치와 바로 다음위치와 숫자를 비교 --> 다음위치의 숫자가 중복되면 지우고 --> 그 다음 위치와 비교 --> 같으면 지우고 --> 다르면 다음 위치로 넘어간다.
TIME OVER CASE.....
대부분의 테이트케이스는 정답으로 나왔지만 한 케이스가 TIMEOVER로 나오는 바람에 실패한 케이스 입니다.......... 코드부터 보겠습니다......
class Solution{
public int[] solution (int[] arr){
int count=1; //answer배열의 크기를 결정할 카운트
for(int i=0; i<arr.length-1;){
for(int j=i+1; j<arr.length; j++){
if(arr[i]!=arr[j]){ //arr[i]와 arr[j]를 비교해서 같은 숫자가 아니면
i=j; //i를 j 인덱스로 바꾸고
count++; //count를 더해준다. (
break; //break로 j가 메인인 for문을 빠져나옴.
}
else if(j== (arr.length-1) && i== (arr.length-2)){ //for문에 증감식이 없기떄문에 마지막 직전 인덱스를
//체크하기 위함.
i++; //i가 마지막 직전 인덱스이고, 위에서 i=j를 해주지 못했을때
} //강제로 i를 늘려 i가 메인인 for문을 종료시킴
}
}
int[] answer=new int [count]; //count크기는 answer배열을 만들어줌
for(int i=0,index=0; index<count; index++){ //for문형식은 같고
answer[index]=arr[i]; //answer배열에 연속되고,중복되는 값은 빼고 처음 보는 숫자를 answer배열에 넣어줌
for(int j=i+1; j<arr.length; j++){
if(arr[i]!=arr[j]){
i=j;
break;
}
}
}
for(int i:answer){
System.out.print(i+" "); //결과값 확인
}
return answer;
}
}주석은 써놨습니다.... 화가 나네요 ㅎㅎㅎ 뭐 알고리즘은 이런 맛에 하지 않겠습니까...?
어떤 코드인지 간단하게 설명을 해드리면
이중 for문을 두번 썼습니다. 그래서 TIMEOVER가 되지 않았나 생각되는데,
- 이중 for문 첫 번째
answer배열의 크기를 결정하기 위한 for문입니다. ArrayList를 사용하지 않고 하려고 하다보니 배열의 크기를 먼저 정해줘야 한다고 생각했기 때문에 이렇게 구현해봤습니다. - 이중 for문 두 번째
첫 번째 for문과 비슷합니다. count로 배열의 크기를 정해줬기 때문에 answer[]배열에 arr[]를 알맞게 넣어줍니다.
또 다른 방법을 생각하지 않은 것은 아니다!!
자. 물론 다른 방법을 생각해보긴 했습니다...
그저 처음에 생각했던대로 구현을 해보고 싶어서 해보긴 했습니다만 어쨌든 실패한것은 실패한 것이기 때문에 다른 방법으로 구현해보겠습니다.
제가 생각한 다른 방법은 2중 for문을 두 번 쓰는 것이 아니라 하나의 이중 for문에 count와 answer[]배열에 입력을 같이 하는 것입니다.
하지만 TIMEOVER가 왜 떴는지 정확히 모르기 때문에....일단... 도전 해보겠습니다!!
해결!!!
코드 제출을 했을때 17번 테스트만 TIMEOVER로 나왔었다. 다른 사람도 17번만 틀린 사람이 있길래 봤더니 생각지 못한 테스트케이스였다. 원인은 그저 무한루프였다. 불행중 다행으로 갈아엎을 필요는 없었다.
테스트케이스는 바로 [1,0,0,0]이었는데 한 줄을 고치고 나니 바로 해결되지 아니한가 하하핫
for(int i=0; i<arr.length-1;){
for(int j=i+1; j<arr.length; j++){
if(arr[i]!=arr[j]){
i=j;
count++;
break;
}
else if(j== (arr.length-1)){ //--> @여기 고침@
i++;
}
}
}두 개의 2중 for문중 위에있는 for문이다. 이 else if문의 조건을 바꿨다.
else if(j== (arr.length-1) && i== (arr.length-2))
{
i++;
}for문에 증감문이 없어 조건을 정해주지 않으면 무한루프를 돌게된다. 내가만든 코드에 내가 걸려버렸다. 그래도 하나 해결해서 너~~~무 뿌듯하다!!
REVIEW
다른 연습문제에는 import문이 없었는데 이번엔 맨 윗줄에 import java.util.*;
가 적혀있었다. 아마 라이브러리를 사용해도 무관하다는 말이 아닌가 싶다. 다른 풀이들을 보니 List도 많이썼고 StringBuilder를 쓴 사람도 보였다. 하지만 이번 문제는 라이브러리 없이 해보기로 마음먹었기 때문에 안써봤다. 라이브러리를 안쓴 사람 중 나랑 비슷하게 구현한 사람이 있었는데 그 코드는 이중 for문을 쓰지않고 한 for문만으로 구현했다. 생각해보니 나도 쓸 필요가 없었던것 같다...
후기
어.쨌.든.
라이브러리 없이 문제를 풀어보니 머리는 깨질것 같지만 술먹고 다음날에 해장하는 것처럼 깔끔~하고 상쾌~하다!! 뿌듯함이 두 배 랄까? 하지만 라이브러리를 써도 무관하다면 쓰는게 정신건강에 좋지 않을까 싶다.... :)
GITHUB 주소 : 같은 숫자는 싫어_giturl
