[프로그래머스] 행렬의 곱셈

java
posted by 코딩 공부중 2022. 3. 17. 16:59

문제 설명

2차원 행렬 arr1과 arr2를 입력받아, arr1에 arr2를 곱한 결과를 반환하는 함수, solution을 완성해주세요.

제한 조건
  • 행렬 arr1, arr2의 행과 열의 길이는 2 이상 100 이하입니다.
  • 행렬 arr1, arr2의 원소는 -10 이상 20 이하인 자연수입니다.
  • 곱할 수 있는 배열만 주어집니다.
입출력 예arr1arr2return
[[1, 4], [3, 2], [4, 1]] [[3, 3], [3, 3]] [[15, 15], [15, 15], [15, 15]]
[[2, 3, 2], [4, 2, 4], [3, 1, 4]] [[5, 4, 3], [2, 4, 1], [3, 1, 1]] [[22, 22, 11], [36, 28, 18], [29, 20,

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
   
    public int[][] solution(int[][] arr1, int[][] arr2) {
        int[][] answer = new int[arr1.length][arr2[0].length];
        int r = 0;
        for (int k = 0; k < arr1[0].length; k++) {
            for (int i = 0; i < arr1.length; i++) {
                r = arr1[i][k];
                for (int j = 0; j < arr2[0].length; j++) {
                    answer[i][j] += r * arr2[k][j];
                }
            }
        }
        return answer;
    }
}
 cs

 

효율성체크가 없어서 일반적인 행렬의 곱셈 식으로 for문을 세개 써서 풀었다.

스트라센 알고리즘 (Strassen Alogrithm)이라는 분할정복 방법으로 풀면 훨씬 효율적으로 가능하다고 한다,

이 알고리즘을 학습해서 다른 방식으로 풀어봐야할듯

'java' 카테고리의 다른 글

[프로그래머스]로또의 최고 순위와 최저 순위  (0) 2022.03.28
[프로그래머스]피보나치 수  (0) 2022.03.18
[프로그래머스] 숫자의 표현  (0) 2022.03.11
[프로그래머스] 점프와 순간 이동  (0) 2022.02.23
[프로그래머스] 올바른 괄호  (0) 2022.02.22

[프로그래머스] 숫자의 표현

java
posted by 코딩 공부중 2022. 3. 11. 12:08

문제 설명

Finn은 요즘 수학공부에 빠져 있습니다. 수학 공부를 하던 Finn은 자연수 n을 연속한 자연수들로 표현 하는 방법이 여러개라는 사실을 알게 되었습니다. 예를들어 15는 다음과 같이 4가지로 표현 할 수 있습니다.

  • 1 + 2 + 3 + 4 + 5 = 15
  • 4 + 5 + 6 = 15
  • 7 + 8 = 15
  • 15 = 15

자연수 n이 매개변수로 주어질 때, 연속된 자연수들로 n을 표현하는 방법의 수를 return하는 solution를 완성해주세요.

제한사항
  • n은 10,000 이하의 자연수 입니다.
입출력 예nresult
15 4
입출력 예 설명

입출력 예#1
문제의 예시와 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int solution(int n) {
        int answer = 1;
        int count,sum = 0;
        
        for(int i=1; i<n; i++){
           // sum = i+(i+1);
            sum = i+i+1;
            count = i+2;
            while(true){
                if(sum==n){
                    answer++;
                    break;
                }
                if(sum>n){
                    break;
                }
                sum = sum+count;
                count+=1;
            }
            
        }
        return answer;
    }
}
 cs

규칙을 찾아서 푸는 문제

1부터 연속된 수를 합쳤을 때 나오는 값을 생각해보니 규칙을 알 수 있었다.

ex)

1,3,6,10,15...

2,5,9,14,20...

3,7,12,18,25...

 

'java' 카테고리의 다른 글

