들어가기에 앞서
참고한 자료를 바탕으로 비전문가가 정리한 글이므로 오류가 있을 수 있습니다.
오류에 대한 지적 사항은 언제든지 환영합니다. 부디 댓글로 알려주시길 바랍니다. 감사합니다.
스택(Stack)
출처: geeksforgeeks.org
대표적인 자료구조 중 하나인 스택은 그 이름에서도 알 수 있듯이, 데이터를 쌓아 올리는 자료구조라고 볼 수 있다.
스택은 작업이 수행되는 특정 순서를 따르는 선형 데이터 구조이며, 데이터가 출력되는 순서는 LIFO(Last In First Out) 또는 FILO(First In Last Out)일 수 있다.
스택의 대표적인 예시로는 브라우저의 뒤로가기 버튼을 누름으로써 가장 최근 방문한 페이지로 이동하기, 뷔페에 쌓여있는 접시 더미 등이 있다.
대표적인 JAVA Stack의 메소드
자주 사용하는 자바 스택의 메소드는 아래와 같다.
•
push(data): 스택에 값(데이터)를 추가한다.
•
pop(): 스택의 최상단 값을 반환 및 삭제한다.
•
peek(): 스택의 최상단 값을 반환한다.
•
empty(): 해당 스택이 비어 있는지 확인하며 비어있으면 true를 반환한다.
프로그래머스 - 같은 숫자는 싫어
이제 자바 스택과 그 메소드를 활용하여 프로그래머스의 “같은 숫자는 싫어” 문제를 풀어보자.
public int[] solution(int []arr) {
Stack<Integer> st = new Stack<>();
for(int num : arr){
if(st.empty()){
st.push(num);
}
else if(!st.contains(num) || st.peek() != num){
st.push(num);
}
}
Integer[] tempArr = st.toArray(new Integer[st.size()]);
int[] answer = new int[tempArr.length];
for(int i = 0; i < tempArr.length ; i++){
answer[i] = tempArr[i];
}
return answer;
}
Java
복사
먼저, Integer 타입(기본 데이터타입 (int,double,String,char등)의 데이터를 객체로 취급해야 함)으로 스택을 선언한다. 그리고 주어진 arr의 값들과 스택의 값을 비교하여 중복된 값을 제외하고 스택에 추가 및 그 스택을 배열로 변환하는 간단한 코드이다.
큐(Queue)
출처: geeksforgeeks.org
큐도 역시나 자료구조를 배운다면 반드시 알게 되는 대표적인 자료구조이다. 이름에서 유추할 수 있듯이, 줄을 지어 데이터를 입력 및 출력하는 선형적인 자료구조인 큐는 스택과는 다르게 FIFO 방식으로 데이터를 처리한다.
큐의 대표적인 예시로는 놀이공원에서 티켓팅을 위해 줄을 서는 사람들, 편의점에서 물건 진열을 유통기한 순으로 하는 모습 등이 있다.
대표적인 JAVA Queue의 메소드
출처: 오라클 자바 공식문서
큐는 자바에서 스택과는 다르게 인터페이스이며, 그렇기에 ArrayList를 이용하여 구현해야 한다. 또한, 위 표와 같이 삽입과 삭제 및 조회를 담당하는 두 종류의 메소드들이 있으며, 예외 처리가 추가적으로 있는 지 없는 지에 따라 다를 뿐, 근본적인 기능은 동일한 메소드들이다.
프로그래머스 - 기능개발
이제 위의 메소드들을 활용하여 프로그래머스의 “기능개발” 문제를 풀어보자.
public int[] solution(int[] progresses, int[] speeds) {
Queue<Integer> queue = new LinkedList<>();
List<Integer> answer = new ArrayList<>();
for(int i=0; i<progresses.length; i++){
queue.add((int) (Math.ceil((100.0 - progresses[i]) / speeds[i])));
}
while (!queue.isEmpty()){
int day = queue.poll();
int cnt = 1; //배포 가능 기능 개수
while(!queue.isEmpty() && day >= queue.peek()){
cnt++;
queue.poll();
}
answer.add(cnt);
}
return answer.stream().mapToInt(Integer::intValue).toArray();
}
Java
복사
먼저 Integer타입의 LinkedList로 큐를 구현하고 해당 큐에 기능 구현에 필요한 작업 일 수(Math.ceil((100.0 - progresses[i]) / speeds[i])))를 삽입한다.
문제에서 구현해야 하는 기능들은 배포해야하는 순서로 구성되어 있고, 뒤에 있는 기능이 먼저 개발 완료된다 하더라도 앞에 있는 기능이 먼저 완료되어야만 함께 배포가 가능하다고 한다. 따라서, 큐에 있는 요소(작업 일 수)를 꺼내서(poll) 남은 큐의 맨앞 값(peek)과 비교한다.
이런 식으로 비교를 하여 크다면 배포 가능 기능 개수를 증가하고(cnt++) 작다면 해당 개수를 정답 리스트에 담는 식으로 로직을 완성하면된다.