[LeetCode] 1629. Slowest Key

문제 출처: https://leetcode.com/problems/slowest-key/

Slowest Key - LeetCode

---

문제

새롭게 설계된 키패드를 테스트하였다. 테스터는 한 번에 하나씩 $n$개의 키를 순차적으로 눌렀다.

 

길이 n의 문자열 $keysPressed$와 $releaseTimes$가 주어진다, $keysPressed[i]$는 테스팅에서 $i^{th}$ 눌린 키를 의미하고 $releaseTimes[i]$는 $i^{th}$번째 키가 눌려진 시간을 의미한다. 두 배열 모두 0-기반 인덱싱 되어 있으며, $0^{th}$ 키는 0 시간에 눌렸고, 모든 하위 키는 이전 키가 해제된 그 시간에 정확히 눌려졌음을 가정한다.

 

테스터는 키패드에서 입력되는데 가장 오래 걸린 키를 알고 싶어한다. $i^{th}$ 키 입력은 $releaseTimes[i] - releaseTimes[i-1]$의 입력 시간을 갖는다, 그리고 $0^{th}$ 키 입력은 $releaseTimes[0]$의 입력 시간을 갖는다.

 

테스트하는 동안에 동일한 키가 여러 번 눌렸을 수 있고, 같은 키가 여러 번 눌렸다고 하더라도 입력 시간은 제각각일 수 있다.

 

키패드에서 입력 시간이 가장 긴 키를 반환하라. 만약 키패드에서 입력 시간이 가장 큰 키가 여러 개 존재한다면, 알파벳 순으로 가장 큰 키를 반환하라. 

예제

Input: releaseTimes = [9,29,49,50], keysPressed = "cbcd"
Output: "c"

Explanation: The keypresses were as follows:
Keypress for 'c' had a duration of 9 (pressed at time 0 and released at time 9).
Keypress for 'b' had a duration of 29 - 9 = 20 (pressed at time 9 right after the release of the previous character and released at time 29).
Keypress for 'c' had a duration of 49 - 29 = 20 (pressed at time 29 right after the release of the previous character and released at time 49).
Keypress for 'd' had a duration of 50 - 49 = 1 (pressed at time 49 right after the release of the previous character and released at time 50).
The longest of these was the keypress for 'b' and the second keypress for 'c', both with duration 20.
'c' is lexicographically larger than 'b', so the answer is 'c'.

Input: releaseTimes = [12,23,36,46,62], keysPressed = "spuda"
Output: "a"

Explanation: The keypresses were as follows:
Keypress for 's' had a duration of 12.
Keypress for 'p' had a duration of 23 - 12 = 11.
Keypress for 'u' had a duration of 36 - 23 = 13.
Keypress for 'd' had a duration of 46 - 36 = 10.
Keypress for 'a' had a duration of 62 - 46 = 16.
The longest of these was the keypress for 'a' with duration 16.

---

풀이

각 키의 입력 시간을 알기 위해서 단순 반복을 이용하여, $durations[i] = releaseTime[i] - releaseTime[i-1]$의 값을 구한다.

 

구해진 $durations$에서 가장 큰 값을 지닌 인덱스를 찾아 $keyPressed$에서 해당 위치의 값을 반환하는 것으로 문제를 해결할 수 있다. 다만, 동일한 값이 여러 개 존재할 경우, 각각의 알파벳을 비교하여 가장 큰 값을 출력해야 한다는 것을 인지하고 있어야 한다.

 

시간 복잡도는 $O(n)$이다. 각 키의 $duration$을 구하기 위해서 $releaseTimes$를 순차적으로 찾아가야 하기 때문이다.

var slowestKey = function(releaseTimes, keysPressed) {
    let maxDuration = releaseTimes[0];
    let index = 0;
    
    for (let i = 1; i < releaseTimes.length; i++) {
        const duration = releaseTimes[i] - releaseTimes[i-1];
        if (maxDuration < duration) {
            maxDuration = duration;
            index = i;
        } else if (maxDuration == duration && keysPressed[index] < keysPressed[i]) {
            index = i;
        }
    }
    
    return keysPressed[index];
};

 

Github: 1629.js

GitHub - opwe37/Algorithm-Study