반복되지 않는 첫 번째 문자 찾기

문제

- 문자열에서 처음으로 반복되지 않는 문자를 효율적으로 찾아내는 함수를 작성하라. 예를 들어 "total"에서 처음으로 등장하는 반복되지 않는 문자는 'o'이며, "teeter"에서 처음으로 등장하는 반복되지 않는 문자는 'r'이다. 작성한 알고리즘의 효율에 대해 논하라

간단하게 푸는 것은 반복분을 두번 돌려 검사하는 방식인데 이 방식은 최악의 경우 시간 복잡도가 이므로 효율적이지 못하다고 할 수 있다.

그래서 생각했던게 해시맵을 사용하면 시간 복잡도에 유리하게 풀 수 있다고 생각했다.(풀다가 생각난건데 그냥 HashMap을 쓰면 순서가 뒤죽박죽이 되기 때문에 LinkedHashMap을 써서 순서를 유지하는 방식으로 풀었다.)

findChar.java

import java.util.HashMap;
import java.util.LinkedHashMap;
 
public class FirstChar {
    public String solution(String str){
        String answer="";
        HashMap<String,Integer> hash=new LinkedHashMap<>();//해시맵에 넣은 순서를 유지하기 위해
        String[] strArray=str.split("");//한글자 단위로 분리
 
        inputElement(hash, strArray);
 
        return findAnswer(answer, hash, strArray);
    }
 
    private String findAnswer(String answer, HashMap<String, Integer> hash, String[] strArray) {
        for(String s:strArray){
            if(hash.get(s)==1){
                answer=answer.concat(s);
                break;
            }
        }
        return answer;
    }
 
    private void inputElement(HashMap<String, Integer> hash, String[] strArray) {
        for(String s:strArray){
            if(hash.get(s)==null){//처음 등장하는 문자일때
                hash.put(s, 1);
            }
            else{//앞에 나왔던 문자일때는 value증가
                hash.put(s,hash.get(s)+1);
            }
        }
    }
}
 

findCharTest.java

import org.junit.Test;
import static org.junit.Assert.*;
 
public class FirstCharTest {
    FirstChar f=new FirstChar();
    @Test
    public void 테스트_결과() {
        assertEquals("o",f.solution("total"));
        assertEquals("r",f.solution("teeter"));
    }
}