Baekjakka

387.First Unique Character in a String

문제

• 문자열이 주어지면, 처음으로 반복되지 않은 문자의 인덱스를 찾아라. 반복되지않는 문자가 없다면 -1을 리턴하기

Examples:

    s = "leetcode"

    return 0.

    s = "loveleetcode"

    return 2

Note

• 문자열은 모두 소문자라고 가정합니다.

Solution 1. 앞에서부터 비교하기
1번 문자가 다음번째랑 같은지 안같으면 다음과 같은지 비교하다 같으면 2번 문자부터 순차적으로 비교하기
     1......n
      2.....n
       3...n

Solution 2. Map활용하기
문자를 Key, 갯수를 Value로 만들기 ( 1...n )

문자열의 앞의 문자부터 순서대로 Map의 키로 전달해 Value를 확인하여 1인 문자가 나오면 해당 인덱스를 반환한다.

( 1...n )

1번의 방법은 너무 많은 반복이 일어날 수 있다. 맨 마지막의 문자가 1번 쓰였을 경우 n번, n-1번, n-2번, ...., 2번, 1번의 경우까지 확인하는 경우도 있어 좋은 방법이라고 생각되지는 않는다.

2번의 경우는 문자열을 처음부터 끝까지 2번만 움직여보면 확인할 수 있는 방법이다.

처음에는 Map에 해당 문자별 갯수가 몇개인지 넣어두고

두번째는 문자열의 순서에 맞게 해당 문자의 갯수가 몇개인지 확인하여 해당 문자의 인덱스를 찾으면 된다.

Tip

Code

• Github : 387.First Unique Character in a String

Reference

• 387.First Unique Character in a String

알고리즘 문제를 보면 해결할 방법이 여러가지인게 재밌는 부분인것 같다. 물론 방법이 여러가지라고 모두 좋은 방법만 있지는 않지만 생각하지 못했던 방법을 보고 공부가 되기도하고 생각하는 방법이 늘어나 재밌는 것 같다.

이번에 풀어볼 문제는 Leetcode라는 사이트에 있는 문제입니다.

344. ReverseString이란 문제이며 난이도는 easy 입니다.

코드는 아래의 링크를 통해 확인해볼 수 있습니다.

문제 : 문자열을 Reverse(뒤집는)하는 함수를 만들어라.

    조건 1. 입력 문자열을 char[] 형태로 제공된다.
    조건 2. 다른 Array에 추가 공간을 할당하지 않는다.
    조건 3. 모든 문자는 출력가능한 아스키 문자로 구성된다고 가정한다.

Example 1
    Input: ["h","e","l","l","o"]
    Output: ["o","l","l","e","h"]

Example 2
    Input: ["H","a","n","n","a","h"]
    Output: ["h","a","n","n","a","H"]

Solution 1. 반복문 활용하기
    Input 문자열의 크기만큼 반복문을 사용해 역순으로 출력하기

Solution 2. 반복문 활용하기
    Reverse는 뒤집는 것이므로 1 2 3 4 5 가 있을 때 5 4 3 2 1 이 되야 하는 것.
    1 2 3 4 5
    5 4 3 2 1
    이 형태를 보면
    1과 5를 바꾸고
    2와 4를 바꾸는 형태임을 확인할 수 있다.

    즉, Swap하면 n번의 반복문이 절반으로 줄어들 수 있게 된다.

Solution 3. 제공되는 함수 활용하기

주의사항
    main에 있는 원본 Input에 변화가 생길 수 있다.

    1번은 역순으로 출력을 하여 원본에 변화가 생기지 않지만,
    2번과, 3번은 원본에 변화가 생기게 되므로 주의해야한다.

    만약 원본이 변하지 않길 바란다면 s를 그대로 넘겨주지 말고
    s.copyOf(), s.clone() 를 이용하면 된다.

    위의 이미지는 디버깅을 했을 때 나타나는 값들이다.

    s는 원본 데이터

    copyOfs는 s.copyOf()의 결과

    cloneS는 s.clone()의 결과

    이미지를 보면 알 수 있듯이 각각 다른 객체임을 확인할 수 있다.

    그럼 정말로 객체를 함수에 넘겨주었을 때 같은 객체가 넘어가는지 아래의 이미지를 통해 확인해보겠습니다.

    먼저 main의 s객체를 보면 @818임을 확인할 수 있다.

   main에서 reverseString1() 함수의 파라미터로 넘겨주고 함수에서 s객체를 확인해보면 아래와 같다.

    main의 객체와 같은 객체임을 확인할 수 있다. 따라서 함수에서 객체의 변화를 주면 함수안에서만 변화가

    일어나는 것이 아니라 밖에서도 변화가 유지될 수 있으므로 주의하는게 좋다.