[프로그래머스]피보나치 수  (0) 2022.03.18
[프로그래머스] 행렬의 곱셈  (0) 2022.03.17
[프로그래머스] 점프와 순간 이동  (0) 2022.02.23
[프로그래머스] 올바른 괄호  (0) 2022.02.22
[프로그래머스] 땅따먹기  (0) 2022.02.16

[프로그래머스] 점프와 순간 이동

java
posted by 코딩 공부중 2022. 2. 23. 17:55

문제 설명

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.

  • 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
  • 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
  • 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

제한 사항
  • 숫자 N: 1 이상 10억 이하의 자연수
  • 숫자 K: 1 이상의 자연수
입출력 예Nresult
5 2
6 2
5000 5
입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동합니다. 이때 1 칸을 앞으로 점프하면 위치3으로 이동합니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 3) x 2 이동할 수 있으므로 위치 6에 도착합니다. 이 경우가 건전지 사용량이 가장 적으므로 2를 반환해주면 됩니다.

입출력 예 #3
위와 같은 방식으로 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;
 
public class Solution {
    static int result = 0;
    
    
    public int solution(int n) {
        int ans = 0;
        
        while(n!=0){
            if(n%2!=0){    //n을 나눈 값이 떨어지지않으면 점프
                n=n/2;
                ans++;
            }else{
                n=n/2;
            }
        }
        
        return ans;
    }
}
 cs

조금만 생각하면 간단하게 풀리는 문제

'java' 카테고리의 다른 글

[프로그래머스] 행렬의 곱셈  (0) 2022.03.17
[프로그래머스] 숫자의 표현  (0) 2022.03.11
[프로그래머스] 올바른 괄호  (0) 2022.02.22
[프로그래머스] 땅따먹기  (0) 2022.02.16
[프로그래머스] 괄호 회전하기  (0) 2022.02.16

[프로그래머스] 올바른 괄호

java
posted by 코딩 공부중 2022. 2. 22. 18:02

문제 설명

괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어

  • "()()" 또는 "(())()" 는 올바른 괄호입니다.
  • ")()(" 또는 "(()(" 는 올바르지 않은 괄호입니다.

'(' 또는 ')' 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

제한사항
  • 문자열 s의 길이 : 100,000 이하의 자연수
  • 문자열 s는 '(' 또는 ')' 로만 이루어져 있습니다.
입출력 예sanswer
"()()" true
"(())()" true
")()(" false
"(()(" false
입출력 예 설명

입출력 예 #1,2,3,4
문제의 예시와 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import java.util.*;
class Solution {
    boolean solution(String s) {
        boolean answer = true;
        int count = 0;
        if(s.charAt(0)==')'){
            return false;
        } else{
            count++;
        }
        for(int i=1; i<s.length(); i++){
            if(i+1 <=s.length()){
               if(s.charAt(i) ==')'){
                   if(count!=0){
                       count--;
                   } else {
                       return false;
                   }
                   
                   
               } else{
                   count++;
               }
            }
        }
        if(count==0){
            return true;
        }else{
            return false;
        }
    }
}
 cs

스택을 써서 풀어야할거 같지만 안써도 된다.

그리고 count를 빼주는 로직에서 한가지 고려해야 할 부분이 더 있음

'java' 카테고리의 다른 글

[프로그래머스] 숫자의 표현  (0) 2022.03.11
[프로그래머스] 점프와 순간 이동  (0) 2022.02.23
[프로그래머스] 땅따먹기  (0) 2022.02.16
[프로그래머스] 괄호 회전하기  (0) 2022.02.16
[프로그래머스]게임 맵 최단거리  (0) 2022.02.15

[프로그래머스] 땅따먹기

java
posted by 코딩 공부중 2022. 2. 16. 17:39

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항
  • 행의 개수 N : 100,000 이하의 자연수
  • 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
  • 점수 : 100 이하의 자연수
입출력 예landanswer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]] 16
입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;
 
class Solution {
    int max(int n,int m){  //최대값을 리턴하는 함수
        
        int max = Math.max(n,m); //max 사용
        
        return max;
    }
    
