😊 #17 프로그래머스 - 가장 가까운 같은 글자(Level 1)

[문제]

출처 : https://school.programmers.co.kr

---

[해설]

- 상당히 지저분하게 풀었다. 뭐 어쨌든 답은 맞췄으니까

- 문제가 약간 선택 정렬의 느낌이 들어서 그거랑 비스무리하게 풀었다.

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];
        for(int i = 0; i < s.length(); i++) {
            if(i == 0) {
                answer[0] = -1;
            } else {
                String tmp = s.substring(0, i);
                String str = String.valueOf(s.charAt(i));
                if(tmp.indexOf(str) == -1) {
                    answer[i] = -1;
                } else {
                    int count = 1;
                    for(int j = (tmp.length() - 1); j > -1; j--) {
                        String str2 = String.valueOf(tmp.charAt(j));
                        if(str2.equals(str)) {
                            answer[i] = count;
                            break;
                        }
                        count++;
                    }
                }
            }
        }
        return answer;
    }
}

- 하지만 성능은 역시 꽝이다.

---

- 다른 사람의 풀이를 봐보자(lastIndexOf 개념을 사용했다.)

class Solution {
    public int[] solution(String str) {
        int[] result = new int[str.length()];

        for(int i = 0; i < str.length() ; i++) {
            String subStr = str.substring(0, i);
            String tmpStr = String.valueOf(str.charAt(i));
            if(subStr.indexOf(tmpStr) == -1) {
                result[i] = -1;
            } else {
                result[i] = i - subStr.lastIndexOf(tmpStr);
            }
        }
        return result;
    }
}

 

1. 왜 result[i] = i - subStr.lastIndexOf(tmpStr) 이러냐?

String s = "banana";

- 위의 코드의 for 문 실행 중 (i = 3)일 때 각 변수의 값을 아래와 같다.

String subStr = str.substring(0, 3);  -->  subStr = "ban";
String tmpStr = String.valueOf(str.charAt(3));  -->  tmpStr = "a";
result[i] = i - subStr.lastIndexOf(tmpStr);  -->  result[3] = 3 - 1 = 2;

1-1. 꼭 i - 을 해야하나?

- 안 하면 아래처럼 된다.

(i = 3)

String subStr = str.substring(0, 3);  -->  subStr = "ban";
String tmpStr = String.valueOf(str.charAt(3));  -->  tmpStr = "a";
result[i] = subStr.lastIndexOf(tmpStr);  -->  result[3] = 1;

- 실제 result[3] = 2 가 돼야한다.

(i = 5)

String subStr = str.substring(0, 5);  -->  subStr = "banan";
String tmpStr = String.valueOf(str.charAt(5));  -->  tmpStr = "a";
result[i] = subStr.lastIndexOf(tmpStr);  -->  result[5] = 3;

- 실제 result[5] = 2 가 돼야한다.

- 아래 그림의 논리 때문에 result[i] = i - subStr.lastIndexOf(tmpStr)를 해야한다고 생각하면 된다.

 

2023.02.19 - [코딩테스트] - 😊 #13 프로그래머스 - 숫자 찾기 / indexOf를 알아보자

😊 #13 프로그래머스 - 숫자 찾기 / indexOf를 알아보자

 

cf) 신의 영역에는 아래 같은 풀이가 있었다. 어떻게 이런 생각을 하지?

- 나도 map을 이용할까 생각은 하긴 했는데... 이런건 상상도 못 했다.

import java.util.*;

class Solution {
    public int[] solution(String s) {
        int[] answer = new int[s.length()];
        HashMap<Character,Integer> map = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            answer[i] = i - map.getOrDefault(ch, i + 1);
            map.put(ch,i);
        }
        return answer;
    }
}

필요한 리소스 자체가 다르다.