copyOf()로 얻은 객체와, clone()으로 얻은 객체가 다른 객체임을 확인해봤는데 이들을 비교하면 어떤 결과가 나오게될지 궁금해져 비교를 해보게 되었다.

s == s.copyOf()
s == s.clone()

s.equals(s.copyOf())
s.equals(s.clone())

위의 결과가 어떻게 나오게 될까?

결과

더보기

s == s.copyOf() // false
s == s.clone() // false

s.equals(s.copyOf()) // false
s.equals(s.clone()) // false

 생각했던대로 결과가 나왔나요? 위의 코드는 같은 코드이기에 같은 결과를 얻게됩니다.

만약 객체의 내용물을 비교하고 싶다면 어떻게 해야 했을까요? contentEquals()라는 메서드를 사용하면 됩니다.

 

아래의 이미지를 통해 결과를 확인해볼 수 있습니다.

 

Code

• Github : 344.ReverseString.kt

Reference

• 344.ReverseString

시간복잡도란 무엇일까요?

점근적 실행시간, 또는 big-O 시간에 대한 개념 이라고 말을 합니다. 예를 들어 데이터 전송 '알고리즘'의 실행시간을 예를 들어 보겠습니다.

온라인 전송 : O(s). 여기서 s는 파일의 크기가 된다. 즉, 파일의 크기가 증대함에 따라 전송 시간 또한 선형적으로 증가합니다.

비행기를 통한 전송 : O(1). 파일 크기에 관계없이 파일을 전송하는데 걸리는 시간이 늘어나지 않는다. 즉, 상수 시간만큼 소요된다.

간단하게 그래프로 그려 보겠습니다.

시간복잡도를 구할 때 기억할 것

• 상수항은 무시하라
• 지배적이지 않은 항은 무시하라

상수항은 무시하라

만든 알고리즘의 시간 복잡도가 4N+100000라는 시간이 걸린다고 생각해보자. N값의 따라 걸리는 시간이 달라진다. N의 값이 점점 커지고 여러분이 상상하는 가장 큰 숫자가 된다고 생각해보자. 뒤에 상수항은 그 숫자에 얼마나 큰 영향을 주게 되나요?

지배적이지 않은 항은 무시하라

이번에 만든 알고리즘의 시간복잡도는 N² + N + 1000000 의 시간이 걸린다고 생각해보자. 이번에도 N의 값을 계속해서 키워나갈 때, N²의 값, N의 값, 1000000 들의 변화를 살펴보자. N²값에 비하면 N은 상수항과 비슷한 느낌을 받는다. 즉, N²값에 따라 이 알고리즘이 걸리는 시간이 결정된다. 그러므로 이 알고리즘을 big-O표기법을 사용해 표현하면 O(n²)의 시간복잡도를 가진다고 말할 수 있다.

덧셈 vs 곱셈

덧셈 수행시간 : O(A + B)

곰셈 수행시간 (A * B)

알고리즘이 두 단계로 이루어져 있다고 가정하자. 어떤 경우에 수행 시간을 곱하고 어떤 경우에 더해야 할까?

• 만약 알고리즘이 "A 일을 모두 끝마친 후에 B일을 수행"하는 형태라면 A와 B의 수행시간을 더해야한다.
• 만약 알고리즘이 "A 일을 할 때마다 B일을 수행"하는 형태라면 A와 B의 수행시간을 곱해야 한다.

log N 수행시간

O(logN) 수행 시간을 자주 접할텐데 이 수행 시간은 어떻게 구해진걸까?

binary search(이진 탐색)을 생각해보자. 이진 탐색은 N개의 정렬된 원소가 들어있는 배열에서 원소 x를 찾을 때 사용된다. 먼저 원소 x와 배열의 중간값을 비교한다. 'x==중간값'을 만족하면 반환한다. 'x < 중간값'일 때는 배열의 왼쪽 부분을 재탐색하고 'x > 중간값'일 경우에는 배열의 오른쪽 부분을 재탐색한다.

