[프로그래머스(programmers)] (Summer/Winter Coding 2018) 영어 끝말잇기

알고리즘 문제 풀이 / 프로그래머스 (programmers)  - 영어 끝말잇기

 

 

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/12981

코딩테스트 연습 - 영어 끝말잇기

 

 

문제 풀이

 

알

 

 

처음 문제를 보고 생각한 것은 앞에 말한것을 구분하기 위하여 str이라는 문자열에 붙이면서 contains로 확인하려는 생각이었다.

이것도 정답이였지만 문제를 풀고난 후 저녁에 잠을 자려고 눈을 감았을 때 문득 이 문제가 생각나서 내가 푼 풀이를 되내이며 생각하는 중에 오류를 발견했다. 바로 qwqwq 이런 단어가 나온 후 qwq이런식의 단어가 나오면 내 코드는 단어가 중복되었다고 나올것이다. 테스트케이스에는 없는 오류였기에 통과로 나왔지만 맞는 코드는 아니였던 것이다. 그래서 다음 날 아침에 돌려보니 역시 틀렸다. 코드를 조금만 바꾸면 문자열 붙이는 것으로도 완벽하게 풀 수 있긴 했다. 하지만 끝말잇기가 더 길어지면 효율적이지 못할거란 생각이들었다. 결국 문자열로 붙이는 것 말고 다른 방법으로 해야겠단 생각에 hashmap을 사용해서 key의 중복으로 구현했다. 이렇게 풀어보니 경과시간이 1,2초 정도 단축되었다.

 

 

 

첫번째 풀이 ( 성공 )

 

public static int[] solution(int n, String[] words) {
	int[] answer = {0,0};
	String str = "," + words[0] ;
	int count = 0;
	for(int i = 1; i < words.length; i++) {
		if(str.contains(","+words[i]) || words[i-1].charAt(words[i-1].length() - 1) != words[i].charAt(0)) {
			count = i+1;
			break;
		} 
		str +=  "," + words[i];
	}

	if(count != 0) {
			
		answer[0] = count % n == 0 ? n : count % n ;
		answer[1] = count % n == 0 ? count / n : count/n + 1;
	}
	return answer;
}

 

 

두번째 풀이 ( 성공 )

 

 

public static int[] solution(int n, String[] words) {
	int[] answer = {0,0};
	HashMap<String, Integer> map = new HashMap<>();
	map.put(words[0], null);
	int count = 0;
	for(int i = 1; i < words.length; i++) {
		if(map.containsKey(words[i]) || words[i-1].charAt(words[i-1].length() - 1) != words[i].charAt(0)) {
			count = i+1;
			break;
		} 
		map.put(words[i], null);
	}

	if(count != 0) {
		answer[0] = count % n == 0 ? n : count % n ;
		answer[1] = count % n == 0 ? count / n : count/n + 1;
	}
	return answer;
}