알고리즘 1 - 한 문자열 에서 첫 번 째 중복 되 지 않 는 문 자 를 찾 습 니 다.

자바 프로그램 을 만들어 서 문자열 의 첫 번 째 중복 되 지 않 는 문 자 를 찾 습 니 다. 이것 은 프로 그래 밍 테스트 에서 흔히 볼 수 있 는 문제 입 니 다. 문자열 처리 가 프로그래머 면접 에서 보편적 인 화제 이기 때 문 입 니 다.면접 전에 잘 알 고 있 는 프로 그래 밍 문 제 를 준비 하 는 것 이 좋 습 니 다. 예 를 들 어 재 귀 반전 문자열 을 사용 하거나 하나의 문자열 이 답장 인지 확인 하 는 것 이 좋 습 니 다.첫 번 째 중복 되 지 않 는 문 자 를 찾 는 것 도 같은 범주 에 있다.해결 방안 을 제시 하기 전에 우 리 는 먼저 이 문 제 를 이해 하 자.함수 가 필요 합 니 다. 이 함 수 는 문자열 을 매개 변수 로 받 아들 이 고 중복 되 지 않 는 첫 번 째 문 자 를 되 돌려 줍 니 다.예 를 들 어 문자열 'hello' 는 'l' 을 제외 한 모든 문 자 는 중복 되 지 않 지만 'h' 는 첫 번 째 중복 되 지 않 는 문자 입 니 다.마찬가지 로 문자열 'swiss' 에서' w '는 중복 되 지 않 는 첫 번 째 문자 입 니 다.이 문 제 를 해결 하 는 방법 은 모든 문자 의 출현 횟수 를 기록 하기 위해 표를 만 들 고 중복 되 지 않 는 첫 번 째 요 소 를 선택 하 는 것 이다.문 제 는 문자 의 순서 입 니 다. 코드 는 첫 번 째 중복 되 지 않 는 문 자 를 되 돌려 야 합 니 다.또 이 글 에서 우 리 는 이 문 제 를 해결 하 는 세 가지 예 를 볼 수 있다.우리 의 첫 번 째 방안 은 링크 드 하 쉬 맵 을 사용 하여 문자 의 개 수 를 기록 하 는 것 입 니 다. 링크 드 하 쉬 맵 이 유지 하 는 요소 의 순서 와 삽입 순서 가 일치 하기 때문에 우 리 는 문자열 에 있 는 문자 가 나타 나 는 순서에 따라 문 자 를 맵 에 삽입 하 는 것 입 니 다.문자열 을 검색 할 때 링크 드 HashMap 을 교체 하고 값 이 1 인 요 소 를 찾 아야 합 니 다.예, 이 방안 은 하나의 링크 드 HashMap 과 두 개의 순환 만 필요 합 니 다.우리 의 두 번 째 해결 방안 은 시간 과 공간의 절충 으로 한 번 에 반복 되 지 않 는 문 자 를 찾 는 것 이다.이번에 우 리 는 반복 되 거나 중복 되 지 않 는 문 자 를 각각 저장 하기 위해 set 와 List 를 사용 합 니 다.시간 복잡 도가 O (n) 인 문자열 을 스 캔 한 후에 우 리 는 List 를 방문 하여 이 신기 한 중복 되 지 않 는 문 자 를 얻 을 수 있 습 니 다. 이 시간 은 복잡 도가 O (1) 입 니 다. List 는 질서 가 있 기 때문에 get (0) 을 통 해 첫 번 째 요 소 를 얻 을 수 있 습 니 다.우리 의 세 번 째 해결 방안 도 비슷 하 다. 그러나 이번 에는 링크 드 하 쉬 맵 이 아 닌 하 쉬 맵 을 사용한다. 우 리 는 첫 번 째 스 캔 으로 각 문자 의 출현 횟수 를 계산 한 후에 문자열 을 다시 스 캔 하여 중복 되 지 않 는 첫 번 째 문 자 를 찾 을 것 이다.다음 에 우 리 는 이 문 제 를 위해 예시 코드 와 단원 테스트 프로그램 을 작성 할 것 이다.너 도 나의 문자열 면접 문제 목록 에 가서 비슷 한 자바 프로 그래 밍 문 제 를 더 볼 수 있다.
 
어떻게 문자열 에서 첫 번 째 중복 되 지 않 는 문 자 를 찾 습 니까?
주어진 문자열 에서 첫 번 째 중복 되 지 않 는 문 자 를 찾 는 완전한 예제 코드 가 있 습 니 다. 이 프로그램 은 첫 번 째 중복 되 지 않 는 문 자 를 찾 는 방법 세 가 지 를 보 여 주 었 습 니 다. 모든 방법 은 문 제 를 해결 하 는 알고리즘 이 있 습 니 다.
첫 번 째 알고리즘 은 getFirst NonRepeated Char (String str) 방법 에서 실 현 됩 니 다.먼저 문자열 의 문자 배열 을 얻 은 다음 배열 을 옮 겨 다 니 며 해시 표를 만 듭 니 다. 해시 표 의 키 는 문자 이 고 값 은 이 문자 가 나타 나 는 횟수 입 니 다.다음 단 계 는 링크 드 하 쉬 맵 을 옮 겨 다 니 며 첫 번 째 값 이 1 인 요 소 를 찾 습 니 다. 그것 은 첫 번 째 중복 되 지 않 는 문자 입 니 다. 링크 드 하 쉬 맵 이 유지 하 는 요소 의 순서 가 삽입 순서 와 일치 하기 때 문 입 니 다. 우 리 는 문자 배열 을 처음부터 끝까지 옮 겨 다 니 기 때 문 입 니 다.이 알고리즘 은 두 개의 순환 이 필요 하 다 는 단점 이 있 습 니 다. 첫 번 째 순환 횟수 는 문자열 의 문자 갯 수 와 정비례 하고 두 번 째 순환 횟수 는 문자열 에서 중복 되 는 문자 갯 수 와 정비례 합 니 다.최 악의 경우 반복 되 지 않 는 문자 가 문자열 의 맨 끝 에 나타 나 면 이 알고리즘 은 2 * N 의 시간 이 필요 합 니 다.
두 번 째 알고리즘 은 firstNonRepeatingChar (String word) 방법 에서 실 현 됩 니 다.이 솔 루 션 은 문자열 스 캔 에서 첫 번 째 중복 되 지 않 는 문 자 를 찾 을 수 있 으 며 전형 적 인 공간 시간 평가 기술 을 사용 했다.그것 은 두 개의 저장 공간 을 사용 하여 한 번 의 순환 을 줄 이 는 표준 공간 인 시간 절충 이다.중복 되 지 않 는 문자 와 중복 되 지 않 는 문 자 를 분리 해서 저장 하기 때문에 순환 이 끝 난 후에 중복 되 지 않 는 문 자 를 저장 하 는 목록 의 첫 번 째 요 소 는 우리 가 찾 는 첫 번 째 중복 되 지 않 는 문자 입 니 다.이런 해결 방안 은 이전 것 보다 약간 우수 하 다.문자열 에 중복 되 지 않 는 문자 가 없다 면 null 이나 빈 문자열 을 되 돌려 주 는 것 을 선택 할 수 있 습 니 다.
세 번 째 알고리즘 은 firstNonRepeated Character (String word) 방법 에서 첫 번 째 방안 과 매우 유사 하 며 유일한 차이 점 은 HashMap 을 사용 한 것 입 니 다.HashMap 은 특정한 순 서 를 보장 하지 않 기 때문에 원본 문자열 에 의존 하여 중복 되 지 않 는 첫 번 째 문 자 를 찾 아야 합 니 다.세 번 째 해결 방안 의 알고리즘 은 다음 과 같다.
문자열 을 스 캔 하고 모든 문자 의 출현 횟수 를 HashMap 에 저장 합 니 다 문자열 을 옮 겨 다 니 며 맵 에서 모든 문자 의 개 수 를 가 져 옵 니 다 우리 가 왼쪽 에서 오른쪽으로 문 자 를 스 캔 하기 때문에, 어떤 문자 의 계수 가 1 인 것 을 찾 았 을 때, 우 리 는 순환 을 벗 어 날 수 있다. 그것 이 바로 첫 번 째 중복 되 지 않 는 문자 이다.여기 서 문자 순 서 는 원본 문자열 을 다시 옮 겨 다 니 는 것 으로 이 루어 집 니 다.

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;
 
public class Programming {
    /**
     * Java Program to find first duplicate, non-repeated character in a String.
     * It demonstrate three simple example to do this programming problem.
     * 
     * @author Javarevisited
     */
    public static char getFirstNonRepeatedChar(String str) {
        Map<Character, Integer> counts = new LinkedHashMap<Character, Integer>(
                str.length());
        for (char c : str.toCharArray()) {
            counts.put(c, counts.containsKey(c) ? counts.get(c) + 1 : 1);
        }
        for (Entry<Character, Integer> entry : counts.entrySet()) {
            if (entry.getValue() == 1) {
                return entry.getKey();
            }
        }
        throw new RuntimeException("didn't find any non repeated Character");
    }
 
    /**
     * Using HashMap to find first non-repeated character from String in Java.
     * Algorithm :
     * 
     * Step 1 : Scan String and store count of each character in HashMap
     * 
     * Step 2 : traverse String and get count for each character from Map. Since
     * we are going through String from first to last character, * when count
     * for any character is 1, we break, it's the first * non repeated
     * character. Here order is achieved by going * through String again.
     */
    public static char firstNonRepeatingChar(String word) {
        Set<Character> repeating = new HashSet<Character>();
        List<Character> nonRepeating = new ArrayList<Character>();
        for (int i = 0; i < word.length(); i++) {
            char letter = word.charAt(i);
            if (repeating.contains(letter)) {
                continue;
            }
            if (nonRepeating.contains(letter)) {
                nonRepeating.remove((Character) letter);
                repeating.add(letter);
            } else {
                nonRepeating.add(letter);
            }
        }
        return nonRepeating.get(0);
    }
 
    /**
     * Using HashMap to find first non-repeated character from String in Java.
     * Algorithm :
     * 
     * Step 1 : Scan String and store count of each character in HashMap
     * 
     * Step 2 : traverse String and get count for each character from Map. Since
     * we are going through String from first to last character, when count for
     * any character is 1, we break, it's the first non repeated character. Here
     * order is achieved by going through String again.
     * 
     * @return
     */
    public static char firstNonRepeatedCharacter(String word) {
        HashMap<Character, Integer> scoreboard = new HashMap<Character, Integer>();
        // build table [char -> count]
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (scoreboard.containsKey(c)) {
                scoreboard.put(c, scoreboard.get(c) + 1);
            } else {
                scoreboard.put(c, 1);
            }
        }
        // since HashMap doesn't maintain order, going through string again
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (scoreboard.get(c) == 1) {
                return c;
            }
        }
        throw new RuntimeException("Undefined behaviour");
    }
}

 
첫 번 째 유일한 문 자 를 찾 은 JUnit 유닛 테스트
프로그램의 모든 방법 을 테스트 하기 위해 JUnit 테스트 사례 가 있 습 니 다.우 리 는 서로 다른 유형의 입력 을 테스트 합 니 다. 하 나 는 중복 문 자 를 포함 하고 다른 하 나 는 포함 되 지 않 습 니 다.프로그램 이 빈 문자열 을 입력 할 때, null 또는 중복 문자 만 포함 하 는 문자열 을 어떻게 처리 해 야 하 는 지 정의 하지 않 았 기 때문에, 효과 적 인 처 리 를 스스로 정의 할 수 있 습 니 다.

importstatic org.junit.Assert.*;
importorg.cc.source.Programming;
importorg.junit.Test;
 
publicclass ProgrammingTest {
    @Test
    publicvoid testFirstNonRepeatedCharacter() {
        assertEquals('b', Programming.firstNonRepeatedCharacter("abcdefghija"));
        assertEquals('h', Programming.firstNonRepeatedCharacter("hello"));
        assertEquals('J', Programming.firstNonRepeatedCharacter("Java"));
        assertEquals('i', Programming.firstNonRepeatedCharacter("simplest"));
    }
 
    @Test
    publicvoid testFirstNonRepeatingChar() {
        assertEquals('b', Programming.firstNonRepeatingChar("abcdefghija"));
        assertEquals('h', Programming.firstNonRepeatingChar("hello"));
        assertEquals('J', Programming.firstNonRepeatingChar("Java"));
        assertEquals('i', Programming.firstNonRepeatingChar("simplest"));
    }
 
    @Test
    publicvoid testGetFirstNonRepeatedChar() {
        assertEquals('b', Programming.getFirstNonRepeatedChar("abcdefghija"));
        assertEquals('h', Programming.getFirstNonRepeatedChar("hello"));
        assertEquals('J', Programming.getFirstNonRepeatedChar("Java"));
        assertEquals('i', Programming.getFirstNonRepeatedChar("simplest"));
    }
}

너 는 더 많은 장면 을 테스트 하기 위해 테스트 용례 를 개선 할 수 있다.상세 하고 창조 적 인 테스트 용례 를 작성 하 는 것 만큼 면접 관 을 감동 시 킬 수 있 는 것 은 없다. 많은 프로그래머 들 이 이런 것들 을 생각 하지 못 하거나 생각 하려 고 노력 하지 않 는 다.
이것 이 바로 이 글 에서 논술 하고 자 하 는 모든 내용 이다.우 리 는 이 문 제 를 해결 하 는 세 가지 방법 을 보 았 다. 비록 그들의 논 리 는 매우 유사 하지만 모두 같 지 않다. 예제 프로그램 은 초보 자 들 이 자바 용기 구 조 를 배 우 는 데 도 매우 좋다.서로 다른 맵 의 실현 을 알 수 있 는 기 회 를 주 고, 언제 사용 할 지 결정 할 수 있 도록 HashMap 과 LinkedHashMap 의 차 이 를 알 수 있 습 니 다.또한 이 문 제 를 해결 하 는 다른 방법 을 알 고 있다 면 공유 해 보 세 요.면접 과정 에서 도 비슷 한 문제 가 있 었 다 면 면접 경험 을 공유 해 보 세 요.