난이도: Level 2
프로그래밍 언어: Java
문제명: 짝지어 제거하기
푼일자: 2021년 5월
URL : https://programmers.co.kr/learn/courses/30/lessons/12973
Solution.cs
문제를 이해하고 코드작성 후 결과가 정상적으로 나오는지 확인 해 보았다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
public int solution(String s) {
ArrayList<String> array = new ArrayList<>(Arrays.asList(s.split("")));
int i = 0;
while(i < array.size() - 1) {
if (array.get(i).equals(array.get(i+1))) {
array.remove(i);
array.remove(i);
i = 0;
continue;
}
i++;
}
if (array.size() == 0) return 1;
else return 0;
}
|
cs |
결과는 정상적으로 나오는 것을 확인했다. 그러나...
여기서는 효율성 테스트도 확인을 한다!
정확성 테스트에서도 결과를 도출하는데 꽤나 시간이 걸린 케이스가 있었다.
이걸 어덯게 효율적으로 코드를 수정할 수 있을까?
프로그래머스의 질문하기를 살펴본 후 Stack을 사용해 보라는 글을 보고 Stack 이라는 클래스를 검색해서 찾아보았다.
간단히 Stack 클래스는
- 데이터 추가 : .push(...)
- 최근 추가된 데이터 삭제 : .pop()
- 최근 추가된 데이터 조회 : .peek()
이러한 함수를 제공한다. 위 함수를 이용해 다음과 같이 작성하였다.
|
1
2
3
4
5
6
7
8
|
Stack<Character> stack = new Stack<>();
for (char c : s.toCharArray()) {
if (!stack.isEmpty() && stack.peek() == c) stack.pop();
else stack.push(c);
}
return stack.isEmpty() ? 1 : 0;
|
cs |
Character 인 Stack 을 하나 선언을 해준 뒤 .toCharArray() 를 사용하면 String 이 한 문자씩 char 형식으로 배열에 쌓여 반환하게 된다.
그 반환된 배열을 이용해 반복문을 돌리고, 먼저 stack 이 비어있는지 확인을 하고 비어있다면 채우고 다음 배열.
이제 비어있지 않으니 AND 조건으로 stack 에 가장 최근에 쌓인 문자가 현재 배열의 index 에 위치한 문자가 동일한 문자인지 확인을 한다. 동일한 문자라면 지금 쌓인 문자 하나를 제거하는 절차를 반복하여서 일치하지 않는 문자는 stack 에 쌓이게 되고, 모든 문자를 한번씩 검사를 한 후에 쌓인 Stack 이 있는지 확인하여 결과를 1과 0으로 반환한다.
Stack 이라는 클래스는 처음 접해보는데, 편리한 기능인 것 같다.