    int makeMax(int[] arr){
        
        List<Integer> result = new ArrayList<>(); 
        for(int i=0; i<arr.length; i++){
            result.add(arr[i]);
        }
        Collections.sort(result);
        
        return result.get(result.size()-1);
    }
    
    int solution(int[][] land) {
        int answer = 0;
        
        
        for(int j=1; j<land.length; j++){
            //자기 전 행에서 본인의 위치에 있는 값을 제외하고 가장 큰걸 더해준다
            land[j][0] += max(max(land[j-1][1],land[j-1][2]),land[j-1][3]);
            land[j][1] += max(max(land[j-1][0],land[j-1][2]),land[j-1][3]);
            land[j][2] += max(max(land[j-1][0],land[j-1][1]),land[j-1][3]);
            land[j][3] += max(max(land[j-1][0],land[j-1][1]),land[j-1][2]);
        }
        
        answer = makeMax(land[land.length-1]);
 
        return answer;
    }
}
 cs

 

DP(동적계획법)로 푸는 문제

처음 접근할 때 각각의 행에서 값을 선택한 뒤, 다음 행에서 값을 가져올때 밟지 못하는 땅을 제외한 나머지 부분에서 최대값을 더하는 식으로 처리했다.

하지만 이러한 방식으로 풀 경우, 테스트케이스는 통과하지만 채점단계에서는 전부 실패한다.

확인해보니 많은 사람들이 이런 실수를 범하고 헤매는 모습을 보였다.

동적계획법을 사용하여 풀어야 한다는 것을 알았고 이에 대해 잘 정리해놓은 블로그가 있어서 참고했다.

https://shanepark.tistory.com/183

 

피보나치 수열과 프로그래머스 땅따먹기 문제로 알아보는 Dynamic Programming (동적 프로그래밍)

https://programmers.co.kr/learn/courses/30/lessons/12913 자세한 문제는 programmers를 통해 확인 해 주세요. 문제 땅따먹기라고 하지만, 우리가 알고있는 땅따먹기와는 거리가 있습니다. 차라리 어렸을 적 하..

shanepark.tistory.com

DP로 문제를 풀면 쉽게 해결할 수 있다.

 

'java' 카테고리의 다른 글

[프로그래머스] 점프와 순간 이동  (0) 2022.02.23
[프로그래머스] 올바른 괄호  (0) 2022.02.22
[프로그래머스] 괄호 회전하기  (0) 2022.02.16
[프로그래머스]게임 맵 최단거리  (0) 2022.02.15
[프로그래머스] 영어 끝말잇기  (0) 2022.02.15

[프로그래머스] 괄호 회전하기

java
posted by 코딩 공부중 2022. 2. 16. 17:08

문제 설명

다음 규칙을 지키는 문자열을 올바른 괄호 문자열이라고 정의합니다.

  • (), [], {} 는 모두 올바른 괄호 문자열입니다.
  • 만약 A가 올바른 괄호 문자열이라면, (A), [A], {A} 도 올바른 괄호 문자열입니다. 예를 들어, [] 가 올바른 괄호 문자열이므로, ([]) 도 올바른 괄호 문자열입니다.
  • 만약 A, B가 올바른 괄호 문자열이라면, AB 도 올바른 괄호 문자열입니다. 예를 들어, {} 와 ([]) 가 올바른 괄호 문자열이므로, {}([]) 도 올바른 괄호 문자열입니다.

대괄호, 중괄호, 그리고 소괄호로 이루어진 문자열 s가 매개변수로 주어집니다. 이 s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항
  • s의 길이는 1 이상 1,000 이하입니다.
입출력 예sresult
"[](){}" 3
"}]()[{" 2
"[)(]" 0
"}}}" 0
입출력 예 설명

입출력 예 #1

  • 다음 표는 "[](){}" 를 회전시킨 모습을 나타낸 것입니다.
