-
프로그래머스 Lv.2) 영어 끝말잇기알고리즘/프로그래머스 2020. 5. 24. 16:43반응형
영어 끝말잇기
풀이
ArrayList를 이용한 풀이(WordChain 메소드)와 이중 for문을 돌면서 조건 검사(getInfo 메소드) 두 방법으로 풀어봤다.
ArrayList도 언뜻 보면 2중 포문 같겠지만, turn과 person을 나눴을 뿐 단일 for문과 같다.
ArrayList를 이용한 풀이는 turn을 돌면서 중복된 단어가 있는지, 단어가 이어지는지를 확인하면서 답을 구하는 방법이다.
이중 for문을 돌면서 검사를 하는 방법은 equals를 통해 앞서 단어가 나왔는지 확인과 이어지는 글자인지 확인을 통해 답을 구했다.
결과적으로는 ArrayList를 이용한 풀이가 속도 및 메모리 측면에서 효율이 좋았다.
코드
import java.util.ArrayList; class Solution { public int[] solution(int n, String[] words) { return wordChain(n,words); } private int[] wordChain(int n, String[] words) { int[] result = new int[2]; ArrayList<String> wordList = new ArrayList<>(); char prev = words[0].charAt(0); loop: for(int turn =0; turn< words.length/n; turn++) { for(int i=0; i<n; i++) { int idx = turn*n +i; String str = words[idx]; if(wordList.contains(str)) { // 이미 나온 단어 result[0] = i+1; result[1] = turn+1; break loop; } else if(prev != str.charAt(0)) { result[0] = i+1; result[1] = turn+1; break loop; } else { // 이어지는 경우 prev = str.charAt(str.length()-1); wordList.add(str); } } } return result; } /*private int[] getInfo(int n, String[] words) { int[] result = new int[2]; char ch = words[0].charAt(0); loop: for(int i=0;i<words.length; i++) { for(int j=0; j<i; j++) { // 같은 글자 검사 if(i!=j && words[i].equals(words[j])) { // 여기가 걸림 result[0] = i%n +1; // person result[1] = i/n +1; // turn break loop; } } if(ch != words[i].charAt(0)) { // 이어지지 않는 글자 result[0] = i%n +1; // person result[1] = i/n +1; // turn break; } else { ch = words[i].charAt(words[i].length()-1); } } System.out.println(result[0] + " " + result[1]); return result; }*/ }
반응형'알고리즘 > 프로그래머스' 카테고리의 다른 글
프로그래머스 Lv.3) 방문 길이 (0) 2020.05.29 프로그래머스 Lv.3) 가장 긴 팰린드롬 (0) 2020.05.27 프로그래머스 Lv.2) 예상 대진표 (0) 2020.05.22 프로그래머스 Lv.2) 숫자의 표현 (0) 2020.05.21 프로그래머스 Lv.2) 행렬의 곱셈 (0) 2020.05.21