![[프로그래머스 Lv2] 짝지어 제거하기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbjVtlh%2FbtrMaGtPBpr%2FEKbfyZoLqj6keYGK51KKg1%2Fimg.png)
오늘 푼 문제 중 하나를 기록으로 남긴다.
이건 정말 인내심있게 잘 했다, 이정도면 트러블슈팅이라고 봐도 되지 않을까 싶어서 기념으로 풀이를 가져왔다.
처음에 시행 착오를 거쳐 정답이 나오게끔 만들고 나서도 다섯번을 더 풀어서 효율성 테스트(시간 초과인지 아닌지)를 통과해냈다. 그냥 조금씩 손 본 게 아니고 전부 다른 로직으로 풀었다. 풀면서 '당장 낼 모레 코딩테스트를 준비한다는 애가 이러고 삽질하며 시간을 보내고 있구나' 하면서도 자꾸 다른 방법이 떠오르고 한 번만 더 해보면 될 것도 같아서, 무슨 게임 공략하듯 홀려서 시간을 보냈다.
다음은 그 장대한 서사시이다.
// 트라이 1:
class Solution {
public int solution(String s) {
if (s == null || s.length() <= 1) {
return 0;
}
StringBuilder sb = new StringBuilder(s);
// 언제 '전부' 검사했다고 판단할 거냐면
// 1. 위의 for루프에서 한 번도 제거가 실행되지 않고 인덱스 끝까지 도달했으면.
// 2. 오오오오오 재귀함수로 풀 수도?! => 포기한다
boolean removal_occurred;
do {
removal_occurred = false;
for (int i = 1; i < sb.length(); i++) {
if (sb.charAt(i-1) == sb.charAt(i)) {
sb.delete(i-1, i+1);
removal_occurred = true;
break;
}
}
// 여기까지 removal_occurred가 false인 채로 남아 있다면, 문자열 끝까지 검사하도록
// 지울 알파벳을 찾지 못했다는 것이므로 이 때 while을 벗어난다.
} while (removal_occurred);
return sb.length() > 0 ? 0 : 1;
}
}
// => 효율성 테스트에서 시간 초과로 전부 실패했다. 다시 모색해봐야겠다.
정확성 테스트
테스트 1 〉 통과 (0.05ms, 72.4MB)
테스트 2 〉 통과 (52.39ms, 91.9MB)
테스트 3 〉 통과 (1475.52ms, 92.7MB)
테스트 4 〉 통과 (1794.77ms, 78.7MB)
테스트 5 〉 통과 (1801.46ms, 88.1MB)
테스트 6 〉 통과 (1789.52ms, 89MB)
테스트 7 〉 통과 (1877.13ms, 91.3MB)
테스트 8 〉 통과 (1807.90ms, 83.9MB)
테스트 9 〉 통과 (0.02ms, 74.9MB)
테스트 10 〉 통과 (0.50ms, 72.3MB)
테스트 11 〉 통과 (0.06ms, 78.1MB)
테스트 12 〉 통과 (0.04ms, 76.3MB)
테스트 13 〉 통과 (0.04ms, 72.1MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)
테스트 5 〉 실패 (시간 초과)
테스트 6 〉 실패 (시간 초과)
테스트 7 〉 실패 (시간 초과)
테스트 8 〉 실패 (시간 초과)
// 트라이 2:
/* 어떤 문자 2개가 제거됐다면, 다음엔 그 직전 문자와 그 직후 문자 두개부터 비교해나가면 된다.
- 지워지고나서 직전 문자가 없을 수 있는 문제. => 그냥 직후 문자부터 두개를 비교한다.
- 지워지고나서 직후 문자가 없을 수 있는 문제. => 검사를 끝낸다.
더 효율적으로 하려면, 한번의 루프를 돌 때 가능한 모든 조합을 지우면 된...다.
아닌가? 한 번 발견할때마다 바로 멈춰버리는 거나 끝까지 가는거나 비슷해야 할 것도 같다.
오히려 한 번 발견할때마다 break로 벗어나는 게, 무조건 끝까지 가며 다 잡아내는 방식보다
낭비되는 검사가 없어서 더 빠를 것 같은데...
지워지고 나서 직전 직후 문자부터 비교한다 => 한 번 지울 문자가 발견되면 즉시 break로 벗어난다
이 조합이 처음과 끝 검사의 낭비 없이 가장 효율적일 것 같다.
*/
class Solution {
public int solution(String s) {
StringBuilder sb = new StringBuilder(s);
search:
while (true) {
int i = 1; // 처음 검사할 땐 인덱스 1부터 시작
// 다시 시작할 지점이 0을 지나 -1이 되어버린 경우 => 0부터 검사하라고 해준다
if (i < 0) {
i = 0;
}
// 검사를 재정의된 시작지점부터 다시 해나간다
for (i = i; i < sb.length(); i++) {
if (sb.charAt(i-1) == sb.charAt(i)) {
sb.delete(i-1, i+1);
// 지워진 문자 직전 문자 = i-2
// 지워진 문자 직후 문자 = i-1
// 다음 검사를 시작할 지점으로 i를 i-2지점으로 보낸다.
i -= 2;
break;
}
// break를 맞지 않고 i도 끝까지 도달했다면, 검사 종료
if (i == sb.length()-1) {
break search;
}
}
// 직전 검사에서 마지막 두 문자를 지웠어서, 재정의된 시작지점 i가 마지막 인덱스가 된 경우 => 더이상 비교할 문자가 없으므로 검사를 완전히 종료한다.
if (i == sb.length()-1) {
break search;
}
}
return sb.length() == 0 ? 1 : 0;
}
}
// => 얼기설기 해봤지만 아예 일반 테스트 9, 11, 12도 시간초과로 실패. 무한 루프에 걸려버린 듯 하다.
// 그리고 웬걸. 처음 해답보다 훨씬 느리다.
정확성 테스트
테스트 1 〉 통과 (0.03ms, 77.4MB)
테스트 2 〉 통과 (52.01ms, 75.5MB)
테스트 3 〉 통과 (1624.57ms, 97.6MB)
테스트 4 〉 통과 (2647.97ms, 99.7MB)
테스트 5 〉 통과 (2522.82ms, 79.6MB)
테스트 6 〉 통과 (2520.87ms, 96.4MB)
테스트 7 〉 통과 (2711.97ms, 89.1MB)
테스트 8 〉 통과 (2622.83ms, 78.6MB)
테스트 9 〉 실패 (시간 초과)
테스트 10 〉 통과 (0.45ms, 72.8MB)
테스트 11 〉 실패 (시간 초과)
테스트 12 〉 실패 (시간 초과)
테스트 13 〉 통과 (0.04ms, 75.7MB)
효율성 테스트
테스트 1 〉 실행 중단
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실행 중단
테스트 4 〉 실행 중단
테스트 5 〉 실행 중단
테스트 6 〉 실행 중단
테스트 7 〉 실행 중단
테스트 8 〉 실행 중단// 트라이 3:
/* 생각해보니 그냥 한 번의 루프에서 끝낼 수도 있을 것 같다.
문자열 연속 두 개를 찾아 제거하고 나면 그냥 두 번 백스텝해서 계속 검사하면 되잖아?
그렇게 마지막 인덱스까지 도달하면 멈추면 되는 거고.
아 맞아 for루프를 또 while로 감싼 이유가 루프 도는 동안 대상 배열 길이를 바꾸면
에러가 난다는 것 때문이었지.
그러면 while로 인덱스가 '현재' 길이-1보다 작은 동안 검사하라고 하면 되지 않을까..?
*/
class Solution {
public int solution(String s) {
if (s == null || s.length() <= 1) {
return 0;
}
StringBuilder sb = new StringBuilder(s);
int i = 1;
while (i < sb.length()) {
// System.out.p
if (sb.charAt(i-1) == sb.charAt(i)) {
sb.delete(i-1, i+1);
i -= 2;
} else {
i++;
}
// System.out.printf("i: %d, sb: %s%n", i, sb.toString());
// i가 1보다 작아져 있으면 다시 1부터 출발하도록 세팅한다
if (i < 1) {
i = 1;
}
}
return sb.length() == 0 ? 1 : 0;
}
}
// => 일반 테스트는 통과했지만 효율성이 모두 시간초과아으으악
// 오 그치만 걸리는 시간이 거의 백배가 줄어들었다. 95배쯤?
정확성 테스트
테스트 1 〉 통과 (0.05ms, 76.4MB)
테스트 2 〉 통과 (58.45ms, 77.2MB)
테스트 3 〉 통과 (51.19ms, 76.9MB)
테스트 4 〉 통과 (46.92ms, 91.7MB)
테스트 5 〉 통과 (45.67ms, 85.3MB)
테스트 6 〉 통과 (38.29ms, 81.1MB)
테스트 7 〉 통과 (36.36ms, 84.7MB)
테스트 8 〉 통과 (48.50ms, 86.4MB)
테스트 9 〉 통과 (0.02ms, 72.4MB)
테스트 10 〉 통과 (0.18ms, 78.9MB)
테스트 11 〉 통과 (0.04ms, 75.1MB)
테스트 12 〉 통과 (0.04ms, 70.2MB)
테스트 13 〉 통과 (0.03ms, 76.6MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 실패 (시간 초과)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)
테스트 5 〉 실패 (시간 초과)
테스트 6 〉 실패 (시간 초과)
테스트 7 〉 실패 (시간 초과)
테스트 8 〉 실패 (시간 초과)// (눈물의) 트라이 4:
/* 마지막 시도이다...
뒤에서부터 인덱스를 앞으로 이동하는 방법으로 해보자.
지금 i와 i+1지점을 검사한다.
-> 그 스텝에 지워지든 안지워지든 딱딱 하나씩 전 칸으로만 이동해가며 비교하면 된다는 장점이 있다.
-> i+1이 없는 경우(=길이를 초과하는 경우)엔 그냥 continue로 다음 한 칸을 이동한다.
-> 깔끔하게 -1 인덱스에 도달했을 때 끝내면 된다.
*/
class Solution {
public int solution(String s) {
if (s == null || s.length() <= 1 || s.length() % 2 != 0) {
return 0;
}
StringBuilder sb = new StringBuilder(s);
int i = sb.length()-1;
while (i > 0) {
i--;
if (i+1 >= sb.length()) { // i에게 비교할 다음 문자가 없으면
continue;
}
if (sb.charAt(i) == sb.charAt(i+1)) {
sb.delete(i, i+2);
}
}
return sb.length() == 0 ? 1 : 0;
}
}
// => 효율성 2번은 그래 통과했구나 그래...
// 문자수가 홀수면 바로 불가능함(0)을 반환하라고 했는데도 여전히 효율성 2번만 파란불이다.
// 1,3,4,5,6,7,8은 다 짝수 개라는 거네.
// 이전 해답보다 전체적으로 쬐끔 더 빨라진 듯 하다. 그 쬐끔에 효율성 2번이 간신히 세이프될만큼...
정확성 테스트
테스트 1 〉 통과 (0.01ms, 73.8MB)
테스트 2 〉 통과 (6.05ms, 81.6MB)
테스트 3 〉 통과 (16.92ms, 83.3MB)
테스트 4 〉 통과 (20.31ms, 87.6MB)
테스트 5 〉 통과 (25.78ms, 79.6MB)
테스트 6 〉 통과 (20.30ms, 82.2MB)
테스트 7 〉 통과 (20.69ms, 89.6MB)
테스트 8 〉 통과 (30.02ms, 78.3MB)
테스트 9 〉 통과 (0.02ms, 75.4MB)
테스트 10 〉 통과 (0.16ms, 76MB)
테스트 11 〉 통과 (0.02ms, 75.3MB)
테스트 12 〉 통과 (0.04ms, 73MB)
테스트 13 〉 통과 (0.04ms, 74.4MB)
효율성 테스트
테스트 1 〉 실패 (시간 초과)
테스트 2 〉 통과 (16.69ms, 56.5MB)
테스트 3 〉 실패 (시간 초과)
테스트 4 〉 실패 (시간 초과)
테스트 5 〉 실패 (시간 초과)
테스트 6 〉 실패 (시간 초과)
테스트 7 〉 실패 (시간 초과)
테스트 8 〉 실패 (시간 초과)// 트라이 5:
/* 진짜 마지막. 질문하기에서 힌트를 얻어서.
스택에 넣었다 뺐다 하고, 애초에 문자개수가 짝수가 아니면 0을 반환시켜버리도록 한다.
아니, StringBuilder가 그렇게 느려?! 겨우 문자 백만개도 시간 내에 못 다루냐구!!
*/
import java.util.Stack;
class Solution {
public int solution(String s) {
if (s == null || s.length() % 2 != 0 || s.length() <= 1) {
return 0;
}
Stack<Character> stack = new Stack<>();
for (int i = 0; i < s.length(); i++) {
char letter = s.charAt(i);
if (!stack.empty() && stack.peek() == letter) {
stack.pop();
} else {
stack.push(letter);
}
}
return stack.empty() ? 1 : 0;
}
}
정확성 테스트
테스트 1 〉 통과 (0.03ms, 75.3MB)
테스트 2 〉 통과 (14.28ms, 75.7MB)
테스트 3 〉 통과 (27.62ms, 74.4MB)
테스트 4 〉 통과 (36.44ms, 89.3MB)
테스트 5 〉 통과 (17.09ms, 71.5MB)
테스트 6 〉 통과 (14.93ms, 86.5MB)
테스트 7 〉 통과 (18.68ms, 70MB)
테스트 8 〉 통과 (16.73ms, 78.4MB)
테스트 9 〉 통과 (0.01ms, 71.6MB)
테스트 10 〉 통과 (0.38ms, 82.4MB)
테스트 11 〉 통과 (0.02ms, 78.3MB)
테스트 12 〉 통과 (0.02ms, 77.7MB)
테스트 13 〉 통과 (0.27ms, 72.2MB)
효율성 테스트
테스트 1 〉 통과 (64.34ms, 61.1MB)
테스트 2 〉 통과 (39.13ms, 56.1MB)
테스트 3 〉 통과 (52.53ms, 58.7MB)
테스트 4 〉 통과 (50.40ms, 59.1MB)
테스트 5 〉 통과 (49.41ms, 58.6MB)
테스트 6 〉 통과 (52.71ms, 58.6MB)
테스트 7 〉 통과 (54.11ms, 58.5MB)
테스트 8 〉 통과 (49.97ms, 59.3MB)
새롭게 찾아 쓴(a.k.a. 구글링한) 코드:
- Stack<E>이란 것. 컬렉션 공부는 아직인데 이런 것도 있었네. 보유 함수가 5개뿐인 것이 아주 마음에 든다. 게다가 전부 유용한 것들이고 사용하기도 쉽다.
- => empty(), peek(), pop(), push(E), search(Object)
- do-while문을 복습했다. 특히 기억할 것: 그냥 while문은 조건식에 쓰일 변수가 초기화가 되어있지 않으면, while 블럭 안에서 초기화를 시키더라도 "초기화가 되어있지 않을 수도 있음 에러"라고 컴파일을 안한다. 그런데 do 안에서 초기화해주면, 밖에서 선언만 했더라도 (참으로 합리적이게도) while의 조건식에서 써도 문제가 없다. do-while문에서는 while 조건식이 제일 마지막에 붙으니까. do가 무조건 한 번은 실행되고 while 조건을 테스트 할 테니까. 이게 문법적으로도 일치되게 구현되어 있으니 합리적이다. 당연한 소리를 하고 있는가? 자바를 무시하는 건 아닙니다.
- 이름붙인 루프(labeled loop) 사용법 복습. while에게도 이름을 붙일 수 있었다는 사실.
- StringBuilder의 함수들 .length(), .charAt(인덱스), .delete(처음인덱스, 끝인덱스+1)은 이제 못 잊겠다. String이랑 용법이 거의 비슷하더라. (StringBuilder와 쌍둥이인) StringBuffer용법까지 덩달아 익힌 셈이니
삽질이 아니라부디 이득이라 해두자...
아쉬운 점:
- 마지막 해답까지 스스로의 힘으로 풀 수 있었다면 좋았을 텐데. 하지만 그게 여한없는(?) 최선이었다.
- 두번째 트라이에서는 왜 시간이 더 걸렸을까? 첫번째 해답보다 분명히 더 적은 요소를 검사하는데 말이다. 그리고 어떻게 시간이 초과되는지도 알아내지 못했다. 무한루프에 왜 걸렸을까.
- StringBuilder가 왜 Stack보다 그토록 느린지도 알 수 없다. 일단 StringBuilder를 살펴보자면,
- 1. 처음 한 번에 String s를 전부 넣어서 만들고 이후로 요소를 추가하는 작업이 없기 때문에, 불필요한 공간을 늘리느라 낭비되는 작업은 없다.
- 2. append나 insert는 받은 파라미터를 String으로 우선 바꿔서 집어 넣는다는데 나는 여기서 append나 insert를 쓰지 않기 때문에 매번 String을 만드는 작업을 하지 않는다. 그러니까 String을 만드는 게 시간이 좀 걸리는 일이라면, 나는 해당 사항이 없으니 충분히 빨라야 하지 않을까?
- StringBuilder의 저장 자료구조는 뭐고, Stack은 뭘까? 여기에 핵심이 있을 것 같다. 다음에 공부해보자.