xs를 왼쪽으로 x칸만큼 회전올바른 괄호 문자열?
0 "[](){}" O
1 "](){}[" X
2 "(){}[]" O
3 "){}[](" X
4 "{}[]()" O
5 "}[](){" X
  • 올바른 괄호 문자열이 되는 x가 3개이므로, 3을 return 해야 합니다.

입출력 예 #2

  • 다음 표는 "}]()[{" 를 회전시킨 모습을 나타낸 것입니다.
xs를 왼쪽으로 x칸만큼 회전올바른 괄호 문자열?
0 "}]()[{" X
1 "]()[{}" X
2 "()[{}]" O
3 ")[{}](" X
4 "[{}]()" O
5 "{}]()[" X
  • 올바른 괄호 문자열이 되는 x가 2개이므로, 2를 return 해야 합니다.

입출력 예 #3

  • s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

입출력 예 #4

  • s를 어떻게 회전하더라도 올바른 괄호 문자열을 만들 수 없으므로, 0을 return 해야 합니다.

※ 공지 - 2021년 4월 16일 테스트케이스가 추가되었습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
import java.util.*;
 
class Solution {
    String make(String s, int cnt){
        String tmp = "";
        String tmp2 = "";
        if(cnt>0){
          tmp +=s.substring(0,cnt);
        }
        for(int i=cnt; i<s.length(); i++){
            tmp2 += s.substring(i,i+1);
        }
        tmp2+=tmp;
        check(tmp2);
        
        return tmp2;
    }
    
    int check(String tmp){
        Stack<Character> stack = new Stack<>();
        if(tmp.charAt(0)=='}'||tmp.charAt(0)==')'||tmp.charAt(0)==']'){
            System.out.println("실패 ");
            return 0;
        }else {
            stack.push(tmp.charAt(0));
        }
        
        for(int i=1; i<tmp.length(); i++){
            if(stack.size()>0){
                if(stack.peek()=='['){
                    if(tmp.charAt(i)==']'){
                        stack.push(tmp.charAt(i));
                        stack.pop();
                        stack.pop();
                    }else {
                        stack.push(tmp.charAt(i));
                    }
                } else if(stack.peek()=='('){
                    if(tmp.charAt(i)==')'){
                        stack.push(tmp.charAt(i));
                        stack.pop();
                        stack.pop();
                    }else {
                        stack.push(tmp.charAt(i));
                    }
                }else if(stack.peek()=='{'){
                     if(tmp.charAt(i)=='}'){
                        stack.push(tmp.charAt(i));
                        stack.pop();
                        stack.pop();
                    }else {
                        stack.push(tmp.charAt(i));
                    }
                } else {
                   System.out.println("실패 ");
                   return 0;
                }
            }else{
                stack.push(tmp.charAt(i));
            }
        }
        if(stack.size()==0){
            System.out.println("성공 ");
            return 1;
        } else{
            System.out.println("실패 ");
            return 0;
        }
        
    }
    
    public int solution(String s) {
        int answer = 0;
        check(make(s,0));   
        for(int i=0; i<s.length(); i++){
            answer+=check(make(s,i));   
        }
        
        return answer;
    }
}
 cs

스택을 이용해 해결

효율성검사가 따로 없어서 그냥 모든 조건을 확인해봄

'java' 카테고리의 다른 글

[프로그래머스] 올바른 괄호  (0) 2022.02.22
[프로그래머스] 땅따먹기  (0) 2022.02.16
[프로그래머스]게임 맵 최단거리  (0) 2022.02.15
[프로그래머스] 영어 끝말잇기  (0) 2022.02.15
[프로그래머스] 카카오 1차 - 캐시  (0) 2022.02.14

[프로그래머스]게임 맵 최단거리

java
posted by 코딩 공부중 2022. 2. 15. 17:14
문제 설명

ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다.

지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다.

위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다.
아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다.

  • 첫 번째 방법은 11개의 칸을 지나서 상대 팀 진영에 도착했습니다.
  • 두 번째 방법은 15개의 칸을 지나서 상대팀 진영에 도착했습니다.

