기능개발
문제설명 생략
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
int[] days = new int[progresses.length];
int day = 0;
for(int i = 0; i < progresses.length; i++) {
for (int j = 0; progresses[i] < 100; j++) {
progresses[i] += speeds[i];
day ++;
if (progresses[i] >= 100) {
days[i] = day;
day = 0;
}
}
}
int temp = days[0];
int update = 0;
List<Integer> completeUpdate = new ArrayList<>();
for (int i = 0; i < days.length; i++) {
if (days[i] <= temp) {
update ++;
if(i == days.length-1) {
completeUpdate.add(update);
}
} else {
completeUpdate.add(update);
update = 1;
temp = days[i];
if(i == days.length-1) {
completeUpdate.add(update);
}
}
}
int[] answer = new int[completeUpdate.size()];
for (int i = 0; i < answer.length; i++) {
answer[i] = completeUpdate.get(i);
}
return answer;
}
}프로그래머스 큐 스택에 해당되는 문제이다.
큐나 스택을 다뤄본 적이 없기 때문에 우선은 배열을 사용해 해결하였다.
해결 방법 아이디어
-
progress배열의 각각 값들을 speeds 배열 값들로 더해 100으로 만든다 (이 과정은 2중 for문으로 )
-
progress[ i ]값을 100까지 만들때까지 몇번 반복했는지 구하고 update변수에 저장한다. 이 값들을 days라는 배열에 저장한다.
-
days에 있는 값들의 크기를 비교하기 위해 temp변수를 만들어주고 days[ i ]가 temp보다 작거나 같으면 update 변수를 +1, 크다면 update를 그대로 completeUpdate 리스트에 추가해주고 update 값을 1로, temp 값은 days[i]로 변경해준다.
이 과정을 반복하여 정답이 될 리스트를 얻을 수 있다. 그러나 오답 처리가 되었다. 이유는
println으로 update를 찍어 봤을 때 정답을 위한 값이 잘 나온다는 것을 확인 할 수 있다. 그런데 completeUpdate 리스트에 도저히 마지막 값이 추가 되지 않는 문제가 있어서 1번은 [2] 하나만 추가되고
2번은 [1, 3] 3번은 [1, 1] 뿐만 값으로 출력되었다.
이 문제 때문에 println을 매우 많이 찍어보고 많은 시간을 날렸다. 애초에 문제 정의 하는 거 부터 굉장히 많은 시간이 걸렸는데 print 많이 찍어보니 찾게 된 문제점이었다.
다 풀고 마지막이어서 다른 사람의 답을 보기도 애매했다. 그래서 계속 매달렸고 결국에 얻어낸 것은 마지막 수는 리스트 자체에 추가되지 않는 다는 것이 결론으로 나온 것이다.
문제 정의 후에도 문제였다. 조건문 바꿔보고 계속 시도해봤는데 도저히 풀리지 않았다. 그래서 낸 결론은 리스트의 마지막이라면 completeUpdate 리스트에 추가하게끔 코드를 추가했다.
if(i == days.length-1) {
completeUpdate.add(update);
}이 방안을 빨리 생각하긴 했는데 너무 억지 같아서 추가하지 않다가 도저히 풀리지 않아 추가하고 정답을 얻을 수 있었다.
근데 속도는 진짜 빠르다 오우
일단 나는 큐를 공부해보지 않아서 배열로 풀어보았는데 문제 분류가 스택/큐 이기 때문에 스택 큐 방식도 알아보겠다. 다른 사람 풀이를 보면서 알아가 보도록 하겠다.
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
Queue<Integer> q = new LinkedList<>();
List<Integer> answerList = new ArrayList<>();
for (int i = 0; i < speeds.length; i++) {
double remain = (100 - progresses[i]) / (double) speeds[i];
int date = (int) Math.ceil(remain);
if (!q.isEmpty() && q.peek() < date) {
answerList.add(q.size());
q.clear();
}
q.offer(date);
}
answerList.add(q.size());
int[] answer = new int[answerList.size()];
for (int i = 0; i < answer.length; i++) {
answer[i] = answerList.get(i);
}
return answer;
}
}1 )
큐가 비어있지 않거나 첫 번째 값이 date보다 작을 경우
큐의 길이를 answerList에 추가
큐 초기화
이후 큐에 값 추가
2)
조건에 맞지 않으면 그냥 q에 값 추가
for 문이 끝나면 마지막 값을 q에 추가 시켜주기 위해
answerList.add(q.size()); 를 써준다.
시각화
date를 7, 3, 9 라고 해준다면
우선 for문 첫 번째는 q에 값이 없으므로 우선 큐에 7 추가
q[ 7 ]
다음 date는 3이므로 q.peek() < date ( 7 < 3 ) 의 조건에 성립하지 않기 때문에
지나가고 큐에 3 추가
q[ 7, 3 ]
다음 date는 9
이번에는 q.peek() < date ( 7 < 9 ) 의 조건에 성립하기 때문에
q[ 7, 3 ] 이 큐의 길이를 answerList에 추가 ( answerList [ 2 ] )
큐 초기화 q [ ]
큐에 date 추가
q[ 9 ]
for문이 종료되고 마지막으로 q의 길이를 answerList에 추가 ( answerList [ 2, 1 ] )
나와 다른 점은 나는 조건에 성립하면 변수에 값을 ++ 해주고 그 변수를 리스트에 넣는 방식으로 풀었다면
큐 풀이는 조건에 성립하면 큐에 값을 넣고 그 길이를 배열에 추가하는 방식으로 푼 점이 다른 것 같다.
풀이보면서 큐를 알게되었는데 딱히 어려운 건 없는 것 같다.
그리고
해당 풀이를 보면서
if(i == days.length-1) {
completeUpdate.add(update);
}이 코드를 줄일 수 있었다. 풀이처럼 for문이 끝나면 배열에 추가해주면 된다. 왜 이걸 생각못했을까 현타가 오지만
괜찮다. 알게 되었으니까.. 6줄을 줄일 수 있다.
그럼 내 코드는
import java.util.*;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
int[] days = new int[progresses.length];
int day = 0;
for(int i = 0; i < progresses.length; i++) {
for (int j = 0; progresses[i] < 100; j++) {
progresses[i] += speeds[i];
day ++;
if (progresses[i] >= 100) {
days[i] = day;
day = 0;
}
}
}
int temp = days[0];
int update = 0;
List<Integer> completeUpdate = new ArrayList<>();
for (int i = 0; i < days.length; i++) {
if (days[i] <= temp) {
update ++;
} else {
completeUpdate.add(update);
update = 1;
temp = days[i];
}
}
completeUpdate.add(update);
int[] answer = new int[completeUpdate.size()];
for (int i = 0; i < answer.length; i++) {
answer[i] = completeUpdate.get(i);
}
return answer;
}
}이렇게 되면 된다.
이상 큐에 대한 설명은 하지 않았지만 큐를 알게되었고 나와 다른 풀이도 해석해보았다.
큐 메소드는 왜 적지 않았는가?? 나만 알면 그만이야 ~
는 사실 귀찮다. 큐 사용법은 그냥 찾아보면 잘 나와있다. 큐에 대해 적는 것은 그저 시간낭비 일 뿐이다.
