[프로그래머스] 가장 가까운 같은 글자 - 자바(Java) Lv. 1

https://school.programmers.co.kr/learn/courses/30/lessons/142086

프로그래머스

문제 설명

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.

예를 들어, s="banana"라고 할 때,  각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

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

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

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

제한사항

• 1 ≤ s의 길이 ≤ 10,000
  • s은 영어 소문자로만 이루어져 있습니다.

입출력 예

s result

"banana"	[-1, -1, -1, 2, 2, 2]
"foobar"	[-1, -1, 1, -1, -1, -1]

---

설계

자신과 같은 글자가 몇 칸 앞에 있는가?

파이썬은 휘뚜루마뚜루 해야하는데 자바는 그렇지 않아서 잠시 뇌를 자바로 바꾸느라 시간이 좀 걸렸다.

reverse로 뒤집어두고 indexOf로 찾아가야 하나 싶었는데 다행히 lastIndexOf라는 뒤에서부터 찾아주는 함수가 존재했다.

1. for문으로 String 역순으로 검사
2. 현재 위치에서 얼마나 앞에서 나랑 같은 문자가 나오는지 lastIndexOf로 검사해주기
3. 있으면 발견된 위치에서 지금 위치i를 빼준 값을, 없으면 -1을 answer에 넣어준다.

 

구현 코드

class Solution {
    public int[] solution(String s) {
        // 문자 길이 만큼 배열 초기화
        int[] answer = new int[s.length()];
        char now;
        int findIndex;
        // 1. 문자열을 역순으로 탐색한다. 
        for(int i = s.length()-1; i>=0; i--){
            // 2. 문자가 등장하는 인덱스를 찾아 얼마나 앞에 있는지 계산해준다
       
            // 현재 인덱스의 문자를 now에 넣는다.
            now = s.charAt(i);
            
            // 현재 문자가 앞에서 어느 인덱스에서 나왔는지 찾는다
            findIndex = s.lastIndexOf(now, i-1);
            
            if(findIndex == -1){
                // 없는 경우 -1을 리턴
                answer[i] = -1;
            }else{
                // 있는 경우 얼마나 앞에 있는지 계산하여 answer배열에 넣는다.
                answer[i] = i - findIndex;
            }
        }
        return answer;
    }
}

• 시간 복잡도: O(n^2)
• n은 입력 문자열 s의 길이, for문 1번과 lastIndexOf 1번으로 n^2
  
  

포인트 함수

① charAt()

• Java 문자열에서 특정 인덱스에 위치한 문자를 반환하는 메소드
• 문자열의 각 문자에 대해 인덱스를 사용하여 해당 위치에 있는 문자를 가져올 수 있음

charAt() 함수의 기본적인 사용법

char charAt(int index)
// index는 가져올 문자의 위치를 나타내는 정수값

String str = "Hello";
char thirdChar = str.charAt(2); // 세 번째 문자 'l'을 가져옴
System.out.println(thirdChar); // 출력: l

주의

charAt() 함수를 사용하여 문자열에서 문자를 가져올 때 주의할 점은 문자열의 길이를 벗어나는 인덱스를 사용하면 **StringIndexOutOfBoundsException**이 발생할 수 있음. 따라서 항상 문자열의 길이를 확인하고 유효한 인덱스를 사용해야 함.

② indexOf() 및 lastIndexOf()

• indexOf() 및 lastIndexOf() 함수들은 Java 문자열에서 특정 문자나 문자열이 처음 등장하는 인덱스를 찾는 데 사용됩니다. 각각의 함수는 문자열에서 검색을 시작하는 방향에 따라 다르게 작동합니다.

indexOf()

• 문자열에서 특정 문자나 문자열이 처음으로 등장하는 위치의 인덱스를 반환합니다.

int indexOf(int ch)
int indexOf(int ch, int fromIndex)
int indexOf(String str)
int indexOf(String str, int fromIndex)

• **ch**는 찾을 문자의 코드 포인트를 나타내며, **fromIndex**는 검색을 시작할 인덱스를 나타냅니다. **fromIndex**가 음수이면 검색은 문자열의 처음부터 시작됩니다. 찾는 문자나 문자열이 없으면 **-1**을 반환합니다.

String str = "Hello World";
int index1 = str.indexOf('o'); // 문자 'o'의 첫 등장 위치를 찾음
int index2 = str.indexOf("World"); // 문자열 "World"의 첫 등장 위치를 찾음
System.out.println(index1); // 출력: 4
System.out.println(index2); // 출력: 6

lastIndexOf()

• 문자열에서 특정 문자나 문자열이 마지막으로 등장하는 위치의 인덱스를 반환합니다.

int lastIndexOf(int ch)
int lastIndexOf(int ch, int fromIndex)
int lastIndexOf(String str)
int lastIndexOf(String str, int fromIndex)

• **ch**는 찾을 문자의 코드 포인트를 나타내며, **fromIndex**는 검색을 시작할 인덱스를 나타냅니다. **fromIndex**가 음수이면 검색은 문자열의 끝에서부터 시작됩니다. 찾는 문자나 문자열이 없으면 **-1**을 반환합니다.

String str = "Hello World";
int index1 = str.lastIndexOf('o'); // 문자 'o'의 마지막 등장 위치를 찾음
int index2 = str.lastIndexOf("World"); // 문자열 "World"의 마지막 등장 위치를 찾음
System.out.println(index1); // 출력: 7
System.out.println(index2); // 출력: 6

• lastIndexOf() 함수는 주로 문자열에서 뒤에서부터 특정 문자나 문자열을 찾을 때 사용됩니다.