프로그래머스 lv2 택배상자

문제 링크

택배상자

풀이

• 처음에는 for문으로 order를 전부 돌면서 그 안에서 조건을 걸고 찾았었다. 결과는 테스트케이스 10개중에 6개까지 맞고 4개는 시간 초과
• 왜인가 고민좀 해봤는데, 아무래도 for문 돌면서 (최대 100000개) 그 안에서 또 한번 더 while 돌면서 (아무리 break라도) 하나하나 찾아내는 그 과정에서 시간 초과가 발생하는 것 같았다.
• 다른 방법을 찾다가 파이썬으로 푼 사람의 글을 읽고 어느정도 힌트를 얻었다. 바로 배열의 인덱스를 기준으로 해서 return값을 돌려줄 수 있도록 할 것
• 이렇게 하면 굳이 두 번의 for문을 돌지 않고도 구할 수 있었다.

import java.util.Deque;
import java.util.LinkedList;
import java.util.stream.IntStream;

public class 택배상자 {
	public int solution(int[] order) {

		Deque<Integer> container = new LinkedList<>();
		IntStream.rangeClosed(1, order.length).forEach(container::push);
		Deque<Integer> tmpContainer = new LinkedList<>();

//		for문을 2번 도는 풀이 방법
//		int answer = 0;
//		for (int i : order) {
//			boolean isExist = container.contains(i);
//
//			if (isExist) {
//				while (!container.isEmpty()) {
//					if (i == container.getLast()) {
//						container.removeLast();
//						answer++;
//						break;
//					} else {
//						tmpContainer.push(container.pollLast());
//					}
//				}
//			} else {
//				if (!tmpContainer.isEmpty()) {
//					if (tmpContainer.peek() != i){
//						return answer;
//					} else {
//						tmpContainer.pop();
//						answer++;
//					}
//				}
//			}
//		}

		int cnt = 0;
		while (!container.isEmpty()){
			if(order[cnt] != container.getLast()){
				if(!tmpContainer.isEmpty() && order[cnt] == tmpContainer.peek()){
					cnt+=1;
					tmpContainer.pop();
				} else {
					tmpContainer.push(container.pollLast());
				}
			} else {
				cnt+=1;
				container.removeLast();
			}
		}

		while (!tmpContainer.isEmpty()){
			if(order[cnt] == tmpContainer.peek()){
				cnt+=1;
				tmpContainer.pop();
			} else break;
		}

		return cnt;
	}
}    

• 무조건 for 문을 다 돌려보지 말고 한번 더 생각을 해보는 습관을 들이자.