24-05-25 알고리즘 문제 풀이

오늘은 근 몇주간 많이 하지 못했던 CS 공부를 해보는 시간을 가졌다. 계속 꾸준히 해야하는데 스프링을 새로 학습해야했고 과제도 있어서 많이 하지는 못했었다. 다음주에 프로젝트가 시작되도 매일 조금씩은 할 수 있도록 노력해봐야겠다.

 

오늘은 알고리즘관련 공부한 내용과 문제를 푼 과정을 정리해보았다.

 

1. 알고리즘 문제 풀이

1-1. 풀어본 문제

leetcode에 있는 '20. Valid Parentheses' 문제를 풀어보았다.

 

[문제]

 

'(', ')', '{', '}', '[' 및 ']' 문자만 포함된 문자열 s가 주어졌을 때, 문자열이 유효한지 판단하세요

 

문자열은 다음과 같은 경우에 유효합니다

1. 열린 괄호는 같은 유형의 괄호로 닫아야합니다
2. 열린 괄호는 올바른 순서로 닫아야합니다
3. 모든 닫는 괄호는 여는 괄호와 같은 유형의 괄호이어야합니다

 

- 예시 1

입력: s = "()"

출력: true

 

- 예시 2

입력: s = "(){[]{}"

출력: true

 

- 예시 3

입력: s = "(]"

출력: false

 

- 제한 사항

• 1 <= s.length <= 10000
• s는 오직 '()[]{}'로만 이루어져 있다

1-2. 문제 풀이 방법

스택과 큐가 어떤 자료형인지는 알고있었지만 알고리즘 풀이를 할 때 어떻게 사용해야하는지를 잘 몰라서 그 부분부터 공부를 해보았다.

 

자바에는 Stack이라는 스택 자료형을 지원한다. 하지만 이 자료형은 읽기 작업도 동시에 한 번밖에 수행할 수 없는 자료형이라 성능 상의 문제가 있다. 따라서 Stack보다는 Deque 자료형을 사용하는 것이 좋다고한다.

 

스택이 필요할때 Deque의 구현체인 ArrayDeque를 이용하면 된다. ArrayDeque는 쓰레드 안전하지 않기 때문에 만약 쓰레드 안전이 필요한 경우에 다른 자료형을 사용하면 된다고한다. Stack이 아니라 LinkedBlockingDeque나 ConcurreuntLinkedDeque같은 자료형을 사용하면 된다고 하니 기억해두어야겠다.

 

코틀린에서 ArrayDeque를 사용하는 방법은 두 가지가 있다.

 

그냥 자바의 ArrayDeque를 가져다가 쓰는 방법이 있다. push()로 목록에 값을 넣어줄 수 있고, pop()으로 마지막에 들어있는 값을 하나씩 꺼낼 수 있으며, isEmpty()로 목록이 비어있는지 확인할 수 있다.

import java.util.Deque
import java.util.ArrayDeque

fun main() {

    val stack: Deque<Char> = ArrayDeque()

    stack.push('A')

    println(stack.pop()) // A
    println(stack.isEmpty()) // true

}

아니면 그냥 코틀린에 있는 ArrayDeque를 이용할 수 있다.

 

push(), pop()같은 함수가 없다. add()로 목록에 값을 더할 수 있고, removeLast()로 목록의 가장 마지막 값을 없애고 반환받을 수 있으며, isEmpty()로 목록이 비어있는지 확인할 수 있다.

fun main() {

    val stack = ArrayDeque<Char>()

    stack.add('A')

    println(stack.removeLast()) // A
    println(stack.isEmpty()) // true

}

 

이제 문제로 다시 돌아와서 문제를 풀어보면 된다. 문제가 어렵지 않기 때문에 쉽게 풀 수 있었다. 

 

문자열의 문자들을 앞에서부터 하나하나 반복하면서 여는 괄호이면 스택에 더하고 닫는 괄호이면 스택에 들어있는 여는 괄호와 맞는지 확인하면 된다. 또한 닫는 괄호일 때 스택이 비어있는지 여부도 확인해야한다.

 

모든 작업이 끝났는데 스택이 비어있지 않다면 여는 괄호만 들어있다는 의미이니 false를 반환한다.

 

위의 작업들을 수행하기 위해 짠 코드는 아래와 같다.

class Solution {
    fun isValid(s: String): Boolean {
        // 스택을 선언한다
        val stack = ArrayDeque<Char>()
        // 맵에 괄호들을 저장해둔다
        val map = mapOf(')' to '(', '}' to '{', ']' to '[')

        for (i in s.indices) {
            // 여는 괄호가 들어오면 스택에 더해준다
            if(!map.containsKey(s[i])) {
                stack.add(s[i])
            // 닫히는 괄호 차례에 스택이 비어있으면 false를 반환한다.
            // 닫히는 괄호가 들어왔을때는 여는 괄호와 맞는지 확인한다
            } else if (stack.isEmpty() || map[s[i]] != stack.removeLast()) {
                return false
            }
        }
        // 문자열 전체 반복이 끝났는데 스택이 비어있지 않다면 false를 반환한다
        return stack.size == 0
    }
}

위와 같이 코드를 작성하니 답안으로 잘 통과가 된다.

 

스택 자료구조에 대한 기초적인 문제는 잘 풀 수 있었다. 앞으로는 스택과 큐에 대해 잘 이해하고 익숙해지도록 연습을 더 해야할 것 같다.

 

 

2. 오늘 배운 것

- 스택과 큐 자료형을 어떻게 코틀린에서 효율적으로 사용할 수 있는지 알게되었다.

- 오늘은 네트워크에 대해 조금 더 공부해보았다. 스프링 학습하느라 CS 공부를 조금 못했었는데 이제 다시 매일 조금씩 하려고한다.