위 예시에서는 첫 번째 방법보다 더 빠르게 상대팀 진영에 도착하는 방법은 없으므로, 이 방법이 상대 팀 진영으로 가는 가장 빠른 방법입니다.

만약, 상대 팀이 자신의 팀 진영 주위에 벽을 세워두었다면 상대 팀 진영에 도착하지 못할 수도 있습니다. 예를 들어, 다음과 같은 경우에 당신의 캐릭터는 상대 팀 진영에 도착할 수 없습니다.

게임 맵의 상태 maps가 매개변수로 주어질 때, 캐릭터가 상대 팀 진영에 도착하기 위해서 지나가야 하는 칸의 개수의 최솟값을 return 하도록 solution 함수를 완성해주세요. 단, 상대 팀 진영에 도착할 수 없을 때는 -1을 return 해주세요.

제한사항
  • maps는 n x m 크기의 게임 맵의 상태가 들어있는 2차원 배열로, n과 m은 각각 1 이상 100 이하의 자연수입니다.
    • n과 m은 서로 같을 수도, 다를 수도 있지만, n과 m이 모두 1인 경우는 입력으로 주어지지 않습니다.
  • maps는 0과 1로만 이루어져 있으며, 0은 벽이 있는 자리, 1은 벽이 없는 자리를 나타냅니다.
  • 처음에 캐릭터는 게임 맵의 좌측 상단인 (1, 1) 위치에 있으며, 상대방 진영은 게임 맵의 우측 하단인 (n, m) 위치에 있습니다.
