[코딩테스트] Programmers - 가장 가까운 같은 글자 (성공)

 

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

프로그래머스

 

 

풀이

문자열 s에서 하나씩 문자를 탐색하며 등장한 적이 있는 문자라면 가장 가까운 곳에 있는 같은 글자가 몇 칸 뒤에 있는지를 저장하여 출력하는 문제다. 

 

난 배열을 이용해서 이 문제를 풀었다. 

 

처음 등장하는 문자는 정답 배열에 -1을 저장하고, arr[ s[i] ] = 현재 인덱스

이전에 등장했던 문자는 정답 배열에 "현재 인덱스 - arr[ s[i] ]를 저장하고, arr[ s[i] ] = 현재 인덱스 

 

 

코드 1 - 오답 

namespace 연습문제
{
    internal class Program
    {
        public int[] solution(string s)
        {
            int[] answer = new int[s.Length];
            int answerIndex = 0;

            int[] arr = new int[100000];
            for (int i = 0; i < s.Length; i++)
            {
                // 처음 등장한 문자이면 
                if (arr[s[i]] == 0)
                {
                    answer[answerIndex++] = -1;
                }
                // 이전에 등장한 문자이면
                else
                {
                    answer[answerIndex++] = i - arr[s[i]];
                }

                arr[s[i]] = i;
            }

            return answer;
        }

        static void Main(string[] args)
        {
            Program p = new Program();

            foreach(int num in p.solution("foobar"))
            {
                Console.Write($"{num} ");
            }
        }
    }
}

테스트케이스 2~15, 17~28, 30에서 실패가 떴다. 

 

 

코드 2 - 정답

namespace 연습문제
{
    internal class Program
    {
        public int[] solution(string s)
        {
            int[] answer = new int[s.Length];
            int answerIndex = 0;

            int[] arr = new int[100000];
            Array.Fill(arr, -1);
            for (int i = 0; i < s.Length; i++)
            {
                // 처음 등장한 문자이면 
                if (arr[s[i]] == -1)
                {
                    answer[answerIndex++] = -1;
                }
                // 이전에 등장한 문자이면
                else
                {
                    answer[answerIndex++] = i - arr[s[i]];
                }

                arr[s[i]] = i;
            }

            return answer;
        }

        static void Main(string[] args)
        {
            Program p = new Program();

            foreach(int num in p.solution("foobar"))
            {
                Console.Write($"{num} ");
            }
        }
    }
}

문자열 s의 첫 번째 문자는 처음 등장했으므로 arr[첫번째 문자] = 0으로 저장된다. 

이후 똑같은 문자가 등장하면 if(arr[s[i]] == 0)을 만족하므로 정답 배열에는 -1이 저장된다. 

똑같은 문자가 등장하면 가장 가까운 문자가 몇칸 뒤에 있는지를 정답 배열에 저장해야 하는데 -1을 저장하고 있었다. 

 

처음 등장한 문자를 arr[index] = 0으로 표현했는데 이러면 첫 번째 문자와 똑같은 문자를 처리할 때 문제가 된다. 

처음 등장한 문자를 arr[index] = -1로 표현하니 해결되었다. 

 

 

복습1 풀이 (5/29)

문자열 s의 문자를 하나씩 탐색하며 처음 나온 글자는 -1를 출력, 처음 나온 글자가 아니면 자신과 가장 가까운 곳에 있는 같은 글자가 몇칸 앞에 있는지를 출력해야 한다. 

 

문자열s의 문자의 인덱스 정보를 담는 배열 arr를 만들고, s문자열을 처음부터 탐색하며 처음 등장하는 문자와 이전에 등장했던 문자에 대한 정보를 arr 배열에 저장하며 문제를 풀면 될 것 같다. 

시간복잡도는 O(N)으로 N은 최대 10,000이니 시간도 충분하다. 

 

 

코드1 - 오답

using System;
using System.Text;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string s) 
    {
        List<int> list = new List<int>();
        
        int[] arr = new int[200];
        for(int i = 0; i < s.Length; i++)
        {
            // 처음 나온 글자이면 
            if(arr[s[i]] == 0)
            {
                list.Add(-1);
            }
            // 처음 나온 글자가 아니면 
            else
            {
                list.Add(i - arr[s[i]]); 
            }
            
            arr[s[i]] = i; // 인덱스 저장 
        }
        
        return list.ToArray();
    }
}

 

오답이다. 

만약 s가 "aaaaa"이면 위 코드는 [-1, -1, 1, 1, 1]을 반환한다. 그러나 정답은 [-1, 1, 1, 1, 1]이다. 

 

 

풀이2

같은 문자로 이루어진 문자열일때 문제가 되고 있다. 

코드를 차례대로 읽어보면.. 위 코드에서 0번째 arr의 값이 0이면 "처음 나온 글자"라고 한다. 

arr 배열 원소들의 초기값은 기본적으로 0이다. 처음부터 두번째 문자까지 같은 문자가 나오면 두번째 문자도 처음 나온 글자로 인식하게 되므로 [-1, -1, 1, 1, 1]을 반환하게 된다. 

"처음 나온 글자"를 0으로 표현해서 문제가 되고 있다. 그러면 arr배열의 원소들 초기 값을 -1로 설정하면 해결되지 않을까? 

 

 

코드2 - 정답

using System;
using System.Text;
using System.Collections.Generic;

public class Solution {
    public int[] solution(string s) 
    {
        List<int> list = new List<int>();
        
        int[] arr = new int[200];
        Array.Fill(arr, -1);
        for(int i = 0; i < s.Length; i++)
        {
            // 처음 나온 글자이면 
            if(arr[s[i]] == -1)
                list.Add(-1);
            
            // 처음 나온 글자가 아니면 
            else
                list.Add(i - arr[s[i]]); 
            
            arr[s[i]] = i; // 인덱스 저장 
        }
        
        return list.ToArray();
    }
}

arr배열 원소들의 초기 값을 -1로 설정하니 해결되었다. 

이전처럼 0이 중복될 수가 없으니 해결된 것 같다.