본문 바로가기

Algorithm/Programmers12

[프로그래머스] 스티커 모으기(2) - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/12971 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이원형으로 된 스티커가 있고, 어느 한 칸을 떼면 양 옆의 칸에 있는 스티커는 뗄 수 없다. 이때, 스티커를 떼어 얻을 수 있는 최댓값을 구하는 문제이다. 배열의 길이가 100,000이기 때문에 dp로 푸는 문제였다. 점화식은 다음과 같다.dp[i] = Math.max(dp[i - 1], dp[i - 2] + sticker[i]);바로 이전 스티커를 떼었으면 현재 칸을 뗄 수 없고, 현재칸을 떼려면.. 2024. 5. 19.
[프로그래머스] 징검다리 건너기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이[2, 4, 5, 3, 2, 1, 4, 2, 5, 1]위과 같은 배열으로 징검다리들의 숫자가 입력으로 들어온다. 디딤돌을 밟을때마다 숫자가 1씩 줄어들고, 0인 돌이 있다면 안뛰고 건너뛸 수 있다. 하지만, 입력으로 k가 주어지는데 한번에 k개의 돌만 건너뛸 수 있다. 예를 들어, `[5, 3, 2, 1, 4]` 이러한 배치를 하고있다면 3명이 돌을 건너간 후의 상태는 `[2, 0, 0, 0, 1.. 2024. 5. 19.
[프로그래머스] 주사위 고르기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/258709 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이n개의 주사위를 2명이 나눠가진다. 주사위에 쓰인 수의 구성은 모두 다르다. 나눠 가진 주사위들의 합을 구해 점수가 큰 쪽이 승리하는데, A가 승리할 확률이 높도록 주사위를 나눠야 하는 문제이다. 먼저 주사위를 어떻게 나눌지 완탐했다. getDice()메소드를 만들어 비트마스킹을 이용해 어떤 주사위를 A가 선택할지 정해주었다. 선택이 완료되면 calculateWinRate()메소드를 통해 승률을.. 2024. 5. 19.
[프로그래머스] 표 병합 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/150366 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이union-find를 이용한 구현 문제였다. MERGE명령에 대한 설명을 읽고 union-find를 사용해야겠다고 생각했다. 병합된 셀의 어느 위치를 선택하더라도 병합된 셀로 접근한다는 부분에서 union-find에서 find를 해야겠다는 생각이 들었다. parent 배열을 1차원으로 만들기 위해 2501사이즈의 배열로 만들었다. 표의 크기가 50X50이기 때문에 (r,c)의 좌표를 (r-1)X.. 2024. 5. 18.
[프로그래머스] 양과 늑대 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이늑대의 수가 양의 수 이상이 되면 양들이 다 잡아먹혀서 안된다. 트리의 0번부터 시작해서 양을 늑대보다 많게 하면서 돌아다닌다. 이때 양의 최댓값을 찾아야한다. 이동이 가능한 노드들을 담는 리스트를 만들었다. 특정 노드를 방문 할 때 그 노드의 자식 노드를 리스트에 담고, 해당 노드는 제거해주었다. 이동가능한 리스트를 들고 dfs탐색을 통해 최댓값을 갱신했다. 리스트에서 노드를 제거할 때 Conc.. 2024. 5. 18.
[프로그래머스] 카드 짝 맞추기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/72415 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이4 X 4 크기의 보드에 카드를 뒤집어 짝을 맞춰서 제거해야 한다. 카드 짝이 맞게 2개씩 위치를 저장해놓았다. 순열을 통해 제거할 카드 번호의 순서를 정해놓았다. 정해놓은 순서대로 제거해서 최소 이동을 계산하여 정답을 갱신했다.  메모리: 74.5MB시간: 1.17ms언어: Java 11import java.util.*;class Solution { static class Node { .. 2024. 5. 18.
[프로그래머스] 파괴되지 않은 건물 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이N X M 크기의 영역이 주어지고, 각 영역을 사각형 크기의 영역을 정해 일정 수를 더하고 빼주게 된다. 누적합을 이용하는 문제였다. (a, b) 부터 (c, d) 까지의 사각형에 5씩 더해주기 위해서는arr[a][b] += 5arr[a+1][b+1] += 5arr[a][b+1] -= 5arr[a+1][b] -= 5위처럼 더해주면 된다. 이렇게 수를 저장한 뒤 행마다 왼쪽에서 오른쪽으로 누적합해주.. 2024. 5. 18.
[프로그래머스] 광고 삽입 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/72414 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이시청자의 시청 시작, 종료 시각이 주어지고, 광고 지속 시간이 주어진다. 광고 지속 시간동안 누적 재생 시간이 가장 많은 구간을 골라야 한다. 누적합을 이용했다. 시청 시작시간에 +1 하고, 종료시간에 -1을 해놓고 누적합 배열을 끝까지 가면서 `preSum[i] += preSum[i - 1]` 해줬다. 누적합 배열을 완성한 후, 0 ~ 광고시간 까지를 첫 기준으로 삼아 1씩 늘려가면서 비교하며 .. 2024. 5. 18.
[프로그래머스] 블록 이동하기 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이두 점의 좌표, 방향, 시간을 Node클래스에 담아서 진행했다. 방문처리는 가로를 0, 세로를 1로 놓고 3차원 배열로 처리했다. 이동했을 때 두 점이 모두 방문한 곳이라면 진행시키지 않았다. 귀찮은 구현문제였다.  메모리: 69MB시간: 5.70ms언어: Java 11import java.util.*;class Solution { static class Node { int x1.. 2024. 5. 17.
[프로그래머스] 마법의 엘리베이터 - JAVA https://school.programmers.co.kr/learn/courses/30/lessons/148653 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 풀이주어진 층에서 10의 제곱수만큼 이동할 수 있는 엘리베이터를 최소로 이용하여 0층으로 가야한다. 일의자리부터 보면서 5보다 크면 한자리 올림할 만큼 위로 가주고, 5보다 작으면 0이 되도록 내려간다. 5일경우 다음 자리 수를 봐야하는데 다음 자리 수가 5보다 크면 올림으로 해주고 5보다 작으면 내림으로 해줘야 최소 횟수로 이동할 수 있다.  메모리: 79.3MB시간: 0.04ms언어: Java .. 2024. 5. 17.

티스토리툴바