입출력 예mapsanswer
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11
[[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1
입출력 예 설명

입출력 예 #1
주어진 데이터는 다음과 같습니다.

캐릭터가 적 팀의 진영까지 이동하는 가장 빠른 길은 다음 그림과 같습니다.

따라서 총 11칸을 캐릭터가 지나갔으므로 11을 return 하면 됩니다.

입출력 예 #2
문제의 예시와 같으며, 상대 팀 진영에 도달할 방법이 없습니다. 따라서 -1을 return 합니다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;
 
class Solution {
    
    int[] dx = {0, 1, 0, -1};
    int[] dy = {-1, 0, 1, 0};
    
    void bfs(int x, int y, int[][] maps, int[][] visited){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = 1;
        
        // 큐가 빌 때까지 반복
        while(!queue.isEmpty()) {
            int[] current = queue.remove();
            int cX = current[0];    //현재 위치
            int cY = current[1];
            for(int i = 0; i < 4; i++){
                int nX = cX + dx[i];
                int nY = cY + dy[i];
                if(nX < 0 || nX > maps.length-1 || nY < 0 || nY > maps[0].length-1)
                    continue;
                if(visited[nX][nY] == 0 && maps[nX][nY] == 1){
                    visited[nX][nY] = visited[cX][cY] + 1;
                    queue.add(new int[]{nX, nY});
                }
            }
        }
    }
    
    public int solution(int[][] maps) {
        int answer = 0;
       
        int[][] visited = new int[maps.length][maps[0].length];
        
        bfs(0,0,maps,visited);
        
        answer = visited[maps.length-1][maps[0].length-1];
        
        if(answer == 0){
            answer = -1;
        }
        
        return answer;
    }
}
 cs

bfs로 문제를 풀었음

해결 방법을 찾는데 오래 걸려 검색 동원함

bfs 학습 필요

'java' 카테고리의 다른 글

[프로그래머스] 땅따먹기  (0) 2022.02.16
[프로그래머스] 괄호 회전하기  (0) 2022.02.16
[프로그래머스] 영어 끝말잇기  (0) 2022.02.15
[프로그래머스] 카카오 1차 - 캐시  (0) 2022.02.14
[프로그래머스] 예상 대진표  (0) 2022.02.14

[프로그래머스] 영어 끝말잇기

java
posted by 코딩 공부중 2022. 2. 15. 17:12

문제 설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

  1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
  2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
  3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
  4. 이전에 등장했던 단어는 사용할 수 없습니다.
  5. 한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

  • 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
  • 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
  • 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
  • 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
  • (계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

제한 사항
  • 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
  • words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
  • 단어의 길이는 2 이상 50 이하입니다.
  • 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
  • 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
  • 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
  • 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.
입출력 예nwordsresult
3 ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"] [3,3]
5 ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"] [0,0]
2 ["hello", "one", "even", "never", "now", "world", "draw"] [1,3]
입출력 예 설명

입출력 예 #1
3명의 사람이 끝말잇기에 참여하고 있습니다.

  • 1번 사람 : tank, wheel, mother
  • 2번 사람 : kick, land, robot
  • 3번 사람 : know, dream, tank

와 같은 순서로 말을 하게 되며, 3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어가 1번 사람이 자신의 첫 번째 차례에 말한 tank와 같으므로 3번 사람이 자신의 세 번째 차례로 말을 할 때 처음 탈락자가 나오게 됩니다.

입출력 예 #2
5명의 사람이 끝말잇기에 참여하고 있습니다.

  • 1번 사람 : hello, recognize, gather
  • 2번 사람 : observe, encourage, refer
  • 3번 사람 : effect, ensure, reference
  • 4번 사람 : take, establish, estimate
  • 5번 사람 : either, hang, executive

와 같은 순서로 말을 하게 되며, 이 경우는 주어진 단어로만으로는 탈락자가 발생하지 않습니다. 따라서 [0, 0]을 return하면 됩니다.

입출력 예 #3
2명의 사람이 끝말잇기에 참여하고 있습니다.

  • 1번 사람 : hello, even, now, draw
  • 2번 사람 : one, never, world

와 같은 순서로 말을 하게 되며, 1번 사람이 자신의 세 번째 차례에 'r'로 시작하는 단어 대신, n으로 시작하는 now를 말했기 때문에 이때 처음 탈락자가 나오게 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;
import java.lang.Math;
class Solution {
    void check(){//끝말잇기를 정상적으로 했는지 체크하는 함수
        
    }
    
    public int[] solution(int n, String[] words) {
        int[] answer = new int[2];
        Stack<String> stack = new Stack<>();
        //queue.add(words[0]);
        int count = 1;  //차례
        int num = 0;    //번호
        
        for(int i=0; i<words.length; i++){
            num++;
           
            if(i==0){
                stack.add(words[i]);
            } else {
                String tmp = stack.peek();
                if(stack.contains(words[i])){
                    //스택에 존재하면 실패
                    count = i;
                    break;
                }
                //stack의 맨 뒷자리와 다음 글자의 앞자리가 일치하는지 확인
                if(tmp.charAt(tmp.length()-1)==words[i].charAt(0)){   
                    //1.일치하는 경우
                    stack.add(words[i]);
                } else {
                    count = i;
                    break;
                    //일치하지 않으면 실패
                }
            }
            if(num == n){
                num = 0;
            }
        }
        
        answer[0] = num;
        answer[1] = (count/n)+1;
        if(stack.size()==words.length){
            //스택에 다 담기면 성공
            answer[0] = 0;
            answer[1] = 0;
        }
        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다. 
       
        return answer;
    }
}
 cs

 

스택을 써서 해결

순서,차례 구하는 부분이 좀 까다로웠음

'java' 카테고리의 다른 글

[프로그래머스] 괄호 회전하기  (0) 2022.02.16
[프로그래머스]게임 맵 최단거리  (0) 2022.02.15
[프로그래머스] 카카오 1차 - 캐시  (0) 2022.02.14
[프로그래머스] 예상 대진표  (0) 2022.02.14
[프로그래머스] 피로도  (0) 2022.02.11

[프로그래머스] 카카오 1차 - 캐시

java
posted by 코딩 공부중 2022. 2. 14. 17:45

캐시

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.
이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.
어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력 형식

  • 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
  • cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
  • cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
  • 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

  • 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

조건

  • 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
  • cache hit일 경우 실행시간은 1이다.
  • cache miss일 경우 실행시간은 5이다.

입출력 예제

캐시크기(cacheSize)도시이름(cities)실행시간

3 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "Jeju", "Pangyo", "Seoul", "NewYork", "LA"] 50
3 ["Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul", "Jeju", "Pangyo", "Seoul"] 21
2 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"] 60
5 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA", "SanFrancisco", "Seoul", "Rome", "Paris", "Jeju", "NewYork", "Rome"] 52
2 ["Jeju", "Pangyo", "NewYork", "newyork"] 16
0 ["Jeju", "Pangyo", "Seoul", "NewYork", "LA"] 25

해설 보러가기

 

카카오 신입 공채 1차 코딩 테스트 문제 해설

‘블라인드’ 전형으로 실시되어 시작부터 엄청난 화제를 몰고 온 카카오 개발 신입 공채. 그 첫 번째 관문인 1차 코딩 테스트가 지난 9월 16일(토) 오후 2시부터 7시까지 장장 5시간 동안 온라인

tech.kakao.com

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import java.util.*;
 
 
class Solution {
    public int solution(int cacheSize, String[] cities) {
        int answer = 0;
        Queue<String> queue = new LinkedList<>();
        
        if(cacheSize!=0){
            for(int i=0; i<cities.length; i++){
                String tmp = cities[i].toLowerCase();
                if(queue.contains(tmp)){
                        //큐에 값이 존재하는 경우
                        queue.remove(tmp);
                        queue.add(tmp);
                        answer+=1;
                } else {
                    queue.add(tmp);
                    if(queue.size()>cacheSize){
                        queue.poll();
                    }
                    answer+=5;
                } 
            }
        } else {
            answer = cities.length * 5;
        }
        return answer;
    }
}
 cs

LRU 알고리즘을 알아야 함

문제에서 값이 존재하는 경우 단순히 맨 앞에 값을 지워주는 것이 아니라

존재하는 값을 지워줘야 함 -> 위 코드상에서 queue remove 부분

'java' 카테고리의 다른 글

[프로그래머스]게임 맵 최단거리  (0) 2022.02.15
[프로그래머스] 영어 끝말잇기  (0) 2022.02.15
[프로그래머스] 예상 대진표  (0) 2022.02.14
[프로그래머스] 피로도  (0) 2022.02.11
[프로그래머스] 최댓값과 최솟값  (0) 2022.02.10

[프로그래머스] 예상 대진표

java
posted by 코딩 공부중 2022. 2. 14. 17:42

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

제한사항
  • N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
  • A, B : N 이하인 자연수 (단, A ≠ B 입니다.)
입출력 예NABanswer
8 4 7 3
입출력 예 설명

입출력 예 #1
첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution
{
    
    public int solution(int n, int a, int b)
    {
        int answer = 1;
        for(int i=n; i>2; i=i/2){
            if(a==b+1||a+1==b){
                if(a<b){
                    if(a%2!=0){
                        break;
                    }
                } else{
                    if(b%2!=0){
                        break;
                    }
                }
            }
            if(a%2==0){
                //짝수
                a=a/2;
            }else{
                a=a/2 + 1;
            }
            if(b%2==0){
                b=b/2;
            }else{
                b=b/2+1;
            }
            answer+=1;
            
        }
        
 
        // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
        System.out.println("Hello Java");
 
        return answer;
    }
}
 cs

a가 짝수이고 b가 홀수인 경우(ex. a = 4 b=5)를 잘 처리하는 것이 중요

'java' 카테고리의 다른 글

[프로그래머스] 영어 끝말잇기  (0) 2022.02.15
[프로그래머스] 카카오 1차 - 캐시  (0) 2022.02.14
[프로그래머스] 피로도  (0) 2022.02.11
[프로그래머스] 최댓값과 최솟값  (0) 2022.02.10
[프로그래머스] 최솟값 만들기  (0) 2022.02.10

티스토리툴바