02/16 알고리즘 공부(50) - 가장 가까운 글자

조건

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.
예를 들어, s="banana"라고 할 때,  각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

1. b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
2. a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
3. n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
4. a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
5. n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
6. a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.

따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

 

알고리즘 예상

1. 반복문을 이용해 문자의 최초 인덱스가 그 문자의 인덱스와 같으면 answer에 -1 추가
2. 다르다면 이전 인덱스와의 거리를 반환

 

초기 코드

class Solution {
    fun solution(s: String): IntArray {
        var answer: IntArray = intArrayOf()
        return answer
    }
}

 

내 코드

class Solution {
    fun solution(s: String): IntArray {
        var answer: IntArray = intArrayOf()
        for((i,c) in s.withIndex()){
            if(i == s.indexOf(c)){
                answer += -1
            }
            else{
                answer += s.reversed().indexOf(c,s.length-i) - (s.length-1-i)
            }
        }
        return answer
    }
}

이전 인덱스를 이용해야 했기 때문에 뒤집어서 생각했다.

 

다른 사람의 풀이

class Solution {
    fun solution(s: String): List<Int> {
        return s.withIndex().map { (i, c) -> s.slice(0 until i).lastIndexOf(c).let { if (it >= 0) i - it else -1 } }
    }
}

class Solution {
    fun solution(s: String): IntArray {
        val answer = IntArray(s.length) {-1}
        val checkIndex = ('a'..'z').associate { it to -1 } as HashMap

        s.forEachIndexed { i, v ->
            if (checkIndex[v]!! > -1) answer[i] = (i - checkIndex[v]!!)
            checkIndex[v] = i
        }

        return answer

    }
}

class Solution {
    fun solution(s: String): IntArray {
        var answer = MutableList(s.length) {-1}

        for ((i, c) in s.withIndex()) {
            if (i == 0) {
                continue
            }
            var count = 0
            for (j in i - 1 downTo 0) {
                count++
                if (s[j] == c) {
                    answer[i] = count
                    break
                }
            }
        }
        return answer.toIntArray()
    }
}

개선점 또는 배운점

1. 1번 풀이는 slice를 이용해 해당 인덱스의 원소가 포함되지 않는 배열을 만들어 중복검사를 하였다.
2. 2번풀이는 해시맵을 이용해 a부터 z까지의 모든 키에 -1이라는 값을 부여한 후 키에 해당하는 문자가 나오면 answer에 -1을, 해시맵의 값에 해당 문자의 인덱스를 부여하는 방법을 사용했다.
3. 3번 풀이는 index와 반복문을 이용해 count를 늘리는 방법으로 해결했다.

 

개선된 코드

class Solution {
    fun solution(s: String): List<Int> {
        return s.withIndex().map { (i, c) -> 
            s.slice(0 until i).lastIndexOf(c).let { 
                if (it >= 0) i - it else -1 } 
        }
    }
}