![[Programmers] 짝지어 제거하기(2017 팁스타운)[Java]](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fw8yu6%2FbtqFUz2kA9w%2FFTbQHORPP5uOeIiZ3aAzak%2Fimg.png)
문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.
예를 들어, 문자열 S = baabaa 라면
b aa baa → bb aa → aa →
의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.
제한사항
- 문자열의 길이 : 1,000,000이하의 자연수
- 문자열은 모두 소문자로 이루어져 있습니다.
입출력 예
| s | result |
| baabaa | 1 |
| cdcd | 0 |
입출력 예 설명
입출력 예 #1
위의 예시와 같습니다.
입출력 예 #2
문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.
문제풀이
시간초과와 런타임에러로 조금 애먹었던 문제.
처음에는 스택으로 풀지 않고 단순 문자열 루프문으로 해결하려 했으나 문자열의 길이가 1,000,000이하의 자연수여서 그런가 시간초과와 유효성에서 실패가 나왔다.
문자열로 풀면 안된다는 것을 깨닫고 스택으로 풀이. 2개씩 삭제하므로 문자열의 길이가 홀수면 무조건 실패-> answer를 0 반환한다. 그리고 stack에 담아주고 while 무한반복으로 계속 돌면서 사이즈가 0이 되거나 전부 다돌아도 삭제되는 것이 없을때 break로 탈출한뒤 return 값을 맞게 반환한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
|
package algo;
import java.util.*;
import java.io.*;
public class Main {
public static int solution(String s){
int answer=0;
Stack<Character> stack = new Stack<Character>();
boolean sw=false;
if(s.length()%2==1) {
return 0;
}
stack.add(s.charAt(0));
for(int i=1;i<s.length();i++) {
stack.add(s.charAt(i));
//같을때
if(stack.size()>1 &&stack.get(stack.size()-2)==stack.get(stack.size()-1)) {
stack.pop();
stack.pop();
continue;
}
}
if(stack.size()==0) {
answer=1;
return answer;
}
int cnt=0;
while(true) {
if(stack.get(cnt)==stack.get(cnt+1)) {
stack.pop();
stack.pop();
sw=true;
cnt=0;
continue;
}
if(stack.size()==0) {
answer=1;
break;
}
if(stack.size()==cnt+2) {
if(!sw) {
break;
}
sw=false;
cnt=0;
}
cnt++;
}
return answer;
}
//문제풀이용 예시
public static void main(String[] args) {
String s="baabaa";
String s2="cdcd";
System.out.println(solution(s));
System.out.println(solution(s2));
}
}
|
cs |
https://programmers.co.kr/learn/courses/30/lessons/12973
코딩테스트 연습 - 짝지어 제거하기
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙
programmers.co.kr