구현 쉽지만 수학 문제 퀴즈 같은 구현[자바 코테 준비 5일차]

1.

로직이 특별한게 없는 간단한 구현 문제이다.

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

연습을 통하여 20분 안으로 작성하는것이 목표이다 . 

 

1. "OSO" 와 같은 문자열에서 'S' 은  split 하지 말고 charAt(index) 로 접근하자.

 

@Test
void sol3(){

    String[] park = {"SOO","OXX","OOO"};
    String[] routes ={"E 2","S 2","W 1"};

    System.out.println(Arrays.toString(sol3(park,routes)));
}
public int[] sol3(String[] park, String[] routes) {
    int[] answer = new int[2];
    int sx = 0;
    int sy = 0;

    int n = park[0].length();
    int m = park.length;

    for (int y = 0; y < m; y++) {
        for (int x = 0; x < n; x++) {
            if (park[y].charAt(x) == 'S') {
                sx = x;
                sy = y;
                break;
            }
        }
    }

    for (String cmdScript : routes) {
        String[] cmd = cmdScript.split(" ");
        int orx = sx;
        int ory = sy;

        for (int i = 0; i < Integer.parseInt(cmd[1]); i++) {
            int nx = sx;
            int ny = sy;

            switch (cmd[0]) {
                case "E" -> nx++;
                case "W" -> nx--;
                case "S" -> ny++;
                case "N" -> ny--;
            }

            if (nx < 0 || nx >= n || ny < 0 || ny >= m || park[ny].charAt(nx) == 'X') {
                sx = orx;
                sy = ory;
                break;
            } else {
                sx = nx;
                sy = ny;
            }
        }
    }

    answer[0] = sy;
    answer[1] = sx;
    return answer;
}

 

문제: https://school.programmers.co.kr/learn/courses/30/lessons/12924

프로그래머스

brutal 하게 1 부터 쭉 더 하고 , 2부터 더하고 

 

문제 조건  n : N  <= 10_000 , 

O( N^2 ) : 

@Test
void sol4(){

    int n = 15 ;

    int re = solution4(n);
    Assertions.assertEquals(4,re);
}
public int solution4(int n) {
     // 5:48 ~ 04:04
    int answer = 0;
    int[] nums = new int[n] ;
    for(int i =0 ; i < n ;i++) {
        nums[i] = i + 1;
    }

    int tmp = 0 ;
    for(int i =0 ; i < n ;i++) {
        for(int j = i ; j < n ; j++) {
            tmp += nums[j];
            if(tmp == n){
                System.out.println(tmp);
                answer +=1 ;
                tmp = 0 ;
                System.out.println("bereak" + answer);
                break;
            } else if (tmp > n) {
                tmp = 0 ;
                break;
            }
        }
        System.out.println("i" + i);
    }

    return answer;
}

https://school.programmers.co.kr/learn/courses/30/lessons/12985%EF%BB%BF

프로그래머스

어렵지 않다,  패턴을 찾는다...

연속하는 두수가 서로 대결 하니 이를 수적으로 2로 나눈 나며지와 몫을 더했을때 같으면 같은거라고 본다.

@Test
    void sol5(){

        int n = 8;
        int a = 4;
        int b = 7;
        int re = solution5(n,a,b);
        Assertions.assertEquals(3,re);

        n = 6;
        a = 1;
        b = 2;
        re = solution5(n,a,b);
        Assertions.assertEquals(1,re);
    }
    public int solution5(int n, int a, int b) {
        int answer = 0 ;
        //  2 로 나눈 몫 + 나머지 = 다음 그룹
        int flag = 0 ;
        int round = 1 ;
        while (flag == 0) {
            //check same group
            int a_next = (a / 2) + (a % 2);
            int b_next = (b / 2) + (b % 2);

//            int a_head =  a / 2 ;
//            int a_tail =  a % 2 ;
//
//            int b_head =  b / 2 ;
//            int b_tail =  b % 2 ;

            if(a_next == b_next ) {
                flag = 1;
                answer  = round;
            }else {
                round+=1;
                a = a_next;
                b = b_next;
            }

        }
        return answer;
    }

 

 

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

프로그래머스

 

비슷한 접근으로 풀었다 . 예시를 적어보고 패턴을 찾는다.

 

직사각형을 만드는 조건은 가로 세로 곱이 타일 수 인것의 역인 ,  전체 노란 타일 수 에서 1 씩 증가를 시켜 확인한다. 

 

(노란 타일의 가로 세로 길이의 합 + 2) * 2 = 갈색 타일 수 를 찾는 로직을 짠다.

 

@Test
    void sol6(){

        int brown = 10;

        int yellow = 2 ;

        int[] re = solution6(brown,yellow);

        String str = "[4, 3]";

        int[] ans = parseIntegerList(str);

        assertThat(ans).containsExactly(re);

        brown = 8;

        yellow = 1 ;

        re = solution6(brown,yellow);

        str = "[3, 3]";

        ans = parseIntegerList(str);

        assertThat(ans).containsExactly(re);

    }
    public int[] solution6(int brown, int yellow) {
        int [] answer = new int[2];
        // 노란 색 가능한거 , 나누고 각각+1 *2 = brown
        int flag = 0 ;
        int checkT = brown / 2;
        int yCol;
        int yRow;
        while(flag == 0)
        {
            for(int i = 1 ; i<=yellow;i++) {
                if(yellow % i == 0 ) {
                    yCol = i ;
                    yRow = yellow / i;
                    if(yCol > yRow) {
                        flag = 1 ;
                        break;
                    }
                    if( (yCol+ yRow +2) == checkT) {
                        answer[0] = yRow + 2;
                        answer[1] = yCol + 2;
                        return answer;
                    }
                }
            }
            flag = 1 ;
        }

        return answer;
    }
}

 

 

