일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- Spring
- template
- immutable
- string
- build_test
- rds
- Github
- git
- 사이드 프로젝트
- redis
- compiler
- workflow
- EC2
- mutable
- db
- JUnit
- CodeDeploy
- springboot
- Action
- aws
- QueryDSL
- Airflow
- kotlin
- JPA
- AOP
- 알고리즘
- 토비의 스프링
- java
- Today
- Total
개발 일기
프로그래머스 레벨 2 짝지어 제거하기 (JAVA) 본문
이번에는 2 레벨에 도전해 보았다
푼 문제!
https://programmers.co.kr/learn/courses/30/lessons/12973
코딩테스트 연습 - 짝지어 제거하기
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙
programmers.co.kr
모든 코드는 GitHub 에 올려놓았다.
이 문제는 Stack을 이용해야 한다고 들어서
Stack을 어떻게 이용해야 풀 수 있을지에만 생각하다가 ( Stack 처음 써본다.. )
쉬운 거를 놓치고 말았다
간단하게!
0번째 index부터 값을 추가해가며 비교해 주면 된다.
ex) baabaa 라면
0번째부터
Stack에 b를 넣고 다음 a값과 비교하고
같지 않다면 Stack에 a를 추가
같다면 pop으로 현재 들어있는 b를 제거해준다
이거는 Stack 말고 ArrayList , LinkedList , StringBuilder로 풀 수 있다
처음에는 StringBuilder로 풀다가 시간 초과가 나서 못 풀었지만 문제의 접근을 다르게 하면
Stack 말고도 다른 거로도 풀 수 있는 문제다.
모든 방식의 코드를 올려놓겠다..
Stack
//Stack
public static int solution(String s) {
Stack<String> stringStack = new Stack<>();
for(int i=0; i<s.length(); i++) {
if(!stringStack.isEmpty()) { // 스택이 비어있지 않으면
if(stringStack.peek().equals(String.valueOf(s.charAt(i)))) { // 첫 값은 0번쨰 index 값이 들감 0 , 1 비교 -> 0 1 같다면 둘다 삭제해야함 스택에서 0 번만 삭제시켜줌
stringStack.pop();
continue;
}
}
stringStack.push(String.valueOf(s.charAt(i))); // 값넣어주기
}
return stringStack.size() == 0 ? 1 : 0;
}
LinkedList
//LinkedList
public static int solution2(String s) {
LinkedList<String> stringLinkedList = new LinkedList<>();
for(int i=0; i<s.length(); i++) {
if(!stringLinkedList.isEmpty()) {
if(stringLinkedList.get(stringLinkedList.size() -1).equals(String.valueOf(s.charAt(i)))) {
stringLinkedList.remove(stringLinkedList.size() -1);
continue;
}
}
stringLinkedList.add(String.valueOf(s.charAt(i)));
}
return stringLinkedList.size() == 0 ? 1 : 0;
}
ArrayList
//ArrayList
public static int solution3(String s) {
ArrayList<String> arrayList = new ArrayList<>();
for(int i=0; i<s.length(); i++) {
if(!arrayList.isEmpty()) {
if(arrayList.get(arrayList.size() -1).equals(String.valueOf(s.charAt(i)))) {
arrayList.remove(arrayList.size() -1);
continue;
}
}
arrayList.add(String.valueOf(s.charAt(i)));
}
return arrayList.size() == 0 ? 1 : 0;
}
StringBuilder
//builder
public static int solution4(String s) {
StringBuilder builder = new StringBuilder();
for(int i=0; i<s.length(); i++) {
if(builder.length() != 0) {
if(builder.charAt(builder.length() -1) == s.charAt(i)) {
builder.deleteCharAt(builder.length() -1);
continue;
}
}
builder.append(s.charAt(i));
}
return builder.length() == 0 ? 1: 0;
}
놀랍게도.. StringBuilder가 속도가 제일 빨랐다..
문제의 접근을 다양하게 할 수 있는 사고를 길러야겠다..
'알고리즘 > programmers' 카테고리의 다른 글
프로그래머스 레벨2 전화번호 목록 (JAVA) (0) | 2021.07.11 |
---|---|
프로그래머스 레벨2 튜플 (JAVA) (0) | 2021.07.11 |
프로그래머스 레벨 1 숫자 문자열과 영단어 (JAVA) (0) | 2021.07.10 |
프로그래머스 레벨 1 키패드 누르기 알고리즘 (JAVA) (0) | 2021.07.10 |
프로그래머스 레벨1 소수구하기 (JAVA) (0) | 2021.07.09 |