그림이 있는 문제는 어려워서 조금 쫄았는데요 조금만생각해보면 쉬운 문제였습니다.
갈색과 노란색의 합이 총넓이 이고 이 넓이로 만들수있는 가로와 세로의 경우의 수 중에서
가로-2*세로-2 의 값이 노란색인 녀석 (갈색은 무조건 테두리 1줄만 칠해져있기때문) 을 찾으면 됩니다
class Solution {
public int[] solution(int brown, int yellow) {
int[] answer = {0,0};
//넓이는 노란색+갈색
int area=brown+yellow;
//노란색은 가로-1*세로-1 무조건이다 갈색이 1줄만있다고 문제에 적혀있음
for(int row=area; row>1; row--) {
if(area%row==0) {
int col = area / row;
if((col-2)*(row-2)==yellow) {
//만약 가로-2*세로-2가 노란색과 같다면
answer[0]=row;
answer[1]=col;
return answer;
}
}
}
return answer;
}
}간단합니다.
중복을 확인하기 위해 자료구조 Set를 사용했습니다.
중복인경우와 마지막 단어의 끝글자와 방금말한 단어의 첫문자가 다른경우에 예외처리를 했습니다.
import java.util.*;
class Solution {
public int[] solution(int n, String[] words) {
int[] answer = {0,0};
int number = 1;
int order = 0;
char lastChar = words[0].charAt(0);
Set<String> seenWords = new HashSet<>();
for(int i=0; i<words.length; i++) {
String currentWord = words[i];
if(seenWords.contains(currentWord)) {
answer[0]=(i%n)+1;
answer[1]=(i/n)+1;
break;
}
if(i>0 && currentWord.charAt(0)!=lastChar) {
answer[0]=(i%n)+1;
answer[1]=(i/n)+1;
break;
}
seenWords.add(currentWord);
lastChar = words[i].charAt(currentWord.length()-1);
}
return answer;
}
}마지막 문자를 계속갱신해 다음 단어의 첫문자와 비교했습니다.
배열을 한번 정렬해서 가장 무거운 사람들부터 태운다 그러면서 가장 가벼운 사람도 탈수 있다면 가장 가벼운 사람을 태운다 이를반복하면된다.
import java.util.*;
class Solution {
public int solution(int[] people, int limit) {
int answer = 0;
Arrays.sort(people);
//작은순으로 정렬
int index = 0;
for(int i=people.length-1; i>=index; i--) {
//가장 무거운 사람과 가장 가벼운 사람을 태운다
if(people[i]+people[index]<=limit) {
//가장 무거운 사람과 가장 가벼운 사람이 제한보다 적으면 그다음 가벼운 사람을 태울것이다.
index++;
}
//둘의 합이 제한보다 크다면 가장 무거운사람만 보트를 타고나간다
//구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.
answer++;
}
return answer;
}
}
탐욕 알고리즘 관련 문제들은 정렬과 조합된 문제가 많다고 하니 유의해두자.