세 번 시도한 풀이
급할수록 돌아가자..
같은 수는 모두 제거
급하게 푼다고 문제 이해를 잘못한 코드
심지어 순서도 그냥 작은 수부터 출력한다! 와!
import java.util.*;
public class Solution {
public Stack<Integer> solution(int []arr) {
int [] compare = new int[9]; // 비교를 위한 정수 세팅
Stack<Integer> stack = new Stack<>(); // 가변 크기의 컬렉션
for(int i=0; i<arr.length; i++){
compare[arr[i]]++;
}
for (int i = 0 ; i < compare.length ; i++){
if(compare[i] != 0){
stack.push(i);
}
}
return stack;
}
}Stack으로만 리턴할 수 있다면
import java.util.*;
public class Solution {
public Stack<Integer> solution(int []arr) {
Stack<Integer> stack = new Stack<>(); // 가변 크기의 컬렉션으로 값 담기
stack.push(arr[0]);
for(int i=0; i<arr.length; i++){
if(stack.elementAt(stack.size()-1) != arr[i]){
stack.push(arr[i]);
}
}
return stack;
}
}0.11ms ~ 0.23ms
효율성 테스트
테스트 1 〉 통과 (32.67ms, 115MB)
테스트 2 〉 통과 (30.46ms, 115MB)
테스트 3 〉 통과 (30.76ms, 109MB)
테스트 4 〉 통과 (32.23ms, 115MB)배열로 리턴해야 한다
import java.util.*;
public class Solution {
public int[] solution(int []arr) {
Stack<Integer> stack = new Stack<>(); // 가변 크기의 컬렉션으로 값 담기
stack.push(arr[0]); // 비교를 위해 배열의 첫번째 값 넣기
for(int i=0; i<arr.length; i++){ // 배열의 길이만큼 돌면서 비교
if(stack.elementAt(stack.size()-1) != arr[i]){ // 바로 앞에 있는 stack의 값과 일치하지 않을 때만
stack.push(arr[i]); // stack에 값 추가
}
}
int[] answer = new int[stack.size()]; // stack의 크기만한 int 배열 생성
for(int i=answer.length-1 ; i>=0 ; i--){ // stack은 LIFO (후입선출)이므로 배열 맨뒤부터 값 넣어줌
answer[i] = stack.pop();
}
return answer;
}
}0.11ms~0.28ms
효율성 테스트
테스트 1 〉 통과 (50.00ms, 120MB)
테스트 2 〉 통과 (47.65ms, 113MB)
테스트 3 〉 통과 (47.71ms, 111MB)
테스트 4 〉 통과 (48.90ms, 116MB)보완점
stack.elementAt(stack.size()-1)
stack 가장 마지막에 넣은 값을 지우지 않고 꺼내기 위했던 코드
1) peek() : Stack의 top에 있는 item을 삭제하지않고 해당 item을 반환
2) get(stack.size()-1) : 특정 index의 item을 반환
다른 사람의 풀이
스터디원 한 분의 풀이
배열의 크기를 지정하기 어려워 가변 크기의 콜렉션을 사용한 건데, 중복된 수가 몇 개인지 세서 배열 크기를 지정하셨다! 결론적으로 속도가 가장 빠르셨다.
public int[] solution(int[] arr) {
int equal = 0; // equal를 선언 초기화
for (int i = 0; i < arr.length - 1; i++) { //반복문으로 arr배열의 길이만큼 반복한다.
if (arr[i] == arr[i + 1]) { //arr배열 속 같이 다음 숫자와 같은지 비교하고 같다면
equal++; // equal을 한개 증가시킨다
}
}
// 같은 수는 제거할 계획이므로 결과에 해당하는 배열은 equal만치 그 크기가 작다.
int[] result = new int[arr.length - equal];
int index = 0; //index 하나 쓸거라서 생성 초기화하고
for (int i = 0; i < arr.length - 1; i++) { //for반복문을 arr배열의 크기만큼 돌리면서
if (arr[i] != arr[i + 1]) { // arr의 숫자가 연속하지 않을때
result[index++] = arr[i]; // 결과의 배열에 arr[i]를 추가하고 index를 하나 늘려준다
}
}
result[index] = arr[arr.length - 1]; //틀린 부분!
// 입력 배열의 마지막 숫자를 결과 배열에 추가하는 부분!
return result; //결과 배열을 반환
}0.01ms~ 0.04ms
효율성 테스트
테스트 1 〉 통과 (16.00ms, 106MB)
테스트 2 〉 통과 (16.09ms, 106MB)
테스트 3 〉 통과 (15.28ms, 106MB)
테스트 4 〉 통과 (15.54ms, 108MB)프로그래머스 풀이
public int[] solution(int []arr) {
ArrayList<Integer> tempList = new ArrayList<Integer>();
int preNum = 10;
// input이 0~9로 정해져있으니 아닌 값을 넣어두면 초기값 (index 0번째 값)은 무조건 세팅됨
for(int num : arr) {
if(preNum != num)
tempList.add(num);
preNum = num;
}
int[] answer = new int[tempList.size()];
for(int i=0; i<answer.length; i++) {
answer[i] = tempList.get(i).intValue();
}
return answer;
}0.02ms ~ 0.10ms
효율성 테스트
테스트 1 〉 통과 (23.37ms, 116MB)
테스트 2 〉 통과 (25.33ms, 115MB)
테스트 3 〉 통과 (23.82ms, 115MB)
테스트 4 〉 통과 (29.40ms, 116MB)직전에 사용한 숫자를 따로 저장하는 변수를 생성한다
현재 input (배열의 값) 과 직전 사용 숫자가 다를 때에만 add를 수행한다
생각해볼만한 것
Stack? List? Array?
위 세 개의 풀이를 보면 (다른 로직은 좀 다르지만...)
효율성이 Array > List > Stack인 것을 알 수 있다
Collection의 경우 동적으로 메모리 크기를 동적으로 할당하기 때문에 메모리 효율성은 더 좋지만, 할당하는 데에 시간이 걸려서 효율성은 더 떨어지는 것으로 추정된다
위 팀원님의 풀이처럼 배열의 크기를 구할 수 있는 로직이 있다면, 배열을 사용하는 것이 더 나아 보인다.
그렇다면 List > Stack의 차이는?
Stack의 pop() 수행 시 메모리를 삭제하는 로직이 추가되기 때문에 시간이 더 걸리는 게 아닐까? (추측)
stack은 임시 데이터를 저장하는 데에 주로 사용된다.
(웹 페이지 뒤로 가기, 앞으로 가기 등...)
웬만하면 List를 사용하는 게 효율성은 낫다.
chatGPT에게 물어본 답변도 보자
- List:
List는 순서가 있는 요소들의 집합으로, 동적으로 크기가 조절될 수 있습니다. Java에서는 ArrayList와 LinkedList가 List 인터페이스를 구현하는 대표적인 클래스입니다. List는 일반적으로 요소의 추가, 삭제, 탐색에 효율적이며, 인덱스를 통한 랜덤 액세스도 가능합니다. 하지만 요소의 삽입과 삭제가 많은 경우에는 성능이 저하될 수 있습니다.- Stack:
Stack은 후입선출(LIFO: Last In, First Out) 구조를 가지는 자료 구조입니다. Java에서는 Stack 클래스가 제공됩니다. Stack은 주로 임시 데이터를 저장하는 용도로 사용되며, 요소의 삽입과 삭제가 스택의 상단에서만 이루어지므로, 데이터 접근이 제한적입니다. 특정 상황에서는 Stack이 효율적일 수 있지만, 대부분의 경우에는 다른 자료 구조를 사용하는 것이 더 적합합니다. Java에서는 보통 Deque 인터페이스를 구현한 LinkedList를 사용하여 스택을 구현하는 것이 권장됩니다.- Array:
Array는 고정 크기의 요소들로 이루어진 연속된 데이터 구조입니다. Java에서 배열은 기본 자료형의 배열 또는 객체의 배열로 생성할 수 있습니다. 배열은 인덱스를 통해 랜덤 액세스가 가능하며, 메모리 상에서 연속된 위치에 요소를 저장하므로 접근 속도가 빠릅니다. 그러나 배열의 크기는 생성 시에 고정되므로, 크기를 동적으로 조절할 수 없습니다. 크기 조정이 필요한 경우에는 List를 사용하는 것이 더 편리할 수 있습니다.
따라서, 어떤 자료 구조를 사용해야 하는지는 사용하는 목적과 요구 사항에 따라 달라집니다. 일반적으로 요소의 추가, 삭제, 탐색이 빈번하다면 List가 효율적일 수 있습니다. 스택의 경우 특정 상황에서 유용하게 사용될 수 있지만, 일반적인 상황에서는 List를 사용하는 것이 더 적합합니다. Array는 크기가 고정되어야 하거나, 랜덤 액세스가 빈번하게 필요한 경우에 유용합니다.
Stream? for?
stream이 보기에 더 깔끔하다는 장점이 있지만 시간이 꽤 차이난다
방법 1) stream
-- 정확성 테스트: 1.84ms ~ 4.91ms
-- 효율성 테스트: 30.70ms ~ 34.33ms
방법 2) for문
-- 정확성 테스트: 0.03ms ~ 0.09ms
-- 효율성 테스트: 24.26ms ~ 28.77ms이것도 ChatGPT에게 물어본 답변을 첨부한다.
- Java 8부터 도입된 스트림(Stream)은 컬렉션과 배열 등의 데이터를 다루는 기능적인 프로그래밍 방식을 제공합니다. 스트림은 데이터를 연속적으로 처리하고 변환하는데 사용되며, 강력하고 표현력이 뛰어나다는 장점이 있습니다. 그러나 일반적으로 for 루프와 비교했을 때 스트림의 수행 시간은 더 오래 걸릴 수 있습니다.
스트림의 수행 시간이 for 루프보다 더 오래 걸리는 이유는 다음과 같습니다:- 내부 반복:
스트림은 내부적으로 반복을 처리하기 때문에, 개발자가 명시적으로 반복을 작성하는 for 루프와는 다릅니다. 스트림은 내부적으로 요소를 하나씩 가져와서 처리하므로, 반복 동작에 추가적인 오버헤드가 발생할 수 있습니다.- 중간 연산과 최종 연산:
스트림은 중간 연산과 최종 연산으로 구성됩니다. 중간 연산은 스트림을 변환하고 필터링하는 연산이며, 최종 연산은 스트림의 요소를 소비하거나 결과를 생성하는 연산입니다. 스트림의 각 요소를 처리하기 위해 중간 연산과 최종 연산이 수행되므로, 추가적인 연산 오버헤드가 발생할 수 있습니다.- 지연 연산:
스트림은 지연 연산(lazy evaluation)을 지원합니다. 즉, 최종 연산이 호출되기 전까지 중간 연산이 실제로 실행되지 않습니다. 이는 스트림의 유연성과 성능 최적화를 가능하게 해주지만, 최종 연산에서 모든 중간 연산이 수행되기 때문에 일부 연산이 불필요하게 실행될 수 있습니다.
스트림과 for 루프의 수행 시간은 다양한 요소에 따라 다를 수 있으며, 일반적으로 데이터의 양과 처리 작업의 복잡성에 따라 달라집니다. 스트림은 병렬 처리를 통해 성능을 향상시킬 수도 있습니다. 따라서, 성능 측면에서 정확한 차이를 알기 위해서는 구체적인 상황과 사용하는 데이터에 따라 벤치마킹이나 프로파일링을 통해 비교해 보는 것이 좋습니다.
프로 개발자가 되기 위해 뚜벅뚜벅.. 뚜벅초