Posted Updated algorithm2 minutes read (About 260 words)

programmers 17687 [3차] n진수 게임

문제

괄호가 바르게 짝지어졌다는 것은 ‘(‘ 문자로 열렸으면 반드시 짝지어서 ‘)’ 문자로 닫혀야 한다는 뜻입니다. 예를 들어
“()()” 또는 “(())()” 는 올바른 괄호입니다.
“)()(“ 또는 “(()(“ 는 올바르지 않은 괄호입니다.
‘(‘ 또는 ‘)’ 로만 이루어진 문자열 s가 주어졌을 때, 문자열 s가 올바른 괄호이면 true를 return 하고, 올바르지 않은 괄호이면 false를 return 하는 solution 함수를 완성해 주세요.

풀이

  1. 시작괄호로 시작하는지 체크
  2. 닫힌괄호가 나올 수 있는 것은 아직 닫히지 않은 시작괄호가 있을 때 뿐임
  3. 이를 startCount 즉 시작괄호로 체크해줌 (==0 이면 모든 시작괄호가 잘 닫혔단 뜻)

코드

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

class Solution {
    boolean solution(String s) {
        boolean answer = true;
        int startCount = 0;

        for(int i=0;i<s.length();i++)
        {
            if(s.charAt(i) == ')')
            {
                startCount++;
            }
            else
            {
                if(startCount < 1)
                {
                    return false;
                }
                startCount--;
            }
        }
        if(startCount != 0)
        {
            answer = false;
        }
        return answer;
    }

}

메모

스택을 사용해서 풀수도 있다는데 참고만 할 것

Posted Updated algorithm12 minutes read (About 1773 words)

프로그래머스 2레벨 77486 다단계 칫솔 판매 JAVA

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/77486

민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, 조직을 운영하던 민호는 조직 내 누가 얼마만큼의 이득을 가져갔는지가 궁금해졌습니다. 예를 들어, 민호가 운영하고 있는 다단계 칫솔 판매 조직이 아래 그림과 같다고 합시다.

그림1.png

민호는 center이며, 파란색 네모는 여덟 명의 판매원을 표시한 것입니다. 각각은 자신을 조직에 참여시킨 추천인에 연결되어 피라미드 식의 구조를 이루고 있습니다. 조직의 이익 분배 규칙은 간단합니다. 모든 판매원은 칫솔의 판매에 의하여 발생하는 이익에서 10% 를 계산하여 자신을 조직에 참여시킨 추천인에게 배분하고 나머지는 자신이 가집니다. 모든 판매원은 자신이 칫솔 판매에서 발생한 이익 뿐만 아니라, 자신이 조직에 추천하여 가입시킨 판매원에게서 발생하는 이익의 10% 까지 자신에 이익이 됩니다. 자신에게 발생하는 이익 또한 마찬가지의 규칙으로 자신의 추천인에게 분배됩니다. 단, 10% 를 계산할 때에는 원 단위에서 절사하며, 10%를 계산한 금액이 1 원 미만인 경우에는 이득을 분배하지 않고 자신이 모두 가집니다.

예를 들어, 아래와 같은 판매 기록이 있다고 가정하겠습니다. 칫솔의 판매에서 발생하는 이익은 개당 100 원으로 정해져 있습니다.

판매원 판매 수량 이익금
young 12 1,200 원
john 4 400 원
tod 2 200 원
emily 5 500 원
mary 10 1,000 원

판매원 young 에 의하여 1,200 원의 이익이 발생했습니다. young 은 이 중 10% 에 해당하는 120 원을, 자신을 조직에 참여시킨 추천인인 edward 에게 배분하고 자신은 나머지인 1,080 원을 가집니다. edward 는 young 에게서 받은 120 원 중 10% 인 12 원을 mary 에게 배분하고 자신은 나머지인 108 원을 가집니다. 12 원을 edward 로부터 받은 mary 는 10% 인 1 원을 센터에 (즉, 민호에게) 배분하고 자신은 나머지인 11 원을 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

그림2.png

그 후, 판매원 john 에 의하여 400 원의 이익이 발생합니다. john 은 10% 인 40 원을 센터에 배분하고 자신이 나머지인 360 원을 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

그림3.png

또 그 후에는 판매원 tod 에 의하여 200 원 이익이 발생하는데, tod 자신이 180 원을, 추천인인 jaimie 가 그 중 10% 인 20 원을 받아서 18 원을 가지고, jaimie 의 추천인인 mary 는 2 원을 받지만 이것의 10% 는 원 단위에서 절사하면 배분할 금액이 없기 때문에 mary 는 2 원을 모두 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

그림4.png

그 다음으로 emily 가 칫솔 판매를 통하여 얻은 이익 500 원은 마찬가지의 규칙에 따라 emily 에게 450 원, mary 에게 45 원, 그리고 센터에 5 원으로 분배됩니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

그림5.png

마지막으로, 판매원 mary 는 1,000 원의 이익을 달성하고, 이 중 10% 인 100 원을 센터에 배분한 후 그 나머지인 900 원을 자신이 가집니다. 이 상태를 그림으로 나타내면 아래와 같습니다.

그림6.png

위와 같이 하여 모든 조직 구성원들의 이익 달성 현황 집계가 끝났습니다. 지금까지 얻은 이익을 모두 합한 결과를 그림으로 나타내면 아래와 같습니다.

그림7.png

이 결과가 민호가 파악하고자 하는 이익 배분 현황입니다.

각 판매원의 이름을 담은 배열 enroll, 각 판매원을 다단계 조직에 참여시킨 다른 판매원의 이름을 담은 배열 referral, 판매량 집계 데이터의 판매원 이름을 나열한 배열 seller, 판매량 집계 데이터의 판매 수량을 나열한 배열 amount가 매개변수로 주어질 때, 각 판매원이 득한 이익금을 나열한 배열을 return 하도록 solution 함수를 완성해주세요. 판매원에게 배분된 이익금의 총합을 계산하여(정수형으로), 입력으로 주어진 enroll에 이름이 포함된 순서에 따라 나열하면 됩니다.

풀이

약간 구현력문제라는 생각을 한 문제

각 seller에 대해서 문제에서 주어진 것처럼 수익을 배분하는데 이것은 재귀로 구현하였다.

각 seller를 추천한 추천인에 대해서는 enrollIdxMapMap이 누가 누구를 추천했는지 담도록 하였다.

수익을 분배하는 조건 그리고 얼마나 분배할지가 관건인 문제

그리고 seller와 enroll을 어떻게 묶을지를 조금 생각해주어야 하는데

이러한 기반을 쌓고 나면 풀 수 있는 문제🙃

코드

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
import java.util.HashMap;
import java.util.Set;

class Solution{
    
    static int ans[];
    static HashMap<String,Integer> enrollIdxMap = new HashMap<String,Integer>();

    static boolean isDivideAble(int money)
    {
        if(money / 10 >= 1)
        {
            return true;
        }
        return false;
    }

    static void divideToRefer(String curSeller, int curMoney,String[] enroll,String[] referral)
    {
        
        //System.out.println(curSeller + ", " + curMoney + " ing");
        int enrollIdx = getIdxFromEnroll(curSeller);
        if(enrollIdx == -1)
        {
            //System.out.println(curSeller);
            return;
        }
        if(curMoney / 10 < 1)
        {
            //System.out.println(curMoney + " add");
            ans[enrollIdx] += curMoney;
        }
        else
        {
            ans[enrollIdx] += curMoney - curMoney / 10;
            //System.out.println((curMoney - curMoney / 10) + " add");
            divideToRefer(referral[enrollIdx],curMoney / 10,enroll,referral);
        }
    }


    static int getIdxFromEnroll(String curSellerString)
    {
        return enrollIdxMap.get(curSellerString);
    }

    static void setEnrollIdxMap(String[] enroll)
    {  
        for(int i=0;i<enroll.length;i++)
        {
            enrollIdxMap.put(enroll[i],i);
        }
        enrollIdxMap.put("-",-1);
    }

    public int[] solution(String[] enroll, String[] referral, String[] seller, int[] amount) {
        //각 enroll이 받은 수익금
        int[] answer = new int[enroll.length];
        ans = new int[enroll.length];
        setEnrollIdxMap(enroll);
        for(int i=0;i<seller.length;i++)
        {
            int curMoney = amount[i] * 100;
            divideToRefer(seller[i], curMoney, enroll, referral);
        }

        answer = ans;
        return answer;
    }
}

메모

스스로 풀었는가 : ✅

Posted Updated algorithm5 minutes read (About 717 words)

프로그래머스 2레벨 77485 행렬 테두리 회전하기 JAVA

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/77485

rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.

  • x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.

다음은 6 x 6 크기 행렬의 예시입니다.

grid_example.png

이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.

rotation_example.png

행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

풀이

구현력 문제임 시키는대로 하면 됨 라고할뻔 ㅎㅎ;

이차원배열을 조금 다뤄야하는 문제임 각 방향으로 값을 밀어야하는데

중요한 것은 시작에 있는 값을 저장할 것인지 마지막에 있는 값을 저장할 것인지 선택해서

저장한 뒤에 맨 마지막에 저장한 값으로 백업해주어야함 이게 무슨말이냐면

변수 두개의 값을 바꿀려면 tmp변수가 필요하듯이 위 문제에서도 밀리는 부분에 대한 임시 저장을 해주어야한다는 말임

너무 당연한거 아닌가 싶을 수 있는데 당연한거 맞고 뭔가라도 써야할 것 같아서 ㅎㅎ; ✍

코드

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
class Solution {
    static int[][] getInput(int rows,int columns)
    {
        int count = 1;
        int arr[][] = new int[rows+1][columns+1];
        for(int i=1;i<=rows;i++)
        {
            for(int j=1;j<=columns;j++)
            {
                arr[i][j] = count++;
            }
        }
        return arr;
    }
    
    public int[] solution(int rows, int columns, int[][] queries) {
        int[] answer = new int[queries.length];
        int startRow,startCal,endRow,endCal;
        int arr[][] = getInput(rows,columns);
         
        for(int i=0;i<queries.length;i++)
        {
            startRow = queries[i][0];
            startCal = queries[i][1];
            endRow = queries[i][2];
            endCal = queries[i][3];
            //오른쪽으로
            int curCal,curRow = 0;
            int tmp = 0;
            int prev = arr[startRow][startCal];
            int min = 987654321;
            for(curCal = startCal; curCal<=endCal-1;curCal++)
            {
                min = Math.min(min,prev);
                tmp = arr[startRow][curCal+1];
                arr[startRow][curCal+1] = prev;
                prev = tmp;
            }

            //시작 row에서 맨 마지막칸 이전값 저장됨

            for(curRow = startRow; curRow<=endRow-1;curRow++)
            {
                min = Math.min(min,prev);
                tmp = arr[curRow+1][curCal];
                arr[curRow+1][curCal] = prev;
                prev = tmp;
            }
            
            for(;curCal>=startCal+1;curCal--)
            {
                min = Math.min(min,prev);
                tmp = arr[curRow][curCal-1];
                arr[curRow][curCal-1] = prev;
                prev = tmp;
            }
            
            for(;curRow>=startRow+1;curRow--)
            {
                min = Math.min(min,prev);
                tmp = arr[curRow-1][curCal];
                arr[curRow-1][curCal] = prev; 
                prev = tmp;
            }

            answer[i] = min;
        }
        return answer;
    }
}

메모

스스로 풀었는가 : ✅

Posted Updated algorithm5 minutes read (About 718 words)

프로그래머스 2레벨 77484 로또의 최고 순위와 최저 순위 JAVA

문제

링크 : https://programmers.co.kr/learn/courses/30/lessons/77484

로또 6/45(이하 ‘로또’로 표기)는 1부터 45까지의 숫자 중 6개를 찍어서 맞히는 대표적인 복권입니다. 아래는 로또의 순위를 정하는 방식입니다. 1

순위 당첨 내용
1 6개 번호가 모두 일치
2 5개 번호가 일치
3 4개 번호가 일치
4 3개 번호가 일치
5 2개 번호가 일치
6(낙첨) 그 외

로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 발표 후, 민우는 자신이 구매했던 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보고 싶어 졌습니다.
알아볼 수 없는 번호를 0으로 표기하기로 하고, 민우가 구매한 로또 번호 6개가 44, 1, 0, 0, 31 25라고 가정해보겠습니다. 당첨 번호 6개가 31, 10, 45, 1, 6, 19라면, 당첨 가능한 최고 순위와 최저 순위의 한 예는 아래와 같습니다.

당첨 번호 31 10 45 1 6 19 결과
최고 순위 번호 31 0→10 44 1 0→6 25 4개 번호 일치, 3등
최저 순위 번호 31 0→11 44 1 0→7 25 2개 번호 일치, 5등
  • 순서와 상관없이, 구매한 로또에 당첨 번호와 일치하는 번호가 있으면 맞힌 걸로 인정됩니다.
  • 알아볼 수 없는 두 개의 번호를 각각 10, 6이라고 가정하면 3등에 당첨될 수 있습니다.
    • 3등을 만드는 다른 방법들도 존재합니다. 하지만, 2등 이상으로 만드는 것은 불가능합니다.
  • 알아볼 수 없는 두 개의 번호를 각각 11, 7이라고 가정하면 5등에 당첨될 수 있습니다.
    • 5등을 만드는 다른 방법들도 존재합니다. 하지만, 6등(낙첨)으로 만드는 것은 불가능합니다.

민우가 구매한 로또 번호를 담은 배열 lottos, 당첨 번호를 담은 배열 win_nums가 매개변수로 주어집니다. 이때, 당첨 가능한 최고 순위와 최저 순위를 차례대로 배열에 담아서 return 하도록 solution 함수를 완성해주세요.

풀이

최저와 최고 순위를 알고 싶은 것인데 보이지 않는 숫자가 있는 것이니까

최저 순위는 보이지 않는 숫자를 정답과 다른 것으로 하고

최고 순위는 보이지 않는 숫자를 정답과 동일한 것으로 하면 된다.

뭔가 문제는 길어보이지만? 간단히 생각하면 꽤 쉽게 풀리는 문제 ✅

코드

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
class Solution {
    
    static boolean isThereAnswer(int[] win_nums,int val)
    {
        for(int i=0;i<win_nums.length;i++)
        {
            if(win_nums[i] == val)
            {
                return true;
            }
        }
        return false;
    }
    
    
    public int[] solution(int[] lottos, int[] win_nums) {
        int[] answer = new int[2];
        int maxWinRate = 7;
        int minWinRate = 7;
        int zeroCount = 0;
        
        for(int i=0;i<6;i++)
        {
            if(lottos[i] == 0)
            {
                maxWinRate--;
                
            }
            else
            {
                if(isThereAnswer(win_nums,lottos[i]))
                {
                    maxWinRate--;
                    minWinRate--;
                }
            }
                
        }
        if(maxWinRate >= 6)
        {
            maxWinRate = 6;
        }
        if(minWinRate >= 6)
        {
            minWinRate = 6;
        }
        answer[0] = maxWinRate;
        answer[1] = minWinRate;
        
        return answer;
        
        
        
        
    }
}

메모

스스로 풀었는가 : ✅

Follow

Categories

Recents

Archives

Tags

CRF3
algorithm72
book_report2
database1
java26
jpa1
pet project12
pet_project1
retrospect1
springboot3
web3
web pet project2
write3

Subscribe for updates

×