코딩테스트 스택 기본 문제

1. 괄호 닫기

문제

올바른 괄호: '('로 열렸을 때 ')'로 닫히는 괄호

'(' 또는 ')'로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 반환하고 올바르지 않은 괄호면 false를 반환하는 함수 만들기

 

제약 조건

• 문자열 s의 길이: 100,000 이하의 자연수
• 문자열 s는 '(' 또는 ')'로만 구성

풀이

*)는 )가 나오기 바로 전의 가장 가까운(최근) 열린 괄호와 상쇄된다.

최근 -> 스택

 

1. ( 나오면 push
2. ) 나오면 ( pop -> 한 쌍 상쇄
3. 마지막 문자까지 반복해서 스택에 열린 괄호가 남아있으면 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진수로 표현하는 과정

1. 10진수 N을 2로 나눈 나머지(%2 연산값)를 저장하고 N을 2로 나눈다
2. 몫이 0이 아니라면 나머지를 버리고 다시 1을 수행한다
3. 모든 과정이 끝나고 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)