본문 바로가기

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

 (81)
[pro] 프로그래머스 level3 12904 가장 긴 팰린드롬 (Java) [문제] https://school.programmers.co.kr/learn/courses/30/lessons/12904 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 가장 긴 길이부터(s.length()) 처음 시작 인덱스를 달리하며 만들 수 있는 모든 부분 문자열에 대해 팰린드롬인지 확인한다. 단순 for문으로 해결 가능하다. [코드] class Solution { public int solution(String s) { int answer = 0; //가장 긴 팰린드롬의 길이를 return for(int len=s.length(); len..
[pro] 프로그래머스 level3 12938 최고의 집합 (Java) [문제] https://school.programmers.co.kr/learn/courses/30/lessons/12938 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 곱의 크기가 최대가 되기 위한 수들을 생각해보면 규칙을 찾을 수 있다. n=2, s=8이라면 [4, 4]가 최고의 집합이 될 것이다. n=3, s=9라면 [3, 3, 3]이 된다. 그렇다면 n=3, s=11이라면? [3, 4, 4]가 최고의 집합이 된다. s/n을 각 자리에 넣어준 후, 나머지가 있다면 +1씩 한 집합이 최고의 집합이 된다는 것을 알 수있다. 나머지를 한쪽으로 몬..
[pro] 프로그래머스 level3 12979 기지국 설치 (Java) - 그리디 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/12979 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 1동부터 n동까지 돌며 그리디하게 기지국을 설치한다. 만약 이미 설치된 기지국 범위 안에 있다면 기지국을 새로 설치할 필요가 없다. 따라서 기지국의 오른쪽 끝 범위 + 1 위치로 이동한다. 만약 설치된 기지국 범위 안에 없다면 새로 기지국을 설치해야 한다. 따라서 설치개수를 증가시켜 주고 새로 설치한 기지국의 전파 범위 다음 위치로 이동시켜줘야 한다. 이때 범위는 (왼쪽으로 w ..
[pro] 프로그래머스 level3 12927 야근 지수 (Java) - 우선순위 큐 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/12927 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 우선순위 큐를 오름차순 반환하도록 설정한다. 가장 큰 작업량에 대해서 n번 1씩 감소시키면 야근 지수를 최소화할 수 있다. [코드] import java.util.*; class Solution { public long solution(int n, int[] works) { long answer = 0; //야근 피로도를 최소화한 값을 리턴 PriorityQueue pq = ne..
[pro] 프로그래머스 level3 17676 추석 트래픽 (Java) [문제] https://school.programmers.co.kr/learn/courses/30/lessons/17676 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 처리시간이 SS.sss 형태이므로 1000을 곱해 ms 단위로 계산한다. 1초 동안의 처리된 요청을 카운트해야 하는데 처리량이 변하는 경우는 새로운 트래픽이 시작하거나 끝나는 경우이다. 따라서 각 요청에 대해서 트래픽이 시작한 지점을 기준으로 1초, 끝난 지점을 기준으로 1초 요청량을 카운트한 뒤 최대 처리량을 반환하도록 했다. [코드] import java.util.*; cla..
[pro] 프로그래머스 level3 17678 셔틀버스 (Java) - 우선순위 큐 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/17678 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 계산하기 편하도록 도착시각을 모두 분으로 변환하여 우선순위 큐에 넣는다. n번의 셔틀 운행에 대하여 크루가 셔틀 출발 시각 이전에 도착 및 버스 탑승 인원이 남아 탑승가능하다면 탑승시킨다. 이때 탑승한 크루가 마지막 탑승 크루일 수 있으므로 정답을 크루탑승시각-1 로 갱신해준다. 만약 마지막 버스에 자리가 남아있다면 그 버스의 출발시각이 가능한 가장 늦은 도착 시각이 된다. [코..
[pro] 프로그래머스 level3 42893 매칭 점수 (Java) - 문자열, 정규식 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/42893 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 정규식을 이용해서 풀 수 있다. 1) word가 나오는 횟수를 계산해서 기본 점수를 구한다. 이때 주의할 점은 찾은 word 앞, 뒤로 다른 문자가 있으면 안된다. 2) 페이지별 외부 링크 개수를 계산한다. 3) 정규식을 이용하여 링크 점수를 계산한다. Page 별로 url을 파싱해서 저장해놓는데, () 로 묶어서 group화 할 수 있다. 전체 pattern에 일치하는 문자열을..
[pro] 프로그래머스 level3 60063 블록 이동하기 (Java) - BFS, 시뮬레이션 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/60063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 구현이 복잡해진 BFS 문제이다. (N, N)에 도착하는 최단 거리를 반환하는 문제이기 때문에 BFS를 이용해서 풀었다. 고려해야 하는 점은 visited 배열을 3차원으로 선언하여 방문한 상태가 수직, 수평인 경우를 분리해줘야 한다는 것이다. 또한 회전하는 경우 역시 수직인 상태에서 회전하는 경우와 수평인 상태에서 회전하는 경우로 나누어 q에 넣어주었다. 수직인 상태에서 회전한..

티스토리툴바