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