https://school.programmers.co.kr/learn/courses/30/lessons/12981
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코드
주석은 대략적인 풀이과정으로 보면된다.
class Solution {
public int[] solution(int n, String[] words) {
/*
규칙성을 고민해보았으나 그냥 구현문제인 것 같다.
$주어진 words 의 개수가 n으로 나누어떨어지지 않으면 언젠가 같은 단어를 말하게 되므로
반드시 탈락자가 발생한다.
*/
/*
words 에서 인덱스%n 의 값으로 사람을 구분한다.
각 n명이 차례를 가진 횟수를 저장하는 n 크기의 int형 배열 arr 를 기본값 0으로 만들어둔다.
첫 사람의 첫번째는 엣지케이스로 arr[0]=1으로 저장해둔다.
words 의 두번째 인덱스부터 순회한다.
먼저 arr[인덱스%n]+=1 를 한다.
바로 앞 단어와 끝말이 이어지는 지 확인한다.
안 이어지면 answer = [인덱스%n+1, arr[인덱스%n]], 반복문 종료
이어지면 continue
wrods 의 처음부터 현재 인덱스까지 중복되는 단어가 있는 지 확인한다.
있으면 answer = [인덱스%n+1, arr[인덱스%n]], 반복문 종료
없으면 continue
answer 리턴
*/
int[] result = new int[2];
int[] arr = new int[n];
arr[0] = 1;
for(int i=1; i<words.length; i++){
arr[i%n]+=1;
if(words[i-1].charAt(words[i-1].length()-1)
!= words[i].charAt(0)){
result[0] = i%n+1;
result[1] = arr[i%n];
return result;
}
for(int j=0; j<i; j++){
if(words[j].equals(words[i])){
result[0] = i%n+1;
result[1] = arr[i%n];
return result;
}
}
}
if(words.length%n!=0){
result[0] = words.length%n;
result[1] = arr[result[0]-1];
}
return result;
}
}
최소한의 공간을 사용하는데 신경을 쓴 문제였다.
문제의 내용대로 각 참가자별로 배열을 두는 등의 단순한 방법이 떠올랐으나,
주어진 배열을 그대로 사용하는 방법이 떠올라 풀게 되었다.
먼저 n명의 참가자의 차례개수를 저장하는 int arr[] 을 선언한다. 이 배열의 인덱스가 참가자 각각을 나타낸다.
첫번째 단어를 처리하기 위해 arr[0] 에 1을 저장한다.
두번째 단어부터 words[] 를 순회하며, 1) 끝말이 이어지는 지 확인한 후 2) 중복되는 단어가 있었는 지 확인한다.
끝말이 이어지지 않는 순간과 중복되는 단어가 발견되는 순간 해당 참가자와 참가자의 차례 개수를 리턴한다.
위 과정에서 함수가 종료되지 않으면 마지막 단어를 말한 사람의 다음 사람이 결과에 담기도록 한다.
시간이 1시간 50분 정도 소요되었는데, 아주 단순한 이유로 시간을 많이 잡아먹었다.
String 을 == 로 비교했던 것이다... equals() 메소드를 사용하니까 바로 해결이 되었다.
'알고리즘 > 문제' 카테고리의 다른 글
| <실패>[프로그래머스] Lv2 구명보트 / JAVA (0) | 2023.02.28 |
|---|---|
| [프로그래머스] Lv2 카펫 / JAVA (0) | 2023.02.27 |
| [프로그래머스] Lv2 다음 큰 숫자 / JAVA (0) | 2023.02.25 |
| [프로그래머스] Lv2 피보나치 수 / JAVA (0) | 2023.02.25 |
| [프로그래머스] Lv2 숫자의 표현 / JAVA (1) | 2023.02.23 |