처음에는 N개가 들어있는 배열에서 시작한다. 한 단계가 지나면 탐색해야할 원소의 개수가 N/2로 줄어들고, 다음 단계에서는 N/4로 줄어든다. 그러다 원소를 찾거나 탐색할 원소 1개가 남으면 탐색을 중지한다.

시작 N이 16이라고 가정하고 정리하면,

N = 16

N = 8

N = 4

N = 2

N = 1 의 결과로 원하는 x를 찾을 수 있다.

반대로 16에서 1로 증가하는 순서로 생각해보면 1에 2를 몇번이나 곱해야 할까?

N = 1

N = 2

N = 4

N = 8

N = 16 약, 4번 2를 곱하고 결과 값을 얻을 수 있다.

즉 2^k = N을 만족하는 k는 무엇인가? 이때 사용되는 것이 바로 로그(log)이다.

2^k = N  ▶  log₂16 = 4  ▶  4

log₂N = k  ▶ 2^k = N

어떤 문제에서 원소의 개수가 절반씩 줄어든다면 그 문제의 수행 시간은 O(logN)이 될 가능성이 크다. 로그의 밑은 고려하지 않아도 된다. 밑이 다른 로그는 오직 상수항만큼만 차이가 나는데 위에서 언급했듯이 상수항은 영향이 크지 않다. 표현할 때도 logN으로 표현되며, 로그의 밑은 무시해도 된다.

재귀적으로 수행시간 구하기

오메가 : 최선의 시간을 고려
세타 : 평균의 시간을 고려
오 : 최악의 시간을 고려 (세타를 O(오)로 통합해 표현하기도 합니다)

Chapter3 : Jailbreak 네번째 문제풀이를 하겠습니다.

Pattern : A man, a plan a canal: Panama

이번에도 어렵지않게 패턴의 규칙을 찾아낼 수 있습니다.

배열안의 원소들이 가운데원소를 기점으로 좌우대칭을 이룬상태인지를 확인해주면 되는 간단한 규칙입니다.

그럼 코드로 작성해보겠습니다. 얍!

배열의 처음부분과 끝부분에서부터 점점 배열의 위치를 가운데로 이동시켜서 비교해줍니다.

그렇게 모두 같으면 true를 리턴하게되고 틀린게 하나라도 있다면 false를 리턴해주게 됩니다.

참 쉽죠?

깔끔히 Chapter3 : Jailbreak 모두 성공했습니다. 다음에 Chapter4 로 돌아오겠습니다.

이상 Chapter3 : Jailbreak(4) 풀이 였습니다.

Chapter3 : Jailbreak 세번째 문제풀이를 하겠습니다.

Pattern : This is odd

이번 패턴도 간단합니다. 홀수일 경우에는 1을 돌려주고 짝수일경우에는 0을 돌려주면 됩니다.

그럼 코드로 작성해보겠습니다. 얍!

입력값이 1보다 큰동안에 반복문을 이용해서 입력값에서 2씩 계속 값을 빼줍니다.

참 쉽죠?

깔끔히 성공했습니다. 다음에 네번째 문제로 돌아오겠습니다.

이상 Chapter3 : Jailbreak(3) 풀이 였습니다.

Chapter3 : Jailbreak 두번째 문제풀이를 하겠습니다.

Pattern : Maxxxxx

이전에는 배열안에 두개밖에 없었는데 이제는 배열안에 원소들이 뒤죽박죽 난리났네요

그래도 배열안에서 제일 큰 수를 찾아내는 max값을 찾아내는 일이란것은 변함없습니다.

그럼 코드를 작성해보겠습니다. 얍!

코드도 간단합니다.

1번 배열의 첫번째 원소를 변수에 저장해줍니다.

2번 배열안의 모든 원소와 값을 비교해야하므로 배열의 길이만큼 반복되는 반복문을 만들어 줍니다.

3번 배열의 원소를 [0] ~ [n]까지 모두 비교해 큰수를 변수 var_b에 넣어줍니다.

이것을 기반으로 만든 코드가 위와 같습니다.

참 쉽죠?

깔끔히 성공했습니다. 다음에 세번째 문제로 돌아오겠습니다.

이상 Chapter3 : Jailbreak(2) 풀이 였습니다.

