Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- Lv. 0
- Java
- bfs
- 소프티어
- softeer
- SQL
- select
- join
- Lv. 3
- 티스토리챌린지
- group by
- level 3
- 파이썬
- 오블완
- Python
- 동적계획법
- C언어
- 프로그래머스
- SQL 고득점 KIT
- dfs
- 너비 우선 탐색
- LEVEL 2
- 자바스크립트
- Lv. 1
- Dynamic Programming
- Lv. 2
- DP
- programmers
- 깊이 우선 탐색
- javascript
Archives
- Today
- Total
몸과 마음이 건전한 SW 개발자
프로그래머스 [Lv. 2] 괄호 변환 {언어 : JavaScript} 본문
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/60058
정답 코드
function solution(p) {
const isValid = (string) => {
const stack = [];
for (let idx = 0; idx < string.length; idx++) {
if (stack.length) {
if (string.at(idx) === ")" && stack.at(-1) === "(") {
stack.pop();
} else {
stack.push(string.at(idx));
}
} else {
stack.push(string.at(idx));
}
}
return stack.length ? false : true;
}
const turnString = (string) => {
const stack = [];
for (let idx = 0; idx < string.length; idx++) {
if (string.at(idx) === "(") {
stack.push(")");
} else {
stack.push("(");
}
}
return stack.join("");
}
const dfs = (string) => {
if (string.length === 0) {
return "";
}
let balance = 0;
let newString = "";
for (let idx = 0; idx < string.length; idx++) {
if (string.at(idx) === "(") {
balance += 1;
} else {
balance -= 1;
}
if (balance === 0) {
if (isValid(string.slice(0, idx+1))) {
newString += string.slice(0, idx+1) + dfs(string.slice(idx+1));
} else {
newString += "(" + dfs(string.slice(idx+1)) + ")" + turnString(string.slice(1, idx));
}
break;
}
}
return newString;
}
const answer = dfs(p);
return answer;
}
풀이 방법
- 괄호가 올바른 괄호 문자열인지 확인하는 함수와 문자열 전부를 뒤집어 주는 함수를 만들었다.
- dfs를 살펴보면
- 빈 문자열은 그대로 반환한다.
- 매개변수 설명을 보면 일단 p가 무조건 짝수이다.
- balance가 0인 경우 일단 균형잡힌 괄호 문자열이다.
- 따라서 현재 idx까지의 문자열이 올바른 괄호 문자열인지 확인한다.
- 올바른 괄호 문자열이면
- newString에 더해준다.
- 이후 idx 뒷 부분(v부분)을 잘라서 재귀를 돌린다.
- 아닌 경우
- "("를 더해주고
- idx 뒷 부분(v부분)을 잘라서 재귀를 돌린다.
- 이후 ")"를 더해준 다음 0부터 idx까지의 부분(u부분)을 다시 자른다.
- u부분의 앞 뒤를 문자를 제거한다.
- u부분의 나머지 문자열을 전부 뒤집는다.
- 올바른 괄호 문자열이면
- 따라서 현재 idx까지의 문자열이 올바른 괄호 문자열인지 확인한다.
- 재귀가 끝나고 newString을 반환하면 끝!
느낀점
- 오랜만에 다시 푸는데 오래 걸리는 것을 봐서는 천천히 접근을 할 필요가 있다.
- 다시 풀었다고 자만하지 말고 여러 번 다시 풀어 보자.
'알고리즘 > 풀었지만 다시 보기' 카테고리의 다른 글
프로그래머스 [Lv. 2] 다음 큰 숫자 {언어 : Python} (0) | 2024.11.22 |
---|---|
프로그래머스 [Lv. 2] 구명보트 {언어 : Python} (0) | 2024.11.19 |
프로그래머스 [Lv. 2] 빛의 경로 사이클 {언어 : Python} (0) | 2024.11.17 |
프로그래머스 [Lv. 2] 마법의 엘리베이터 {언어 : Python} [백트래킹] (0) | 2024.11.16 |
프로그래머스 [Lv. 2] 시소 짝꿍 {언어 : Java} (1) | 2024.11.15 |