티스토리 뷰
Problem
You are given a string s of lowercase English letters and an integer array shifts of the same length.
Call the shift() of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a').
For example, shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'.
Now for each shifts[i] = x, we want to shift the first i + 1 letters of s, x times.
Return the final string after all such shifts to s are applied.
Example 1:
Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.
Example 2:
Input: s = "aaa", shifts = [1,2,3]
Output: "gfd"
Constraints:
- 1 <= s.length <= 10^5
- s consists of lowercase English letters.
- shifts.length == s.length
- 0 <= shifts[i] <= 10^9
Solution
주어진 문자열을 주어진 배열의 인덱스에 해당하는 값만큼 shift 시켜 반환하는 문제로 Medium 난이도 치고는 굉장히 쉬운 편입니다.
각 인덱스에 해당하는 문자열을 shift 할 때 첫 번 째 인덱스에 대해서는 첫 번 째 문자만 shift 하지만, 그 이후 인덱스에 대해서는 앞 쪽 문자까지 같이 shift 해줘야 합니다.
따라서 기존 shift 배열에 대해 실제로 shift 해야 할 횟수를 더하고 알파벳의 갯수를 나눈 나머지로 설정해주는 작업이 필요합니다.
public class Solution {
public String shiftingLetters(String s, int[] shifts) {
for (int i = shifts.length - 2; i >= 0; i--) { // (1)
shifts[i] += shifts[i + 1] % 26;
}
char[] chars = s.toCharArray();
for (int i = 0; i < shifts.length; i++) { // (2)
chars[i] += shifts[i] % 26;
if (chars[i] > 'z') { // (3)
chars[i] -= 26;
}
}
return new String(chars);
}
}
(1) shift 배열의 누적 값을 계산하여 26으로 나눈 나머지를 구함
(2) 문자열을 탐색하면서 shift 배열에 해당하는 값만큼 shift
(3) shift한 값이 알파벳 소문자 범위를 넘어가면 26을 빼줌
Test
package io.lcalmsky.leetcode.shifting_letters;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.assertAll;
import static org.junit.jupiter.api.Assertions.assertEquals;
class SolutionTest {
@Test
void givenStringAndShifts_whenShiftString_thenCorrect() {
assertAll(
() -> test("abc", new int[]{3, 5, 9}, "rpl"),
() -> test("ruu", new int[]{26, 9, 17}, "rul"),
() -> test("mkgfzkkuxownxvfvxasy", new int[]{505870226, 437526072, 266740649, 224336793, 532917782, 311122363, 567754492, 595798950, 81520022, 684110326, 137742843, 275267355, 856903962, 148291585, 919054234, 467541837, 622939912, 116899933, 983296461, 536563513}, "wqqwlcjnkphhsyvrkdod")
);
}
private void test(String S, int[] shifts, String expected) {
// when
Solution solution = new Solution();
String actual = solution.shiftingLetters(S, shifts);
// then
assertEquals(expected, actual);
}
}
'Algorithm > LeetCode' 카테고리의 다른 글
[LeetCode - Daily Challenge] 1189. Maximum Number of Balloons (0) | 2021.09.14 |
---|---|
[LeetCode - Daily Challenge] 764. Largest Plus Sign (0) | 2021.09.10 |
[LeetCode - Daily Challenge] 206. Reverse Linked List (0) | 2021.09.08 |
[LeetCode - Daily Challange] 1629. Slowest Key (0) | 2021.09.07 |
[LeetCode] 96. Unique Binary Search Trees (Java) (0) | 2021.09.03 |
- Total
- Today
- Yesterday
- 스프링 부트 회원 가입
- intellij
- Java
- 스프링 부트 튜토리얼
- leetcode
- QueryDSL
- 헥사고날 아키텍처
- Spring Boot JPA
- 함께 자라기 후기
- Spring Boot Tutorial
- proto3
- r
- @ManyToOne
- spring boot jwt
- JPA
- 스프링 데이터 jpa
- gRPC
- Spring Data JPA
- Linux
- Spring Boot
- 함께 자라기
- 스프링부트
- 스프링 부트 애플리케이션
- Jackson
- 알고리즘
- 스프링 부트
- 클린 아키텍처
- JSON
- spring boot application
- spring boot app
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |