아마존 닷컴 (Amazon.com) 코딩 연습 문제 - Non Repeating Character

[사진 출처: http://static.interviewstreet.com/whitelabel/code_ninja.png]

 

Amazon.com 에서 준다는 인터뷰 문제중에 하나를 풀어 봤습니다. char 을 integer 가격으로 바꾸는점 하고 ascii 만 주어진다고 가정하고 계산하는게 충분할지 결정하는 순간만 빼고는 그렇게 어렵지는 않았어요.

문제

Find the non-repeating character in a stream of characters.

해석: character 를 저장되어 있는 리스트가 인풋으로 주어지면 그 중 제일 처음으로 반복되지 않는 character 를 찾아라.

우선 characters 들 종류가 총 256개 만 있다고 가정했습니다. 아메리칸 스탠다드인 ASCII 는 126개 character 만 있고 국제 스탠다드인 Unicode 는 현재 95,211 개가 있다고 되어 있는데 인터뷰를 한다면 256개라고 가정을 하면 충분할것 같네요. 문제 해결 방식을 찾기 위해 다음과 같이 pseudocode 를 만들어 보았습니다.

PSEUDOCODE

1. 우선 getFirstNonRepeatingChar() 이란 이름을 가진 함수를 만듭니다. 리턴 타입은 int 에요. 왜 char 로 리턴을 안하냐구요? 그 이유는 나중에 나옵니다 ^^


2. 합수 안에서 처음 index array 를 만듭니다. 언급했듯이 array 사이즈는 256으로 지정합니다.
   
   int[] listAscii = new int[256];
   
   
   처음에는 0 에서 255 까지 기본값으로 0 이 지정됩니다.



3. 첫번째 루푸를 만듭니다. for loop 이고 인덱스 i 를 지정하고 0 에서 character stream 크기까지 처음 루프 (loop) 을 돌립니다. 첫번째 루프는 character 을 하나 하나 char 로 읽다가 해당되는 위치의 listAscii 의 가격을 increment 시킵니다. 모든 char 이 int 가격을 이미 가지고 있기 때문에 listAscii[char[i]] 라고 하면 알아서 멥핑해줍니다.



4. 윗부분의 스텝까지 했으면 listAscii 안에 각 character 가 나타난 횟수 가 저장되어 있습니다. 0 이면 한번도 character 가 나타난 적이 없고 1이면 딱 한번만 나타난거겠죠. 우리가 원하는건 주어진 character stream 안에서 반복되지 않고 딱 한번만 나오는 character 에요. 다르게 말하자면 listAscii 에서 가격이 1일 character 이죠. 하지만 제일 처음 나온 character 만 원하기 때문에 두번째 루프를 만듭니다. 다시 인덱스 i 를 0 에서 character stream 의 크기 만큼 돌립니다. 그리고 listAscii[list[i]] == 1 이라는 콘디션이 바로 만족되면 그 char 가격을 리턴해요.



5. 그런데 여기서 한가지 문제가 있습니다. 만약 character stream 안에서 반복되는 character 가 없으면 어떻하죠? 그게 바로 getFirstNonRepeatingChar() 이란 함수가 char 이 아닌 int 가격을 리턴하게 만든 이유에요. 위의 두번째 루브안에서 caller 에게 리턴이 되지 않으면 -1 를 리턴 시킵니다.
   
   

Big-O 퍼포먼스

Big-O 성능은 어떨까요? 루프를 character stream 의 사이즈만큼 따로 따로 두번 돌리니까 O(N) + O(N) = 2 O(N) = O(N) 이 되겠네요. 리니어 타임 퍼포먼스죠. 나쁘진 않네요 ^^

Source Code

솔류션은 자바로 되어 있습니다.

package com.practice;

public class NonRepeatingCharTest {

	public static void main(String[] args) {
		NonRepeatingCharTest nct = new NonRepeatingCharTest();
		
		// First non repeating character in the list in this example is c
        // though 2, 4, d also qualifies for non repeating characters
		char[] list = new char[] {'a','b','c','2','4','b','a','d'};
		int answer = nct.getFirstNonRepeatingChar(list);
		if(answer == -1) {
			System.out.println("No non repeating character in the list");
		}
		else {
			System.out.println("First non repeating character in the list is " + (char)answer);
		}
	}
	
	public int getFirstNonRepeatingChar(char[] list) {
		int[] listAscii = new int[256];
		// Count the number of character for each asccii character
		for(int i=0; i < list.length; ++ i) {
			listAscii[list[i]] ++;
		}
		
		for(int i=0; i < list.length; ++ i) {
			if(listAscii[list[i]] == 1) 
				return list[i];	
		}
		return -1;
		
	}
}