프로그래머스에서 제공하는 문제들 중 큐에 대해 연습하기 위한 문제를 풀었다.
문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42588
코딩테스트 연습 - 탑 | 프로그래머스
수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다. 발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다. 예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다. 높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7
programmers.co.kr
문제 설명
풀이 과정
큐를 활용해 이전 요소와 비료를 순차적으로 수행하며 수신이 가능한 탑을 찾아나가도록 했다.
처음에는 별다른 어려움 없이 쉽게 풀 수 있을거라 생각했지만 큐에는 요소를 순서대로 찾아가는 메소드가 없다는 생각지 못한 문제가 발생했다.
순서대로 찾는 방법을 대체하기 위해 입력받은 배열을 한 칸씩 앞으로 돌며 조건문을 통해 비교하는 방식을 채택하게 되었다.
...
for (int i = 1; i < heights.length; i++) {
int comp = beforeQ.poll();
for (int j = i - 1; j >= 0; j--) {
if (comp < heights[j]) {
resultArray[i] = j + 1;
break;
}
}
}
...
처음에는 의도와는 달리 큐의 값과 배열을 비교하는 데 IndexOutOfBoundException이 발생했다. 이 원인을 알고자 디버그를 수행했는데 조건문을 통해 탑을 비교하는 두 번째 반복문에서 조건 비교 후 j의 값을 변화시킬 때 1씩 빼야할 것을 더해 발생했던 것이엇다.
...
for (int j = i - 1; j >= 0; j++) {
...
}
...
코드 작성을 완료하고 테스트를 진행할 때 입력값을 [6, 9, 5, 7, 4]로 입력했을 때 결과가 [0, 0, 2, 2, 4]여야 했지만 [0, 0, 2, 0, 0]로 나오는 문제를 찾았다. 다시 코드를 리뷰해본 결과 첫 번째 반복문 부분에서 반복이 종료되는 조건을 beforeQ.size()메소드로 설정해버려 비교가 진행함에 따라 poll()메소드를 통해 점점 요소가 제거되고 변화하는 큐의 사이즈로 인해 3, 4번 인덱스는 아예 비교하는 코드로의 진행이 되지 않고 반복이 종료된 것이었다.
...
for (int i = 0; i < beforeQ.size(); i++) {
...
}
...
위 문제는 반복의 종료 조건을 큐의 사이즈가 아닌 입력 배열의 길이로 바꿈으로써 해결할 수 있었다.
최종 코드
package StackQueueProblem;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Tower {
public static void main(String[] args) {
init();
}
static void init() {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
try {
String input = br.readLine();
StringTokenizer st = new StringTokenizer(input);
int index = 0;
int[] heights = new int[st.countTokens()];
while (st.hasMoreTokens())
heights[index++] = Integer.parseInt(st.nextToken());
bw.write(Arrays.toString(solution(heights)));
bw.close();
} catch (IOException e) {
e.printStackTrace();
}
}
static int[] solution(int[] heights) {
int[] resultArray = new int[heights.length];
Queue<Integer> beforeQ = new LinkedList<>(); //아직 조회되지 않은 송신탑 저장
for (int i = 1; i < heights.length; i++)
beforeQ.offer(heights[i]);
for (int i = 1; i < heights.length; i++) {
int comp = beforeQ.poll();
for (int j = i - 1; j >= 0; j--)
if (comp < heights[j]) {
resultArray[i] = j + 1;
break;
}
}
return resultArray;
}
}
채점 결과