문제가 많은 ? 문제 

 

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

 

프로그래머스

1. brutal

1. 1을 증가 시킨 10진수를 이진 법으로 변환후

2. 0 을 지우고 개수를 확인한다.

3. 비교

-> 효율성 불합격

@DisplayName("next int")
@Test
void sol7(){
    int n = 78;
    int re = solution7(n);

    Assertions.assertEquals(83,re);
    n = 15;
    re = solution7(n);
    Assertions.assertEquals(23,re);
}
public int solution7(int n) {
    int answer = 0 ;
    int flag = 0 ;
    String given = Integer.toBinaryString(n);
    int numberOneGiven = given.replaceAll("0","").length();

    while (flag == 0 )
    {
        n += 1;
        String check = Integer.toBinaryString(n);
        int numberOneCheck = check.replaceAll("0","").length();
        if(numberOneCheck == numberOneGiven) {
            return (n);
        }

    }
    return answer;
}

 

2.  

주어진 수 2 진 수 변환 

 

ex ) 100100110

1 의 개수  0 의 개수 구하고 만들수 있는 모든 경우 만들기,

public int solution7(int n) {
    int answer = 0;
    String given = Integer.toBinaryString(n);
    System.out.println(given);
    int onesCount = given.replaceAll("0", "").length();
    int zerosCount = given.replaceAll("1", "").length();

    List<String> lists = generatePermutations(onesCount, zerosCount);

    TreeMap<Integer, Integer> map = new TreeMap<>();

    int count = 0;
    for (String item : lists) {
        int value = Integer.parseInt(item, 2);
        map.put(value, count);
        count += 1;
    }
    // 모든 entry 출력
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
    }

    int target = n + 1;
    Map.Entry<Integer, Integer> entry = map.ceilingEntry(target);
    if (entry != null) {
        answer = entry.getKey();
    }
    if(answer == 0 ){
        String reg = given.replaceFirst("1","10");
        System.out.println(reg);
        answer =Integer.parseInt(reg, 2);
        return answer;
    }
    return answer;
}

-> 시간 초과 

 

정답 코드 :

 

Integer.bitCount()

 

>>> 정수의 1의 개수를 반환해준다.

 

public int solution7Ans(int n) {
    int bitCount = Integer.bitCount(n);
    while(true){
        if(bitCount == Integer.bitCount(++n)){
            break;
        }
    }
    return n;
}

 

 

오늘의 ,,마지막 문제 ,, 유명한 피보나치 ..

https://school.programmers.co.kr/learn/courses/30/lessons/12945%EF%BB%BF

프로그래머스

일단 설명대로 작성 하는 구현 :

@Test
void sol8(){
    int n = 3;
    Assertions.assertEquals(2,solution8(n));
    n = 5;
    Assertions.assertEquals(5,solution8(n));
}
public int solution8(int n) {
		return fib(n) ;
}
public int fib(int n){
    if(n == 0 ) return 0 ;
    if(n == 1 ) return 1;
    return (fib(n - 1 ) + fib(n - 2))% 1234567);
}

->>> 시간 초과 , 실패 

 

 

수정 코드 :

1. 메모리 측면을 생각해라, -> 네이버 코테 문제랑 유사하게 나머지만 저장 하게 만들어서 메모리 관리를 용의 하게 도와 주게 유도함

public int solution8(int n) {
    int[] fib = new int[ n + 1];
    fib[0] = 0 ;
    fib[1] = 1 ;
    fib[2] = 1 ;
    if (n == 2) {
        return  1 ;
    }
    else {
        for(int i = 2 ;i < n + 1;i++) {
            fib[i] = (fib[i - 1] + fib[i - 2]) % 1234567;
        }
        return fib[n];
    }
}

 

 

IceCube dfs clone coding : 0 과 1 로 이루어진 판에서1  은 칸막이 이고 0으로 이어지는 구역 수를 구하는 문제 

int[][] graph =   {
    {0, 0, 1, 1, 0}
    ,{0, 0, 0, 1, 1}
    ,{1, 1, 1, 1, 1}
    ,{0, 0, 0, 0, 0}
};

int n = 4, m = 5;

@Test
public void iceCubeTest() {

    // quest : 1 은 막혀있고 만들 수 있는 총 얼음의 개수
    int res = 0 ;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // 현재 위치에서 DFS 수행
            if (iceDfs(i, j)) {
                res += 1;
            }
        }
    }
    System.out.println(res); // 정답 출력

}
public Boolean iceDfs(int x, int y ) {
    // out of range
    if (x <= -1 || x >=n || y <= -1 || y >= m) {
        return false;
    }
    // recursion visit graph
    if(graph[x][y] == 0 ) {
        graph[x][y] = 1;
        iceDfs(x - 1, y);
        iceDfs(x, y - 1);
        iceDfs(x + 1, y);
        iceDfs(x, y + 1);
        return true;
    }
    return false;
}