Two Strings

🔗 문제 링크

https://www.hackerrank.com/challenges/two-strings/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=dictionaries-hashmaps

❔ 문제 설명

Given two strings, determine if they share a common substring. A substring may be as small as one character.

Example

s1 = 'and'
s2 = 'art'

These share the common substring a.

s1 = 'be'
s2 = 'cat'

These do not share a substring.

Function Description

Complete the function twoStrings in the editor below.

twoStrings has the following parameter(s):

• string s1: a string
• string s2: another string

Returns

• string: either YES or NO

Input Format

The first line contains a single integer p, the number of test cases.

The following pairs of lines are as follows:

• The first line contains string s1.
• The second line contains string s2.

Output Format

For each pair of strings, return YES or NO.

⚠️ 제한사항

• s1 and s2 consist of characters in the range ascii[a-z].

• $1 ≤ p ≤ 10$

• $1 ≤ |s1|,|s2| ≤ 10^5$

---

💡 풀이 (언어 : Java)

시간복잡도에서 계속 탈락해서 애를 먹었다. 처음에는 비교당하는 배열의 원소가 더 크면 뒤의 원소들은 비교하지말고 중단하도록 했는데 이래도 탈락했다. 그래서 비교당하는 배열의 앞의 비교했던 원소들도 비교작업에서 제외해주기 위해 idx를 기록해주고 그곳부터 다음 비교할 배열의 원소가 비교 작업을 시작하도록 알고리즘을 작성했고 이것은 시간복잡도를 통과했다. 타인의 풀이는 set를 이용해서 중복문자를 제거해주었다. 중복제거 만으로 시간복잡도를 통과하는 것이 가능했나보다.

내 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	private static String twoStrings(String s1, String s2) {
		char[] s1Arr = s1.toCharArray();
		char[] s2Arr = s2.toCharArray();
		Arrays.sort(s1Arr);
		Arrays.sort(s2Arr);
		// 비교당하는 문자 리스트에서 비교하는 리스트에서 어디 인덱스까지 비교해봤는지 기록하는 인덱스 
		int idx = 0;
		// 비교 당하는 배열 원소를 모두 비교해봤는데 비교하는 배열의 앞의 원소보다 작았으면
		// 비교하는 배열의 그 뒤의 모든 원소는 더 볼 필요없으니 for문 종료
		for (int i = 0; i < s1Arr.length && idx < s2Arr.length; i++) {
			while (idx < s2Arr.length) {
				// 비교하는 배열의 원소가 비교 당하는 배열의 원소보다 작으면 뒤는 
                		// 더 볼필요 없으니 중단하고 다음 문자로
				if (s1Arr[i] < s2Arr[idx]) {
					break;
				}
				if (s1Arr[i] == s2Arr[idx]) {
					return "YES";
				}
				idx++;
			}
		}
		return "NO";
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			String s1 = br.readLine();
			String s2 = br.readLine();			
			System.out.println(twoStrings(s1, s2));
		}
		br.close();
	}
}

배울 만한 풀이

 static String twoStrings(String s1, String s2) {
    Set<String> set = new HashSet<String>();
    String[] c1 = s1.split("");
    for (String a : c1)
      set.add(a);
    for (String a : set)
      if (s2.contains(a))
        return "YES";
    return "NO";
  }