[알고리즘/인프런] String(문자열) #1-10. 가장 짧은 문자거리

 

인프런의 "자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비" 강좌를 수강했습니다.

C, C++, Python, Js 등 다른 언어의 강의도 있으니 본인에게 맞는 강의를 선택하시면 됩니다. 😁

https://inf.run/pCPH

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

 

 

---

Q1-10. 가장 짧은 문자거리

한 개의 문자열str과 한 개의 문자c를 입력받는다. 문자열str을 이루고 있는 각 문자가 문자 c와 떨어진 최소 거리를 구한다.

 

입력	출력
teachermode e	1 0 0 1 1 0 0 1 2 1 0

 

 

✏️ 내가 쓴 답

이 문제는 못 풀었다 ㅠㅠ

단순히 position을 출력하라는 문제였다면 쉽게 풀 수 있었을 텐데, 같은 문자 사이에 숫자가 대칭되어서.. 어떻게 해야할지 몰랐다.

position 변수를 선언하고 그림까지 그려가면서 해봤는데 어떻게 하는지 몰라 결국 풀이의 도움을 받았다.

 

반응형

👨🏻‍🏫  풀이코드

강의를 참고하여 아래와 같이 수정했다.

import java.util.Scanner;

public class Main {
    
    public int[] solution(String str, char c){
    
        int[] answer = new int[str.length()];
        int p = 1000;

        for(int i=0; i<str.length(); i++) {
            if(str.charAt(i) != c) p++;
            else p=0;
            answer[i] = p;
        }

        p = 1000;

        for(int i=str.length()-1; i>=0; i--){
            if(str.charAt(i) != c) {
                p++;
                if(answer[i] > p) answer[i] = p;
            } else {
                p=0;
            }
        }

        return answer;
    }

    public static void main(String[] args) {
        Main main = new Main();

        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        char c = sc.next().charAt(0);
        for(int a : main.solution(str, c)){
            System.out.print(a + " ");
        }
        
    }
}

solution() 메소드로 문자열과 문자를 넘겨준다. 

정답은 정수형 숫자가 들어있는 배열 형태이고, 문자열의 자리수만큼 배열 크기를 할당해주므로  int[] answer = new int[str.length()] 이렇게 작성한다.

answer 배열에 들어갈 문자의 위치값인 p(position)는, 문자열의 길이보다 큰 값으로 임의로 지정해준다.

일단 첫 번째 for문을 보자.

애초에 이 문제는 str.charAt(i)번째 문자와 문자 c가 같을 경우 위치는 0이 되는 것이고, 다를 경우 0이었던 위치로부터 한 문자씩 멀어지는 것이기 때문에 p를 1씩 더해준다.

그래서 str.charAt(i) 번째 문자와 c 문자가 다를 경우 p++, 같을 경우 p=0으로 해주며 answer에는 p의 값을 넣어준다.

첫 번째 반복문을 다 돌리고나면 answer배열 내부는 아래 [그림1]과 같은 모양새가 된다.

[그림1] p값이 저장된 answer 배열

 

두 번째 반복문은 첫 번째 반복문과 거의 똑같다. 하지만 뒤에서부터 시작해준다.

두 번째 반복문 돌리기 전, p=1000으로 다시 초기화 해 첫 번째 반복문과 같은 과정을 거친다.

여기서 핵심!

문자가 같으면 p=0으로 이미 answer 배열에 저장되어 있으니 다시 저장해줄 필요 없고, 

문자가 다르면 똑같이 p++ 해주나, answer배열에 저장된 p의 값과 현재 p값을 비교해 작은 값을 넣어준다. 

즉, 방법은 앞과 뒤로 반복문으로 위치값을 저장하고, 위치값 중 작은 값을 answer 배열에 넣으면 된다.

그래서 정답은 가운데(주황색) 적힌 숫자의 배열이 answer배열로 저장되어 return 된다.

[그림2]

 

 

🤓 정리

• for반복문을 배열의 뒤에서부터 시작할 때는 항상 변수의 초기값과 범위를 잘 확인하는 것이 좋겠다.

 

 

 

---

저번주 일요일을 마지막으로 알고리즘 풀이를 못올리다가 이제야 올린다.

조금 해이해진건지 너무 잠도오고 피곤해서 힘들었지만, 다시 복습하니 재미있다.

내일도 또 공부해야지..!! 

다른 방법이 있다면 댓글 부탁드립니다. :)