[Java&알고리즘] 가장 가까운 같은 글자 (Level 1)

 

 

환경

언어 : 자바

단계 : 레벨 1단계 (입문자용)

정답률 : 65%

 

 

 

 

제목 

 

가장 가까운 같은 글자

 

 

 

 

 

문제 설명 및 코드

 

문자열 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은 영어 소문자로만 이루어져 있습니다.

 

 

 

 

 

class Solution {
    public int[] solution(String s) {
        int[] answer = {};
        return answer;
    }
}

 

 

 

 

 

입출력 예

 

 

 

 

 

 

 

입출력 예 설명

 

 

입출력 예 #1
지문과 같습니다.

입출력 예 #2
설명 생략

 

 

 

 

 

 

 

반응형

 

 

 

 

 

 

 

문제 정답 코드

 

 

class Solution {
    public int[] solution(String s) {
        
        int[] answer = new int[s.length()];
        answer[0] = -1;
        
        for(int a=1; a<s.length(); a++){
            boolean ckVal = false;
            int ckCount = 0;
            for(int d=0; d<a; d++){
                if(s.charAt(a) == s.charAt(d)){
                    ckVal = true;
                    ckCount = 1;
                }else if(ckVal){
                    ++ckCount;
                }
            }
            answer[a]  = (ckVal) ? ckCount : -1;
        }
        return answer;
    }
}

 

저는 이중 반복문을 사용하여 문제를 해결해보았습니다.

 

두번째 반복문의 길이를 첫번째 반복문 변수로 설정하고 

 

첫번재 반복문의 값과 두번째 반복문의 값이 같을 경우 boolean 변수를 설정해주고 

 

ckCount 변수를 1로 설정해줍니다.

 

그리고 boolean 변수가 true일 경우 하나씩 증가해준 다음

 

두번째 반복문이 끝나는 부분에서 삼항 연산자로 boolean 변수가 true일 경우

 

ckCount 값을 넣고 아니라면 -1 값을 넣어 배열을 형성해줍니다.

 

 

 

 

 

 

다른사람 풀이

 

 

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++) {
            if(!map.containsKey(s.charAt(i))) {
                answer[i] = -1;
                map.put(s.charAt(i), i);
            }else {
                int before = map.get(s.charAt(i));
                answer[i] = i - before;
                map.put(s.charAt(i), i);
            }
        }
        return answer;
    }
}
 

 

이 코드는 HashMap을 이용하였습니다.

 

문자열 s길이만큼 반복을 하면서

 

맵에 키값이 없으면 -1값을 넣는 동시에 

 

맵에는 키값과 인덱스 값을 넣어줍니다.

 

맵에 키값이 있다면

 

before의 변수에 키의 값을 꺼내거 적용한 다음 

 

반복문의 변수에 빼준 값을 answer변수에 넣어주는 방식입니다.

 

확실히 이런 알고리즘에는 맵을 활용하는 경우가 많군요.. 맵하고 친해져야겠습니다..