24-06-17 알고리즘 문제 풀이

오늘은 내일까지인 프로젝트를 최종 마무리를 하는 시간을 가졌다. 그 과정에서 알지 못했던 버그들도 발견이 되고 수정하는 시간도 있었다.

 

또한 여태까지 해왔던 것들을 하나하나 정리하는 작업도 하였다. 어떠한 것을 했는지 어떤 고민을 했었는지 어떤 점을 배웠는지 잘 정리하는 것 역시 공부도 되고 중요한 것 같다.

 

프로젝트 시작 할 때는 이것저것 해보고 싶은게 많이 생기는데 마감기한이라는 것이 있기 때문에 하고 싶었던 걸 모두 하지는 못하게 되는 것 같다. 마감기한에 맞추어 스코프를 적절히 가져가는 것 또한 중요한 것 같다.

 

여기에는 오늘 하루를 마감하기 직전에 풀어본 알고리즘 문제 풀이 하나를 정리해본다.

1. 알고리즘 문제 풀이

오늘은 leetcode에 있는 '771. Jewels and Stones' 문제를 풀어보았다.

1-1. 풀어본 문제

[문제]

 

보석에 속하는 원석의 종류를 나타내는 문자열 jewels와 소유한 원석들을 나타내는 문자열 stones가 주어진다. stones의 각각의 문자들은 소유하고 있는 원석의 종류를 나타낸다. 가지고 있는 원석들 중 몇 개의 원석이 보석인지 구하여라.

 

문자는 대소문자를 구분한다. 따라서 'a'와 'A'는 다른 종류의 원석으로 간주된다.

 

- 예시 1

입력: jewels = "aA", stones = "aAAbbbb"

출력: 3

 

- 예시 2

입력: jewels = "z", stones = "ZZ"

출력: 0

 

- 제한 사항

• $1 {\;}{\leq}{\;}  jewels.length, stones.length {\;}{ \leq}{\;} 50$
• jewels 와 stones는 오직 영문자로만 이루어져있다.
• jewels의 모든 문자는 유일하다.(서로 다른 문자로만 이루어져있다.)

 

1-2. 문제 풀이

굉장히 간단한 문제이기 때문에 쉽게 풀 수 있었다.

 

jewels에 있는 보석들을 자료구조를 이용해 잘 담아두고 stones에 있는 원석들이 여기에 속해있는지 여부를 판단해 카운트를 하나씩 증가시키기만 하면 되는 간단한 문제이다.

 

다양한 자료형을 이용할 수 있었는데 jewels는 어차피 중복이 불가능하고 서로 다른 문자로만 이루어져있기 때문에 set을 이용해보기로 했다.

 

jewels에 있는 보석들을 반복문을 이용해 하나하나 set에 저장해주고, stones에 있는 원석들이 이 set에 들어있는지를 판단해 들어있다면 카운트를 하나 증가시키는 방식으로 코드를 작성했다.

 

답안으로 통과된 코드는 아래와 같다.

class Solution {
    fun numJewelsInStones(jewels: String, stones: String): Int {
        var answer = 0
        val set = mutableSetOf<Char>()

        for (jewel in jewels) 
        set.add(jewel)

        for (stone in stones) 
        if(set.contains(stone)) answer++

        return answer
    }
}

문제는 간단히 풀 수 있었지만 이 문제는 자료구조를 어떻게 선택하느냐에 따라 다양한 답이 있을 수 있기 때문에 한 번 여러 자료형을 이용해 답을 작성해 실행 시간을 측정해보았다.

 

CharArray를 이용한 답안

class Solution {
    fun numJewelsInStones(jewels: String, stones: String): Int {
        var answer = 0
        val charArray = jewels.toCharArray()

        for (stone in stones) 
        if(charArray.contains(stone)) answer++

        return answer
    }
}

jewels의 String을 그대로 이용한 답안

class Solution {
    fun numJewelsInStones(jewels: String, stones: String): Int {
        var answer = 0

        for (stone in stones) 
        if(jewels.contains(stone)) answer++

        return answer
    }
}

 

MutableList를 이용한 답안

class Solution {
    fun numJewelsInStones(jewels: String, stones: String): Int {
        var answer = 0
        val list = mutableListOf<Char>()

        for (jewel in jewels) 
        set.add(jewel)

        for (stone in stones) 
        if(list.contains(stone)) answer++

        return answer
    }
}

 

이렇게 여러 답안을 작성해보았고 모두 답안으로 잘 통과되었다.

 

실행속도는 MutableSet > MutableList > CharArray > String 순으로 빨랐다.

 

위와 같은 문제처럼 특정 컬렉션이 특정 요소를 포함하는지 여부를 확인하는데에는 Set이 빠르다는 것을 알게되었다.

 

자료구조에 대해서 더 자세히 공부해 어떤 상황에서 어떤 자료구조를 사용하는 것이 유리한지에 대해서도 자세히 공부해보아야겠다.

 

2. 오늘 배운 것

- 팀 프로젝트 막바지에 이르러 그간 해온 것을 정리해보았다. 생각보다 만족스러운 부분이 많았던 것 같아 놀랍기도 했다.

- 좋은 협업 방식에 대해서 계속 고민하게 되는 것 같다. 이번 조에서의 협업은 꽤 만족스러웠기 때문에 여기서 배웠던 점을 다른 곳에서도 적용할 수 있도록 노력해봐야겠다.