프로그래머스[Java] - (Level2)영어 끝말잇기

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

프로그래머스

코드

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        int[] answer = new int[2];
        List<String> list = new ArrayList<String>();
        boolean flag = true;
        
        for(int i=0; i<words.length; i++){
            if(list.contains(words[i])){   // 이전에 등장한 단어인경우
                answer[0] = (i%n) + 1;
                answer[1] = (i/n) + 1;
                flag = false;
                break;
            }
            
            list.add(words[i]); // 현재 단어 리스트에 넣기
            
            // 이전 끝단어와 현재 첫단어가 다른경우 - 끝말잇기가 아닌경우
            if(i>0 && words[i-1].charAt(words[i-1].length()-1) != words[i].charAt(0)){
                answer[0] = (i%n) + 1;
                answer[1] = (i/n) + 1;
                flag = false;
                break;
            }
        }
        if(flag) return new int[]{0, 0};
        return answer;
    }
}

풀이

어제 풀다가 실패해서 놔두고 오늘 다시 풀어보니 해결했다. 

문제는 길지만 주어진 조건에 따라 그대로 구현하면 되는 문제인데 문제의 조건은 다음과 같다.

 

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
4. 이전에 등장했던 단어는 사용할 수 없습니다.
5. 한 글자인 단어는 인정되지 않습니다.

여기서 2, 3, 4번의 조건을 유의하며 문제를 해결하면 된다.

 

 

● 3번은 앞사람이 말한 단어의 마지막 문자와 현재 사람이 말한 첫번째 문자가 같은지 판단 하는 조건은 다음이다.

(가장 첫번째 단어는 확인할 필요가 없으므로 i > 0 이라는 조건을 추가했다.)

            // 이전 끝단어와 현재 첫단어가 다른경우 - 끝말잇기가 아닌경우
            if(i>0 && words[i-1].charAt(words[i-1].length()-1) != words[i].charAt(0)){
                answer[0] = (i%n) + 1;
                answer[1] = (i/n) + 1;
                flag = false;
                break;
            }

 

● 4번은 list에 단어를 하나씩 넣고, 중복체크(contains()) 메소드를 통해 확인을 한다.

        for(int i=0; i<words.length; i++){
            if(list.contains(words[i])){   // 이전에 등장한 단어인경우
                answer[0] = (i%n) + 1;
                answer[1] = (i/n) + 1;
                flag = false;
                break;
            }
            
            list.add(words[i]); // 현재 단어 리스트에 넣기

 

● 만약 위에서 조건 3, 4번에 의해 탈락자가 생기지 않는다면 flag의 값은 그대로 true이므로,

마지막에 true일경우 [0, 0]을 리턴해준다.

        if(flag) return new int[]{0, 0};

 

리턴하는 값 - [번호, 차례] 에서 번호와 차례를 어떻게 구해야 할지 고민을 좀 했는데, 직접 주어진 입출력을 예제로 하나하나 써가며 규칙을 찾아서 해결했고, 번호 = (i%n) + 1 , 차례 = (i/n) + 1 이라는 규칙이 있다.

 

 

첫번째 입출력 예제를 예로 들어서 보자. ( n = 3 , 단어 = 9개 )

3

[tank, kick, know, wheel, land, dream, mother, robot, tank]

[3,3]

위 그림에서 첫번째 열들의 값은 i의값(인덱스)를 나타내고, 두번째는 문자, 세번째가 [번호, 차례]의 형식이다.

먼저 번호 부터 확인해보자.

i의 값이 0, 3, 6 일때 첫번째 사람이다.

0, 3, 6 을 3으로 나눴을경우 나머지는 모두 0이다. 따라서 여기에 +1을 해주면 첫번째 사람이 된다.

 

i의 값이 1, 4, 7 일때 두번째 사람이다.

1, 4, 7 을 3으로 나눴을경우 나머지는 모두 1이다. 따라서 여기에 +1을 해주면 두번째 사람이 된다.

 

따라서 규칙은 answer[0] = i%n + 1 이 된다.

 

 

그 다음으로 차례를 확인해보자.

i의 값이 0, 1, 2 일때 차례는 1이다.

0, 1, 2를 3으로 나눴을경우 몫은 0이다. 따라서 여기에 +1을 해주면 첫번째 차례가 된다.

 

i의 값이 3, 4, 5 일때 차례는 2이다.

3, 4, 5 를 3으로 나눴을경우 몫은 1이다. 따라서 여기에 +1을 해주면 두번째 차례가 된다.

 

따라서 규칙은 answer[1] = i/n + 1 이 된다.

 

 

 

+ 어제 풀었던 코드로도 해결이 됐다.

class Solution {

	// 배열에 단어가 중복인지 아닌지 체크
	public static boolean checkWords(String[] words, String s, int end){
		int count = 0;
		boolean flag = true;
		for(int i=0; i<end; i++)
			if(words[i].equals(s))
				count ++;
		// 배열에 단어가 한개 인 경우
		if(count == 0)  flag = true;

		// 배열에 단어가 두개 이상인 경우
		else    flag = false;
		return flag;
	}

	public static int[] solution(int n, String[] words) {
		int[] answer = new int[2];
		boolean check = true;   // 탈락자가 생기는지 아닌지 체크
		int end = 0;

		/* 탈락하는 경우는 2가지 -> 이전에 말한 단어 말하거나 단어를 잘못 말한 경우 */
		for(int i=0; i<words.length; i++){
			end = i;
			// 1) 현재 말한 단어가 이전에 등장했던 단어인 경우
			if(!checkWords(words, words[i], end)){
				answer[0] = (i%n) + 1;
				answer[1] = (i/n) + 1;
				check = false;
				break;
			}

			// 2) 앞사람이 말한 단어의 마지막 문자로 시작하는 단어가 아닐경우(e.g "never" - "now")
			if(i>0 && words[i-1].charAt(words[i-1].length()-1) != words[i].charAt(0)){
				answer[0] = (i%n) + 1;
				answer[1] = (i/n) + 1;
				check = false;
				break;
			}
		}

		// 위 for문에서 탈락하는 사람이 없는 경우 1), 2)에 모두 포함되지 않는 경우
		if(check) return new int[]{0, 0};

		return answer;
	}
}

어제는 ArrayList 대신 현재의 단어가 배열에서 이전에 사용된 단어인지 아닌지 확인을 하는 메소드 checkWords() 

를 만들었다.

여기서 매개변수 end는 어디까지 반복을 할지 결정해주는 변수인데,

 

만약 아래에서 know라는 단어가 들어왔을때, 앞에값(tank, kick)까지 확인해야 하므로 i까지 확인해야 한다.

따라서 for문의 i까지 확인해야 하므로 매개변수에 넣어주었다.

3

[tank, kick, know, wheel, land, dream, mother, robot, tank]

[3,3]

그 외 나머지는 동일하다.

 

 

+ 첫 코드의 if문을 하나로 줄이면 더 간단한 코드가 된다.

import java.util.*;

class Solution {
    public int[] solution(int n, String[] words) {
        int[] answer = new int[2];
        List<String> list = new ArrayList<String>();
        boolean flag = true;
        
        for(int i=0; i<words.length; i++){
            if(i>0 && words[i-1].charAt(words[i-1].length()-1) != words[i].charAt(0) 
               || list.contains(words[i])){   // 이전에 등장한 단어인경우
                answer[0] = (i%n) + 1;
                answer[1] = (i/n) + 1;
                flag = false;
                break;
            }
            
            list.add(words[i]); // 현재 단어 리스트에 넣기
        }
        if(flag) return new int[]{0, 0};
        return answer;
    }
}