[99club/TIL] 6주차 - 목요일 TIL(Today I Learned)

안녕하세요. delay100 입니다!

오늘도 세션 내에 문제를 다 풀지 못했습니다... ㅠㅠ 11시 41분에 겨우 마쳤네요..

99클럽 라이브 세션

---

미들러 문제

---

1번. n^2 배열 자르기

https://school.programmers.co.kr/learn/courses/30/lessons/87390

프로그래머스

 

1. 실패코드 - 실패 & 시간초과 & 런타임에러

 

2중 for문을 이용한 풀이입니다. 실패코드이니 따라하지는 마세요

사실 풀면서도 시간복잡도 관련 문제가 발생할 것이라 예상은 됐지만.. 그래도 풀이한 방법을 적어두겠습니다.

 

풀이 방법은 n번만큼 반복을 합니다. 즉 각 행마다 아래와 같이 반복을 합니다.

i=1일때, 1 /  2, 3, 4 

현재 행값 만큼 행의 값을 반복해줍니다.(1)

남은 행값 만큼 나머지 행의 값을 추가해줍니다(2, 3, 4)

i=2일때,  2, 2 / 3, 4

현재 행값 만큼 행의 값을 반복해줍니다.(2, 2)

남은 행값 만큼 나머지 행의 값을 추가해줍니다(3, 4)

i=3일때,  3, 3, 3 / 4

i=4일때,  4, 4, 4, 4 / 

해당 작업 중, 현재 index값이 left에 도달한 경우 정답리스트(answer리스트)에 값을 넣어줍니다.

 

class Solution {
    public int[] solution(int n, long left, long right) {
        int index = 0;
        int index2 = 0;
        int[] answer = new int[(int)(right - left + 1)];
        
        for(int i=1; i<=n; i++) {
            for(int j=0; j<i; j++) {
                if(index>=left && index<=right) {
                    answer[index2] = i;
                    index2++;
                }
                index++;
            }
            for(int j=i+1; j<=n; j++) {
                if(index>=left && index<=right) {
                    answer[index2] = j;
                    index2++;
                }
                index++;
            }
        }
        return answer;
    }
}

여러 코드들이 실패, 런타임 에러가 발생하는 것을 보고 시간복잡도를 줄여야한다고 생각했습니다.

 

2. 성공 코드

 

2중 for문이아닌 for문 1개로 해결해야겠다고 생각을 했습니다.

혼자서 생각했을 때는 left index에 대해 n으로 나눈 후 +1을 하면 해당 원소의 행을 알 수 있음은 파악했습니다.

그러나 이 행, 열값을 가지고 어떻게 해야하는지에 대한 생각을 하지 못했습니다.

그래서 검색을 해본 결과.. 행, 열 중 최댓값을 구하면 해당 값이 그 위치에 있는 값임을 알 수 있었습니다..

 

프로그래머스 87390번 풀이

import java.io.*;
import java.util.*;

class Solution {
    public int[] solution(int n, long left, long right) {
        int diff = (int)(right - left);
        int[] answer = new int[diff + 1];
        
        for(int i=0; i<(diff + 1); i++) {
            int row = (int)((left+i)/n) + 1; // 행
            int col = (int)((left+i)%n) + 1; // 열
            answer[i] = Math.max(row, col); // 행, 열 중 최댓값
        }
        
        return answer;
    }
}

[참고한 블로그]

 

https://hyojun.tistory.com/entry/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-n2-%EB%B0%B0%EC%97%B4-%EC%9E%90%EB%A5%B4%EA%B8%B0-Java

[프로그래머스] n^2 배열 자르기 - Java

---

2번. k진수에서 소수 개수 구하기

https://school.programmers.co.kr/learn/courses/30/lessons/92335

프로그래머스

아래의 두 가지 작업을 연달아 해주면 됩니다. 자세한 내용은 주석으로 달아두었습니다.

1. n값을 k진수로 변경 -> 소인수분해 이용

2. 숫자들에 대해 소수인지 확인

import java.io.*;
import java.util.*;

class Solution {
    public int solution(int n, int k) {
        int answer = 0;
        StringBuilder sb = new StringBuilder();
    
        // 1. n값을 k진수로 변경 -> 소인수분해 이용
        while(n/k >= 1) {
            sb.insert(0, n%k);
            n /= k;
        }
        sb.insert(0, n%k);
        
        // System.out.println(sb.toString());
        
        String[] list = sb.toString().split("0"); // 0값으로 분리
        
        // 2. 숫자들에 대해 소수인지 확인
        for(int i=0; i<list.length; i++) {
            if(!(list[i].isEmpty())) { // 00처럼 0이 붙어있는 경우 split을 하면 ""값으로 분리가 됨. 해당 사항 제외 
                long a = Long.parseLong(list[i]); // 런타임에러 방지로 Long으로 변환
                boolean isTrue = false;
                for(long j=2; j<=Math.sqrt(a); j++) { // 소수 확인
                    if(a%j==0) { // 제곱근 이하의 수로 나누어 떨어지는 경우 소수x
                        isTrue = true;
                        break;
                    }                    
                }
                if(!isTrue && a > 1) { // 1은 소수가 아니므로 제외
                    // System.out.println(a);
                    answer++;
                }
            }
        }
        
        
        return answer;
    }
}

프로그래머스 92335번 테스트케이스

java로 풀 때, 1번과 11번이 런타임에러가 발생한다면 아래의 코드가 문제일 확률이 큽니다.

// 1번, 11번 런타임에러 코드
int a = Integer.parseInt(list[i]);

// 성공 코드
long a = Long.parseLong(list[i]);

[소인수분해 관련 정보글]

https://m.blog.naver.com/icbanq/221727893563

[진법변환] 2진수,8진수,10진수,16진수 쉽게 변환하는 방법 알아보기!

 

[1, 11번 런타임에러 해결방안 알게된 질문 게시판 게시글]

https://school.programmers.co.kr/questions/48461

프로그래머스

---

+ 비기너 문제

1번.

https://school.programmers.co.kr/learn/courses/30/lessons/138477

프로그래머스

2번.

https://school.programmers.co.kr/learn/courses/30/lessons/86491

프로그래머스

+ 챌린저 문제

1번.

https://school.programmers.co.kr/learn/courses/30/lessons/42860

프로그래머스

2번.

https://school.programmers.co.kr/learn/courses/30/lessons/131129

프로그래머스

---

봐주셔서 감사합니다. 피드백 환영합니다.