[LeetCode/JAVA] 1436. Destination City

https://github.com/ROUTINE-STUDY/Algorithm

ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/destination-city/

Destination City - LeetCode

문제 설명

출처 : LeetCode

배열이 주어집니다. [서울, 부산]의 의미는 서울에서 부산으로 나가는 경로가 존재함을 의미합니다.
다양한 경로 중 더이상 나가는 경로가 없는 목적지 도시가 존재합니다.
그 도시를 반환하세요.

풀이 방법

목적지 도시는 어떠한 경우에도 배열의 첫 번째 도시가 될 수 없음을 이용하였습니다.

1. 첫 번째 도시들의 이름을 StringBuilder 객체에 이어 붙입니다.
2. 두 번째 도시들 중 첫 번째 도시에 포함되어있지 않다면 반환합니다.

내 코드(JAVA)

 

// 목적지는 어떠한 경로의 첫 번째 도시가 될 수 없음을 이용
public String destCity(List<List<String>> paths) {
    String res = "";
    StringBuilder firstCitys = new StringBuilder();

    // 첫 번째 도시 세팅
    for(List<String> path : paths) {
        String firstCity = path.get(0);
        firstCitys = firstCitys.append(firstCity);
    }

    // 두 번째 도시들 중 첫 번째 도시에 해당하지 않는 도시 찾기
    for(List<String> path : paths) {
        String lastCity = path.get(1);

        if(firstCitys.indexOf(lastCity) < 0) {
            res = lastCity;
            break;
        }
    }

    return res;
}

다른 사람 코드

 

public String destCity(List<List<String>> paths) {
    Set<String> cities = new HashSet<>(); 
    for (List<String> path : paths) {
    	cities.add(path.get(0)); 
    }

    for (List<String> path : paths) {
        String dest = path.get(1); 
        if (!cities.contains(dest)) {
        	return dest; 
        }
    }
	return "";
}

 

String 카테고리의 문제임을 알고 있어 Set을 생각하지 못하였습니다.

전체적인 로직은 유사하지만 Set을 사용하여 첫 번째 도시 목록에 불필요한 중복 데이터를 삽입하지 않습니다.

HashSet의 contains 메서드는 O(1) 시간 복잡도를 가지기 때문에 속도도 더 빠르네요.

 

문제의 카테고리에 종속되지 말고, 다양한 측면으로 문제를 바라보는 습관을 가지겠습니다.