TIL) 프로그래머스 문제풀이

1. 문제 상황

코딩테스트 연습 - 햄버거 만들기 | 프로그래머스 스쿨 문제에서 문제 정답은 맞지만 시간 초과가 나옵니다.

 

2-1. 첫번째 풀이

 ingredient(int 배열)을 String ing로 변환합니다.

String ing = Arrays.toString(ingredient).replace(", ", "").replace("[", "").replace("]", "");

 

위 코드로 int 배열인 ingredient를 연속된 숫자의 배열인 ing로 변환할 수 있습니다. 위 문제에서 빵-야채-패티-빵 순으로 배열이 되야하므로 순서는 1231순으로 나열되어있어야 합니다. 문제의 조건에서 1231순서대로 갯수를 제외해야하므로 아래와 같이 문제를 풀었습니다.

while(ing.contains("1231")) {
  ing = ing.replaceFirst("1231", "");
  answer++;
}

 

이때, 처음부터 1231을 한개씩 공백("")으로 바꿔준 후 answer의 값을 증가시켜 줍니다. 이렇게 구현을 했을 때, 정답은 맞지만 시간복잡도에서 오류가 있었습니다.

 

2-2. 두번째 풀이

String ing = Arrays.toString(ingredient).replace(", ", "").replace("[", "").replace("]", "");

 

위와 같이 String ing를 선언해 줍니다. 위 문제에서 시간 복잡도를 줄이기 위해 중요한 것은 1231의 위치와 3의 위치라고 생각했습니다. 이때, 3이 중요한 이유는 다음과 같습니다.

1. 1231의 앞의 문자열에 3이 있다면 그 전까지는 이어질 수 없습니다. (예를 들어121212313131 같은 경우는 중간에 1231이 사라지면서 1231이 새롭게 조합이 가능한데 12312311 같은 경우는 앞의 1231이 먼저 조합 된 후 2311은 버려지게됩니다.)
2. 1231의 뒤의 문자열에 3이 있다면 그 후 문자열은 이어질 수 있습니다. 위에서 설명한 것과 같이 3은 1231기준으로 뒤에 위치해야합니다.

위의 이류로 구현 한 코드는 다음과 같습니다.

while(ing.contains("1231")) {
  int threeIdx = ing.indexOf("3");
  int idx = ing.indexOf("1231");
  String str = ing.substring(threeIdx);
  if (!str.contains("3")) {
    str = "";
  }
  if (threeIdx > idx) {
    ing = ing.substring(0, idx) + str;
  } else if (threeIdx < idx) {
    ing = ing.substring(threeIdx, idx) + str;
  }
  answer++;
}

 

1231과 3의 인덱스를 찾고, 1231을 기준으로 앞에 3이 있다면, 그 문자열을 버리는 방식으로 시간을 줄여보았습니다. 실행결과 2-1의 풀이보다 시간복잡도가 개선되었지만 contains와 indexOf, substring 함수의 실행시간이 길어서 여전히 시간초과로 실패하는 경우가 있습니다.

 

3. 정답 풀이

 결국 String으로 하는 것을 포기하고 ArrayList를 사용하였습니다.

ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < ingredient.length; i++) {
  list.add(ingredient[i]);
  if(list.size()>=4 &&
  list.get(list.size() - 4) == 1 &&
  list.get(list.size() - 3) == 2 &&
  list.get(list.size() - 2) == 3 &&
  list.get(list.size() - 1) == 1){
    answer++;
    list.remove(list.size() - 1);
    list.remove(list.size() - 2);
    list.remove(list.size() - 3);
    list.remove(list.size() - 4);
  }
}

 

위와 같이 size가 4 이상이면 조합이 가능합니다. 먼저 들어온 순서대로 1231이라면 정답(answer)을 한개 증가시키고, 정답 배열을 remove하였습니다.

 이때, 시간복잡도는 for문 1번이므로 O(n)입니다. 시간복잡도도 해결을 한 코드입니다.

 

4. 내일 할 것

• JDBC를 기반으로 JPA를 공부하기