728x90
반응형
https://github.com/ROUTINE-STUDY/Algorithm
알고리즘 스터디를 진행하고 있습니다. 😊
초보들로 구성되어 있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
참여 문의는 댓글 혹은 GitHub 주소를 참고해 주세요.
문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/133502#qna
풀이 방법
문자열("1231")을 공백으로 치환하면 된다.
내 코드(JAVA)
public static int solution(int[] ingredient) {
final String MAKE_BURGER = "1231";
int answer = 0;
StringBuilder sb = new StringBuilder();
// 미리 다 담고
for (int i : ingredient) {
sb.append(i);
}
// 반복문을 돌며 "1234" -> ""로 치환하며 갯수를 샌다
while (sb.indexOf(MAKE_BURGER) > -1) {
int from = sb.indexOf(MAKE_BURGER);
sb.delete(from, from + 4);
// sb.replace(from, from + 3, "");
answer++;
}
return answer;
}
해당 코드는 3개의 케이스에서 시간초과가 발생한다.
미리 담아두지 말고 담을 때마다 검사하거나, indexOf를 한 번만 하도록 개선하거나, replace를 delete로 바꾸는 등 리팩토링을 해봤지만 잘 되지 않았다.
public static int solution(int[] ingredient) {
final String MAKE_BURGER = "1231";
int answer = 0;
StringBuilder sb = new StringBuilder();
for (int i : ingredient) {
sb.append(i);
// 1(빵)이 나오고, 쌓인 재료가 4개 이상(만드는데 필요한 갯수)이고, 끝자리부터 뒷 4자리의 문자열이 "1231"인지 확인
if(i == 1 && sb.length() >= 4 && sb.subSequence(sb.length() - 4, sb.length()).equals(MAKE_BURGER)) {
sb.delete(sb.length() - 4, sb.length()); // 햄버거 만들기
answer++;
}
}
return answer;
}
- 문제를 잘 보면 빵이 나왔을 때만 햄버거를 만들 수 있는지 확인하여 만들 수 있다.
- 한 번 만드는데 4개의 재료가 필요하니 최소 쌓인 문자열의 길이는 4보다 커야 한다.
- 재료를 쌓을 때마다 검사하므로 마지막 문자열에서 필요 재료의 개수인 4자리만 검사하면 된다.
StringBuilder의 subSequence()를 활용했는데, 문자열의 위치를 사용하여 잘라내 새로운 문자 시퀀스를 만들어낸다.
미리 다 쌓아두고 찾을 때 쌓인 데이터가 많거나, 가장 뒤에 나온다면 탐색해야 할 양이 많아진다.
StringBuilder sb = new StringBuilder("12345678");
println(sb.subSequence(sb.length() - 4, sb.length())); // 5678
println(sb.subSequence(0, 4)); // 1234
728x90
반응형
'알고리즘' 카테고리의 다른 글
[프로그래머스/JAVA] 둘만의 암호 (1) | 2023.11.12 |
---|---|
[프로그래머스/JAVA] 대충 만든 자판 (0) | 2023.11.12 |
[프로그래머스/JAVA] 달리기 경주 (0) | 2023.11.08 |
[프로그래머스/JAVA] 개인정보 수집 유효기간 (0) | 2023.08.04 |
[프로그래머스/JAVA] 야간 전술보행 (0) | 2022.11.14 |
댓글