https://school.programmers.co.kr/learn/courses/30/lessons/12973
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
LV 2
구현 방법
문자열의 길이 : 1,000,000이하의 자연수 조건을 통해 시간 복잡도를 고려하여 구현해야 한다.
<시간 초과 경우>
ArrayList로 구현 할 경우, remove() 함수가 O(n)의 시간 복잡도를 가지고, 두 짝을 찾는데에도 O(n)을 가지므로
총 O(n^2)의 시간복잡도를 가지게 된다. 이런 경우, 시간초과가 발생한다.
또한 LinkedList로 구현 할 경우, remove() 함수는 O(1)을 가지지만 get()함수가 O(n)의 시간 복잡도를 가진다. 따라서 두 짝을 찾는 시간복잡도 O(n)까지 하여 총 O(n^2)의 시간복잡도를 가지게 된다. 이 경우 또한 시간초과가 발생한다.
<올바른 구현 - stack>
문자 두개가 같은 경우에는 stack에 넣지 않고, 다른 경우 stack에 값을 넣는다. 그 후 stack의 가장 위의 값과 현재 비교할 문자열의 문자를 비교하여 같은 경우 pop, 다른 경우 stack에 push 하여 구현한다.
이 경우, stack의 push와 pop은 O(1)의 시간 복잡도를 가지므로, 시간복잡도는 문자열의 문자를 하나씩 꺼낼 때의 O(n)만 가지게 된다.
코드
ArrayList 구현 - 시간 초과
import java.util.List;
import java.util.ArrayList;
class Solution
{
public int solution(String s)
{
List<Character> sList = new ArrayList<Character>();
for(char c : s.toCharArray()) {
sList.add(c);
}
int start = 0;
int end = 1;
while(end < sList.size()) {
if (sList.get(start) == sList.get(end)) {
sList.remove(end);
sList.remove(start);
start = 0;
end = 1;
} else {
start++;
end++;
}
}
if(sList.isEmpty())
return 1;
else
return 0;
}
}
stack 구현
import java.util.Stack;
class Solution
{
public int solution(String s)
{
Stack<Character> stack = new Stack<>();
for(char c : s.toCharArray()) {
if(!stack.empty() && stack.peek() == c) {
stack.pop();
} else {
stack.add(c);
}
}
if(stack.empty())
return 1;
else
return 0;
}
}
느낀 점
큰 범위는 시간 복잡도 계산 필수!
참고 블로그
'알고리즘' 카테고리의 다른 글
자바 - 프로그래머스 / [1차] 뉴스 클러스터링 (1) | 2023.05.26 |
---|---|
자바 - 프로그래머스 / 연속 부분 수열 합의 개수 (0) | 2023.05.20 |
자바 - 프로그래머스 / 피보나치 수 (1) | 2023.05.03 |
자바 - 프로그래머스 / 개인정보 수집 유효기간 (0) | 2023.05.03 |
자바 - 프로그래머스 / [1차]캐시 (0) | 2023.05.02 |