1. 괄호 닫기
문제
올바른 괄호: '('로 열렸을 때 ')'로 닫히는 괄호
'(' 또는 ')'로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 반환하고 올바르지 않은 괄호면 false를 반환하는 함수 만들기
제약 조건
- 문자열 s의 길이: 100,000 이하의 자연수
- 문자열 s는 '(' 또는 ')'로만 구성
풀이
*)는 )가 나오기 바로 전의 가장 가까운(최근) 열린 괄호와 상쇄된다.
최근 -> 스택
- ( 나오면 push
- ) 나오면 ( pop -> 한 쌍 상쇄
- 마지막 문자까지 반복해서 스택에 열린 괄호가 남아있으면 false
//스택 생성
ArrayDeque<Character> stack = new ArrayDeque<>();
//문자열 s를 char 배열로 변환
char[] a = s.toCharArray();
//char 배열을 순환하는 forEach문
for(char c : a){
//여는 괄호일 경우
if(c == '('){
stack.push;
}
//닫는 괄호일 경우
else{
//닫는 괄호이고 스택이 empty인 경우
if(stack.isEmpty())
return false;
//닫는 괄호이고 스택이 empty가 아닌 경우
else
stack.pop();
}
}
return stack.isEmpty();
시간 복잡도
s 순회 -> O(N)
2. 10진수를 2진수로 변환하기
문제
10진수를 입력받아 2진수로 변환해 반환하는 함수
제약 조건
decimal은 1 이상 10억 미만의 자연수
문제 분석
10진수를 2진수로 표현하는 과정
- 10진수 N을 2로 나눈 나머지(%2 연산값)를 저장하고 N을 2로 나눈다
- 몫이 0이 아니라면 나머지를 버리고 다시 1을 수행한다
- 모든 과정이 끝나고 1에서 저장한 수를 뒤부터 순서대로 가져와 붙인다
뒤부터 순서대로 -> 나머지를 스택에 넣어놓고 하나씩 꺼내기
코드
public static String solution(int decimal){
Stack<Integer> stack = new Stack<>();
while(decimal > 0){
//나머지 연산
int remainder = decimal % 2;
stack.push(remainder);
//나누기 연산
decimal /= 2;
}
StringBuilder sb = new StringBuilder();
//스택이 비어있지 않을 동안 반복
while(!stack.isEmpty()){
//스택에서 pop연산하고 StringBuilder에 더하기
sb.append(stack.pop());
}
}
시간 복잡도
N이 1이 될 때까지 2로 계속 나눔 -> O(logN)
'코딩테스트' 카테고리의 다른 글
코딩테스트 스택 기초 (0) | 2024.04.24 |
---|---|
코딩테스트 배열 관련 함수② (0) | 2024.04.23 |
코딩테스트 배열 관련 함수 (0) | 2024.04.22 |
자바 코딩테스트 메서드 기초: 구현 노하우 (0) | 2024.04.18 |
자바 코딩테스트 메서드 기초: 람다식 (0) | 2024.04.18 |