이제는 Chapter3 : Jailbreak 가 열렸네요. 오늘도 문제를 다 뿌수도록 하겠습니다.

들어와보니 익숙한 느낌의 사과가 반겨주네요.

Pattern : Max

첫번째 문제의 패턴은 Max 최대값을 찾는 문제입니다.

배열안에 두개의 원소가 들어있고 둘 중 누가 더 큰 수인지 판별하는 간단한 패턴입니다.

그럼 코드로 작성해보겠습니다. 얍!

위의 코드는 간단합니다.

배열안에 두개의 원소밖에 없기 때문에 두개의 원소를 직접 비교해주고 큰 수를 돌려주는 간단한 문제입니다.

참 쉽죠?

깔끔히 성공했습니다. 다음에 두번째 문제로 돌아오겠습니다.

이상 Chapter3 : Jailbreak(1) 풀이 였습니다.

Chapter 2 : High School Hack 네번째문제입니다.

바로 패턴부터 살펴보겠습니다.

이번 패턴도 어렵지 않습니다.

입력값으로 배열의 길이를 주면 그 길이에 맞춰 배열 안에 0부터 시작하는 양의 정수를 채워 넣으면 됩니다.

그럼 코드를 작성해보겠습니다. 얍!

배열을 돌려줘야 하기 때문에 배열을 먼저 선언해 줬습니다.

그리고 while문을 이용하여 배열안에 0부터 1씩 증가하는 값을 차례대로 채워 넣었습니다.

그리고 while의 반복횟수는 입력값보다 작게 반복하면 됩니다. 배열은 1부터 시작하는게 아니라 0부터 시작하기 때문입니다.

High School Hack (4) 의 문제풀이를 마쳤는데요 Chapter2는 네번째 문제가 마지막 문제였네요.

다음에는 Chapter3으로 돌아오겠습니다.

Chapter 2 : High School Hack 세번째문제입니다.

바로 패턴부터 살펴보겠습니다.

이번 패턴도 간단해 보입니다. 

살펴보니 배열을 입력값으로 주면 배열의 길이를 확인해서 알려주면 될 것 같습니다.

그럼 코드로 작성해보겠습니다. 얍!

이번에 foreach 가 새로 생겨서 foreach를 이용해서 만들었습니다. 먼저 foreach가 어떤건지 예를 들어 보겠습니다.

처음 봤다면 당황하지 마세요. 전혀 어렵지 않습니다.

var_a;     //변수 선언

var_b = [1,2,3,];    //배열 초기화

위처럼 배열과 변수가 있을 때 간단한 코드를 써 보겠습니다.

foreach var_a in var_b {

var_c++ ;

} 

retrun var_c;

이렇게 되면 처음 foreach 문을 들어오게 되었을 때 var_a 에 var_b의 첫번째 인수인 1이 들어가게됩니다.

그리고 중괄호 안의 내용을 실행하게 되는데요 var_c의 값이 1증가합니다.

var_b에 아직 배열에 원소가 남아있으므로 다시 var_a에 var_b의 두번째 인수가 들어갑니다. 그리고 중괄호 안의 코드가 실행됩니다.

이렇게 배열의 마지막 인수까지 실행이 된 후 foreach가 끝나게 됩니다.

그럼 var_b에는 3개의 인수가 들어있으므로 var_c의 값은 1씩 3번 증가했으니 var_c의 값은 3이 됩니다.

이렇게 foreach문을 이용해서 배열의 길이를 알 수 있었습니다. 참 쉽죠?

High School Hack (3) 의 문제풀이를 마치겠습니다.

Chapter 2 : High School Hack 두번째문제입니다.

바로 패턴부터 살펴보겠습니다.

첫번째 문제와 같은 패턴이네요. 입력값의 제곱수를 돌려주면 되는 간단한 패턴이네요.

바로 코드로 작성해보겠습니다. 얍!

저번 문제를 풀고 새롭게 생긴 pow라는 함수를 이용해서 한줄로 만들었습니다.

pow(a,b); 라는 함수는 a를 b의 크기만큼 제곱하는 함수입니다.

간단한 예를 들어보면은   pow(3,5); 라면 3의 5승이 되는 겁니다. 즉 3*3*3*3*3 이 되는거죠. 참 쉽죠?

High School Hack (2) 의 문제풀이를 마치겠습니다.