[프로그래머스 , 리트코드] 시즌3 n^2 배열 자르기 , 행렬의 곱셈 , 의상 , H-Index , [1차] 캐시 , 기능개발 , 튜플
순서대로..
코딩테스트 연습 월간 코드 챌린지 시즌3 n^2 배열 자르기
left 값 고정
right 값도 고정
i = 1,2,3,...,n 까지
n이 4면 4까지임
1 2 3 4
2 2 3 (4) left = 7
3 3 3 4
4 4 (4) 4 right = 14
4,3,3,3,4,4,4,4 -> 정답
n은 근데 중요하지 않음.. 해당 인덱스 값은 i,j둘 중 큰 값에 + 1이 해당 숫자
(1,0) -> 2인것 처럼 변하지 않음
n : 4
n으로 left를 나눈 몫과 나머지 값을 더하면 해당 값이 됨
7/4 = 1 이고 그리고 7%4 = 3 이여서 ( 몫 , 나머지 ) 큰 값에서 + 1
8/4 = 2 이고 그리고 8%4 = 0 이여서
9/4 = 2 이고 그리고 9%4 = 1 이여서
class Solution {
public int[] solution(int n, long left, long right) {
int[] answer = new int[(int)(right - left + 1)];
int cnt = 0;
for(long i=left; i<=right; i++){
answer[cnt] = (int)(Math.max(i / n , i % n) + 1);
cnt++;
}
return answer;
}
}
// long 타입이 들어와서 int형으로 잘 바꿔줘야 함코딩테스트 연습 > 연습문제 > 행렬의 곱셈
2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수
문제는 이렇게 나와있음 요구사항이 너무 적음 입출력 예시를 보면서 규칙을 찾아야하는 아주 별로인 문제
arr1 하고 arr2를 그려보면
2 3 2 5 4 3 22 22 11
4 2 4 2 4 1 36 28 18
3 1 4 3 1 1 29 20 14
2 3 2 (arr1은 행)
5 2 3 (arr2는 열)
4 4 1
3 1 1
총 반복문은 arr1의 원소 만큼 돌려서 return
class Solution {
public int[][] solution(int[][] arr1, int[][] arr2) {
int row1 = arr1.length; // arr1의 행 개수
int col1 = arr1[0].length; // arr1의 열 개수
int col2 = arr2[0].length; // arr2의 열 개수
int[][] answer = new int[row1][col2]; // 결과 행렬 크기로 초기화
for (int i = 0; i < row1; i++) { // 행에 대해서 반복함 2 3 2
for (int j = 0; j < col2; j++) { // arr2의 열에 대해서 반복 5 2 3 / 4 4 1 등등
for (int k = 0; k < col1; k++) { // 열과 행을 곱해서 값을 담는 부분 하나 필요
answer[i][j] += arr1[i][k] * arr2[k][j];
}
}
}
return answer; // 결과 행렬 반환
}코딩테스트 연습 > 해시 > 의상
뒤에가 key값이 들어오는데
총 key값의 종류들 갯수(모자,가방,신발 -> 3개) 더하기
그리고 key값 조합 앞에 갯수 곱하기 2 * 2 * 1 이런식으로
그럴려면 HashMap써서 담긴 해야함
import java.util.HashMap;
class Solution {
public int solution(String[][] clothes) {
int answer = 1;
HashMap<String,Integer> hs = new HashMap();
for(int i=0; i<clothes.length; i++){
if(hs.containsKey(clothes[i][1])){ // containsKey로 해쉬 확인
hs.put(clothes[i][1] , hs.get(clothes[i][1]) + 1);
}else{
//answer++; // 새로운 값 추가 + 1
hs.put(clothes[i][1] , 1);
}
}
for(int val : hs.values()){
answer *= (val + 1);
}
// 자기 자신만 있는 경우를 위하여 + 1
return answer - 1; // -1을 하는 이유 : 모두 선택하지 않는 경우 뺴기 위함
}
}코딩테스트 연습 > 정렬 > H-Index
import java.util.Arrays;
class Solution {
public int solution(int[] citations) {
Arrays.sort(citations); // 0 1 3 5 6
int answer = citations.length;
for(int i=0; i<citations.length; i++){
int h = answer-i; // 5 4 3 2 1
if(citations[i] >= h){
return h;
}
}
return 0;
}
}코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT > [1차] 캐시
// 처음 도시면 +5 있던거면 +1
// 반복문 한번 돌리면서 +해주면 제일 좋음
// 정렬 후 앞 뒤 똑같으면 +1 하고 다르면 +5 해주는게 제일 효율적?
import java.util.Arrays;
class Solution {
public int solution(int cacheSize, String[] cities) {
Arrays.sort(cities);
System.out.println(Arrays.toString(cities));
int answer = 5;
String tmp = cities[0].toLowerCase();
for(int i=1; i<cities.length; i++){
if (tmp.equals(cities[i].toLowerCase())) {
answer += 1;
} else {
answer += 5;
}
tmp = cities[i].toLowerCase();
}
return answer;
}
}
이러면 캐시크기가 필요없음 .. 캐시 크기로 그 값 담을 수 있는 사이즈
다른 방식으로 풀어야함 3캐시인경우 다시 제주가 나와도 도시이름이
캐시 사이즈가 넘어가면 제주는 없어지기 때문
LRU로 푸는게 가장 오래전에 사용된 항목을 제거해야함
FIFO를 이용해서 제일 처음 들어온게 제일 처음으로 나갈 수 있게 구현해야함
import java.util.LinkedList; // util에 있는 LinkedList 사용
class Solution {
public int solution(int cacheSize, String[] cities) {
int answer = 0;
LinkedList<String> cache = new LinkedList<>();
for(String city : cities){ // cities배열 돌음
city = city.toLowerCase(); // 소문자로 비교
if(cache.contains(city)){ // 캐쉬에 city가 있는지 확인
answer++; // 있으면 캐쉬 히트 +1
}else{
answer+=5; // 없으면 캐쉬 미스 +5
if(cache.size() >= cacheSize && cacheSize > 0){ // 캐쉬 사이즈 초과 시 삭제(캐쉬 처음에 없을 경우 지워버리면 오류 추가만)
cache.removeFirst();
}
cache.addLast(city);
}
}
return answer;
}
}
if(cacheSize == 0){ //캐시 크기가 0이면
return cities.length * 5;
}
구문을 넣어야함 캐시 크기가 0일 경우 removeFirst에 들어가지 않아서 if문에 걸리지 않고, 캐쉬에 계속 Last로 쌓이기 때문
코딩테스트 연습 > 스택/큐 > 기능개발
import java.util.ArrayList;
class Solution {
public int[] solution(int[] progresses, int[] speeds) {
int len = progresses.length;
// 1. 작업량 날짜 구함
int days[] = new int[len];
for(int i=0; i<len; i++){
int mok = 100 - progresses[i];
int remain = (mok + speeds[i] - 1) / speeds[i]; // speeds[i] - 1은 나머지를 구하기 위한 방법
days[i] = remain;
}
ArrayList<Integer> arr = new ArrayList<>();
// 2. 작업량 같으면 묶음해서 Array에 담아줌
int idx = 0; // 총 프로그래스 넘어가지 않게
while(idx < len){
int doday = days[idx]; // 현재 날짜
int cnt = 0;
while(idx < len && doday >= days[idx]){
idx++;
cnt++;
}
arr.add(cnt);
}
int[] answer = new int[arr.size()];
for(int i=0; i<arr.size(); i++){
answer[i] = arr.get(i);
}
return answer;
}
}
// pro 1번은 spd 1번 작업 1 7일하면 100
// pro 2번은 spd 2번 작업 30 하면 3일 100
// pro 3번은 spd 3번 작업 5 하면 9일
// 첫번째 작업이 안끝났으니 2번은 기다렸다가 1번 하고 3번 작업 [ 2 , 1 ] 배포 같이 함
// 몫
// (100-93) / spped = 7
// (100-30) / 30 = 2 ( + 1)
// 나머지 있는 경우 + 1
// (100 - 55) / 5 = 9
// 첫번째 했을 경우를 담아두고 두번째가 그것보다 크지 않으면 같이 배포 클 경우 따로 배포 계속 체크코딩테스트 연습 > 2019 카카오 개발자 겨울 인턴십 > 튜플
import java.util.Set;
import java.util.HashSet;
import java.util.ArrayList;
import java.util.Arrays;
class Solution {
public int[] solution(String s) {
s = s.replace("{","").replace("}",""); // 2,2,1
String[] strList = s.split(",");
System.out.println(Arrays.toString(strList));
int[] answer = new int[0];
return answer;
}
}
좀 어렵다...
다른 풀이 참조
앞에 두개 지우고
만약 1 / 1,2 이렇게 있을 경우 1이 먼저나와야 하고 그다음 2가 나와야함
길이가 적은 배열부터 공통인 것 나오게 함
class Solution {
public int[] solution(String s) {
s=s.substring(1,s.length()-1);
String[] sets = s.split("\\},\\{"); // 특수문자 escape 처리 잘 해줘야함
System.out.println(s);
int[] answer = new int[1];
return answer;
}
}
배열의 출력 크기 초과 됨 --> Sysout 찍어서 메모리 많이 잡아먹었음 하지만 다른 방법으로도 ..
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Arrays;
class Solution {
public int[] solution(String s) {
s=s.substring(2,s.length()-2);
s=s.replace("},{","-");
String[] stList = s.split("-");
Arrays.sort(stList , new Comparator<String>(){
public int compare(String o1 , String o2){
return Integer.compare(o1.length(), o2.length());
}
});
System.out.println(Arrays.toString(stList));
int[] answer = new int[stList.length];
int idx = 0; // 인덱스로 추가하면서 넣음
for(String str : stList){
String[] numbers = str.split(","); // str을 잘라서 넣는다. 2 / 2,1 이런식으로
for(String tup : numbers){ // 2,1
// tup : 2 , tup : 1 , tup : 3
boolean chk = false;
int tupNum = Integer.parseInt(tup);
// 배열에 숫자 있는지 확인
for(int i=0; i<idx; i++){
if(answer[i] == tupNum){
chk = true;
break;
}
}
// 배열에 없으면 추가
if(chk == false){
answer[idx++] = tupNum;
}
}
}
return answer;
}
}
원래 코드 테스트 속도
테스트 1 〉 통과 (0.44ms, 77.1MB)
테스트 2 〉 통과 (0.43ms, 75.3MB)
테스트 3 〉 통과 (0.45ms, 74MB)
테스트 4 〉 통과 (0.62ms, 76.3MB)
테스트 5 〉 통과 (3.63ms, 77.5MB)
테스트 6 〉 통과 (2.49ms, 73.1MB)
테스트 7 〉 통과 (17.33ms, 88.4MB)
테스트 8 〉 통과 (28.66ms, 86.6MB)
테스트 9 〉 통과 (29.86ms, 93.4MB)
테스트 10 〉 통과 (28.34ms, 90.3MB)
테스트 11 〉 통과 (34.69ms, 90.9MB)
테스트 12 〉 통과 (73.70ms, 89.1MB)
테스트 13 〉 통과 (50.41ms, 102MB)
테스트 14 〉 통과 (47.26ms, 109MB)
테스트 15 〉 통과 (0.34ms, 79.1MB)
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Arrays;
class Solution {
public int[] solution(String s) {
s=s.substring(2,s.length()-2);
s=s.replace("},{","-");
String[] stList = s.split("-");
// 길이 순으로 정렬
Arrays.sort(stList, (o1, o2) -> Integer.compare(o1.length(), o2.length()));
// 중복 없는 결과를 담을 ArrayList
ArrayList<Integer> answerList = new ArrayList<>();
for (String str : stList) {
String[] numbers = str.split(",");
for (String tup : numbers) {
int tupNum = Integer.parseInt(tup);
// ArrayList에 숫자가 없는 경우에만 추가
if (!answerList.contains(tupNum)) {
answerList.add(tupNum);
}
}
}
// ArrayList를 배열로 변환
int[] answer = new int[answerList.size()];
for (int i = 0; i < answerList.size(); i++) {
answer[i] = answerList.get(i);
}
return answer;
}
}
ArrayList테스트 속도
테스트 1 〉 통과 (0.93ms, 73.7MB)
테스트 2 〉 통과 (0.83ms, 74.8MB)
테스트 3 〉 통과 (0.50ms, 73.3MB)
테스트 4 〉 통과 (1.01ms, 76MB)
테스트 5 〉 통과 (2.27ms, 73MB)
테스트 6 〉 통과 (3.41ms, 75.7MB)
테스트 7 〉 통과 (22.27ms, 88.4MB)
테스트 8 〉 통과 (48.83ms, 94.2MB)
테스트 9 〉 통과 (17.62ms, 86MB)
테스트 10 〉 통과 (32.42ms, 92.4MB)
테스트 11 〉 통과 (58.38ms, 104MB)
테스트 12 〉 통과 (68.31ms, 105MB)
테스트 13 〉 통과 (59.83ms, 105MB)
테스트 14 〉 통과 (62.98ms, 95.6MB)
테스트 15 〉 통과 (0.47ms, 75MB)
속도는 비슷한 것 같다. 똑같이 O(n)의 복잡도를 사용하는 것이기 때문이다
for문 도는거나 contains로 돌아서 확인하는 것 비슷함
contains메서드 indexOf 메서드를 호출해서 요소의 인덱스를 찾아서 비교
또 새로운 방법을 알려줬는데 그냥 중복제거를 contains로 체크안하고 Set으로 넘김
근데 그럼 어차피 Set도 얘가 중복인지 아닌지 체크하면 오래걸리지않는가?
ArrayList는 순서 가지고 있고 , 중복된 데이터 가능 , index구조로 저장
Set은 순서 X , 중복 X , Hash 테이블 구조
그럼 해시 테이블 왜 중복검사를 더 빨리할 수 있음?
해시 값을 계산하여 테이블의 특정 버킷에 저장됨.
해시 테이블은 평균적으로 O(1) 시간 복잡도로 요소의 포함 여부를 확인할 수 있음.
ArrayList는 O(n)의 시간 복잡도로 각 요소를 순차적으로 비교하지만 HashSet은 직접 계산하여 빠르게 검색함
이렇게 하고보니 무조건 Set을 써야겠다는 생각이 들었음 Set으로 구현해본다.
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Arrays;
import java.util.Set;
import java.util.HashSet;
class Solution {
public int[] solution(String s) {
s=s.substring(2,s.length()-2);
s=s.replace("},{","-");
String[] stList = s.split("-");
// 길이 순으로 정렬
Arrays.sort(stList, (o1, o2) -> Integer.compare(o1.length(), o2.length()));
Set<Integer> ans = new HashSet<>();
for(String str : stList){
String[] numStr = str.split(",");
for(String numEle : numStr){
ans.add(Integer.parseInt(numEle));
}
}
// Set<Integer>를 int[]로 변환
int[] answer = new int[ans.size()];
int idx = 0;
for (Integer num : ans) {
answer[idx++] = num;
}
return answer;
}
}
문제의 요지와 맞지않음. 순서를 가지고 있지 않으니 다시 answer로 변환해서 순서가 필요하므로 Set은 순서가 없어서 안됨.