괄호 검사 문제
1. 열린 괄호들은 모두 같은 타입의 닫는 괄호로 닫혀야 함
2. 열린 괄호들은 모두 옳은 순서로 닫혀야 함
그리고 Java에서는 스택을 쓰는 문제였던 걸로 기억한다.
주어진 str을 읽으면서 스택에 여는괄호를 넣고 가다가 닫는괄호를 만나면 짝 맞는지 체크하고 pop하는 방향이 좋겠음
Java
import java.util.*;
class Solution {
public boolean isValid(String s) {
int length = s.length();
if(length % 2 == 1) return false; // 길이가 홀수면 당연히 짝이 맞지 않는다
Stack<Character> opens = new Stack<>();
for(int i = 0; i<length; i++){
Character thisChar = s.charAt(i);
if(isOpen(thisChar)) opens.push(thisChar);
else { // 닫는 괄호를 만났을 때
try{
if(isPair(opens.peek(), thisChar)) opens.pop();
else return false; // 짝이 맞지 않는다
} catch(Exception e){ // 닫는 괄호만 있는 경우. (스택에 아무것도 없음)
e.printStackTrace();
return false;
}
}
}
if(!opens.isEmpty()) return false; // 여는 괄호가 남은 경우
return true;
}
public boolean isOpen(char c){ // 여는 괄호인가?
if(c == '(' || c == '[' || c == '{') return true;
else return false;
}
public boolean isPair(char open, char close){ // 짝이 맞는가?
switch(open){
case '(' : {
if(close == ')') return true;
break;
}
case '{' : {
if(close == '}') return true;
break;
}
case '[' : {
if(close == ']') return true;
break;
}
}
return false;
}
}코드 좀 더러운데 자바는 이렇게 짰다
TypeScript
스택에 넣고 가다가 pop한다 ? 라서
스택을 만들어야 하나? 했는데 javascript 배열에서는 자체적으로 pop() 메서드를 지원한다.
짱이잖아?
그래서 걍 배열로 했다.
TS는 IDE로 짜고 결과를 어떻게 돌려봐야 할지 모르겠어서
일단 계산 결과를 리턴하는 컴포넌트를 하나 만들었다.
그리고 아래처럼 불러와서 사용했다.
console.log로 찍어봐도 됐겠지만 디버깅할 때 콘솔을 사용할 거기 때문에
답안 확인과 디버깅 콘솔을 물리적으로 분리하고 싶어서 선택한 방법이다.
코드 수정해서 저장할 때마다 자동으로 실행(렌더링)돼서 이쪽이 더 편리하기도 하고 ㅋㅋ
풀이는 다음과 같이 작성했다.
그랬더니 결과가
허허
하지만 배열만 가지고 놀았던 걸로 만족할 순 없지
다음날 타입스크립트로 야매 스택을 만들어 보았다
야매라기에는 코드 양이 고봉밥인데
내가 아직 코드를 드럽게 짜서 어쩔 수 없음 ... 짜다 보면 고쳐지겠지
class Node {
val: string | undefined; // 제시되는 자료형 타입에 맞추기
next: Node | null;
constructor(val?: string) {
this.val = val;
this.next = null;
}
}
class Stack {
btm: Node;
second: Node; // curr 직전의 두 번째 노드
curr: Node; // 가장 위에 있는 노드
constructor() {
this.btm = new Node();
this.curr = this.btm;
this.second = this.btm;
}
add = (node: Node): void => {
this.second = this.curr;
this.curr.next = node;
this.curr = node;
console.log('add =============');
console.log(this.toArray());
};
remove = (idx: number): void => {
// 인덱스는 1부터 시작한다. n번째 요소를 삭제하므로 유의
// 인덱스로 삭제하기
let curr: Node = this.btm;
let before: Node = this.btm;
for (let i: number = 0; i <= idx; i++) {
if (i === idx - 1) before = curr;
if (i === idx) before.next = curr.next;
if (curr.next) curr = curr.next;
// 마지막 인덱스를 삭제하는 경우?
}
};
peek = (): string => {
// 제시된 자료형에 맞추어서
if (this.curr.val) return this.curr.val;
else throw new Error('NullPointerException'); // 새로운 Error 객체 생성
};
get = (idx: number): Node => {
// 인덱스로 노드 찾기
let curr: Node = this.btm;
let count: number = 0;
for (let i = 0; i <= idx; i++) {
count++;
if (count === idx) break;
if (curr.next) curr = curr.next;
}
return curr;
};
pop = (): string => {
// 제시된 자료형에 맞추어서
const del: Node = this.curr; // 지워질 노드
if (this.second) this.second.next = null;
this.curr = this.second;
this.second = this.get(this.size());
console.log('pop =============');
console.log(this.toArray());
if (del.val) return del.val;
else throw new Error('StackUnderflow');
};
size = (): number => {
let curr: Node = this.btm;
let count: number = 0;
while (curr.next !== null) {
count++;
curr = curr.next;
}
return count;
// or toArray() 실행 후 length 리턴
};
toArray = (): string[] => {
// 제시된 자료형
let curr: Node = this.btm;
const result: string[] = []; // 제시된 자료형
while (curr.next !== null) {
// 마지막 노드 전까지만 실행됨
if (typeof curr.val === 'string')
// 제시된 자료형
result.push(curr.val);
curr = curr.next;
}
if (typeof curr.val === 'string') result.push(curr.val); // 마지막 노드까지 추가
return result;
};
}
// ====================== stack
const isOpen = (c: string): boolean => {
const opens: string[] = ['(', '[', '{'];
return opens.includes(c);
};
const isPair = (open: string, close: string): boolean => {
const opens: string[] = ['(', '[', '{']; // 같은 종류 괄호를 같은 순서로 배치
const closes: string[] = [')', ']', '}'];
const oIdx: number = opens.findIndex((each: string) => each === open);
const cIdx: number = closes.findIndex((each: string) => each === close);
return oIdx === cIdx; // 인덱스가 같으면 짝이 맞는 것이다.
};
테스트
아직 제너릭을 쓸 줄 몰라서 타입을 일단 고정해서 받았는데
다음에는 제너릭을 쓰는 방향으로 구현해 봐야겠음
그리고 뭔가 pop이 찜찜하다 연산을 너무 많이 하는데
양방향 링크드리스트로 구현했어야 했나
접은글 안에 있는 게 만들어둔 스택이고
이걸 활용해서 문제풀이를 해보겠음
된다. 되긴 했는데
대박 ;
---
https://nogotit.tistory.com/entry/TypeScript-Stack-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0
[TypeScript] Stack 구현하기
어제 문제풀이 참고https://nogotit.tistory.com/entry/Grind75-TypeScript-Java-2-Valid-Parentheses [Grind75 / TypeScript, Java] #2 Valid Parentheses괄호 검사 문제1. 열린 괄호들은 모두 같은 타입의 닫는 괄호로 닫혀야 함2.
nogotit.tistory.com
이 포스트에서 구현한 스택을 가지고 해 봤다
좀 더 빨라지지 않을까? 하는 기대를 가지고
으흠 뿌듯하군
그리고 처음에 만든 스택이 왜 느렸는지도 알아냈다
내가 add / pop 연산 할 때마다 toArray() 를 하게 만들어놔서 그런 거였음 ;
출력으로 채점을 하는 게 아니다보니 포함시켜 놔도 오답 처리되지 않아서
계속 포함시킨 상태로 돌렸다 .. 그러니까 느리지
그치만 처음에 만든 스택이 비효율적인 구조였던 건 맞았는데
단방향 링크드리스트를 썼기 때문이다. 그래서 pop() 연산을 할 때마다 이전 노드의 주소를 가지고 있지 않아서
get(index) 연산을 수행한 후에(모든 스택 요소를 한 번 훑고) 가장 마지막에 있는 요소로 맨 위 요소를 업데이트해야 했다.
그래서 출력문을 빼고 실행하더라도 첫 번째로 만든 스택은
좀 느리다.
'미분류 > 취준' 카테고리의 다른 글
| 또 근황 (2) | 2025.04.06 |
|---|---|
| 근황 (0) | 2025.03.17 |
| [PGMRS / Java] 개인정보 수집 유효기간 (2) | 2024.12.25 |
| [Grind75 / TypeScript, Java] #1 Two Sum (2) | 2024.10.22 |
| 알고리즘 공부할 것 리스트 (0) | 2024.10.16 |
댓글