본문 바로가기

알고리즘 공부 및 문제 풀이/프로그래머스(PRO)

 (81)
[pro] 프로그래머스 level3 43163 단어 변환 (Java) - DFS [문제] https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] words 배열을 돌면서 기존 단어 중 알파벳 하나만 바뀌어서 words 배열 안에 있는 단어로 변환 가능하다면, 변환 후 dfs를 다시 호출한다. dfs는 단어가 target 단어와 일치하면 count를 반환한다. [코드] import java.util.*; class Solution { boolean[] visited; int ans = Integer.MAX_VALUE; pu..
[pro] 프로그래머스 level3 49191 순위 (Java) - 플로이드 와샬 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/49191 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] i가 j에게 이겼다면, rank[i][j] = 1, rank[j][i] = -1 을 채운다. 플로이드 와샬 3중 for 문을 돌며, i가 k에게 이겼고, k가 j에게 이겼다면 rank[i][j] = 1, rank[j][i] = -1을 채운다. 자기 자신을 제외한 나머지 선수들과의 배열이 채워져있어서 n-1이라면 순위를 알 수 있다. [코드] class Solution { publ..
[pro] 프로그래머스 level3 60061 기둥과 보 설치 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/60061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 시뮬레이션(구현) 문제. 기둥과 보가 같은 좌표에 설치될 수 있으므로 구현상의 편의를 위해 기둥, 보 배열을 분리해두었다. 1) 기둥을 설치하는 경우. 기둥이 바닥 위에 있거나, 보의 한 쪽 끝 부분 위에 있거나, 또 다른 기둥 위에 있는 조건을 만족하면 설치하고 count를 증가시킨다. 2) 보를 설치하는 경우, 보의 한 쪽 끝 부분이 기둥 위에 있거나, 양쪽 끝 부분이 다른 ..
[pro] 프로그래머스 level3 68646 풍선 터뜨리기 (Java) - 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/68646 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] i번째 풍선이 존재하고, 그 양 옆으로 큰 풍선들을 터뜨려나가면 i번째 풍선 양 옆에는 왼쪽 최솟값을 가진 풍선과 오른쪽 최솟값을 가진 풍선이 남을 것이다. 번호가 더 작은 풍선을 터뜨릴 수 있는 기회는 딱 1번 존재하기 때문에, 만약 양 옆 풍선이 둘 다 i번째 풍선보다 더 작으면 i번째 풍선만 남기는 것이 불가능하다. 하나만 더 크거나 둘 다 크면 남기는 것이 가능하다. 맨 ..
[pro] 프로그래머스 level3 64062 징검다리 건너기 (Java) - 이분탐색 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 징검다리를 건널 수 있는 친구들의 수를 기준으로 이분탐색을 한다. 건널 수 있다면 친구들의 수를 늘리기 위해서 left값을 mid+1로 갱신하고, 건널 수 없다면 친구들의 수를 줄이기 위해서 right값을 mid-1로 한다. 징검다리에 써져있는 숫자보다 친구들의 수가 더 많을 경우 숫자가 0보다 작아져 건널 수 없으므로 skip을 증가시키고, 연속된 skip이 k와 같아지면 건널..
[pro] 프로그래머스 level3 67259 경주로 건설 (Java) - BFS [문제] https://school.programmers.co.kr/learn/courses/30/lessons/67259 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] BFS 문제이다. 주의할 점은, 이동 방향을 포함해서 visited를 3차원 배열로 선언한 후, 경주로 건설 비용을 저장해서 더 최소 비용인 경우에만 q에 넣어주어야 한다. 이동 방향을 포함해야 하는 이유는 다음과 같다. 현재 위치 {r, c, 이동 방향}에 대해서 {5,5,동쪽} = 1100, {5,5,남쪽} = 900이라고 가정하자. 만약 2차원 배열을 사용한다면 더 작은 값..
[pro] 프로그래머스 level3 67258 보석 쇼핑 (Java) - 투포인터 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/67258 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 범위를 구하는 문제로, 투포인터를 이용해서 풀 수 있다. 1. 보석의 종류가 총 몇 가지인지 알기 위해 중복을 허용하지 않는 HashSet을 이용한다. 2. 포인터를 이동시켜가며 보석의 종류와 개수를 key, value로 저장하기 위해 HashMap을 이용한다. 3. left, right 변수를 이용해 투포인터를 이동시킨다. map의 size와 set의 사이즈가 일치하면 모든 종..
[pro] 프로그래머스 level2 67257 수식 최대화 (Java) - 브루트포스, dfs [문제] https://school.programmers.co.kr/learn/courses/30/lessons/67257 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 먼저 피연산자와 연산자를 분리해서 List에 넣은 후, 모든 연산자의 우선순위 순열에 대해 값을 계산해준다. +, *, - 3가지 연산자에 대해서 가능한 우선순위는 3!=6가지이다. dfs를 통해 이에 대한 순열을 구할 수 있다. 그 후 연산자 우선순위에 따라서 계산해준 후 최대값을 비교해서 얻어낸다. [코드] import java.util.*; class Solution { s..

티스토리툴바