솧로그

https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 투포인터 문제로 주의할 점은 다음과 같다. 최대 초밥 종류의 개수를 구해야하므로, 굳이 k 미만의 접시를 고를 필요가 없으며, 정확히 k개의 접시를 고르면 된다. 즉, 투포인터보다 슬라이딩 윈도우로 푸는 것이 더 적합하다! (start와 end가 함께 이동하며 그 범위가 k로 유지) 먹은 초밥을 배열로 관리한다(eat[30] = 1이면, 30번의 초밥을 1개..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 이 문제의 핵심은, 섬들의 가장자리에서 bfs로 바다를 탐색하면 된다. 그러다가 다른 섬을 만났을 때 이동한 카운트가 가장 작은 것이 정답이다. 이렇게 푸는데 있어서 흐름은 다음과 같다. 우선 각 섬들을 bfs해서 각 섬들에 번호를 매겨주어야 한다(2, 3, 4, ...). 이는 나중에 바다를 탐색하다가 섬에 닿았을 때 시작 섬과 도착 섬이 같은 섬인지 아닌지를 구분하기 위함이다. 또 한번 각 섬들을 ..

https://school.programmers.co.kr/learn/courses/30/lessons/92335 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 위 문제를 풀 때 소수인지 판단하는 메소드를 다음과 같이 구현했었다. 그런데 시간 초과가 났다. public boolean isPrime(long num) { for (int i = 2; i < num; i++) { if (num % i == 0) { return false; } } return true; } 만약 100이 소수인지 판단한다고 가정하자. 100의 약수는 [1, 2, 4, 5, 10..

https://school.programmers.co.kr/learn/courses/30/lessons/42627# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 모든 작업들의 평균 작업시간을 작게 만들어야 하는 문제이다. 운영체제에서 CPU 스케줄링에서 배운 최단작업 우선 스케줄링 기법(SJF)이 생각났는데, 그대로 하면 된다! 아이디어를 떠올리는 건 괜찮았는데, 구현이 어려웠고 자꾸 8번과 18번 테스트 케이스에서 실패해서 고생한 문제이다. 주요 포인트는 다음과 같다. 현재 시간까지 들어온 작업들을 큐에 넣는다. 그런데 이때 매개변수로 주어지는 job..

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이동 가능한 모든 경로 중 알파벳 순서가 앞서는 경로를 return하면 된다. 그리고 모든 항공권을 사용해야 한다. 따라서 dfs를 사용했다. 그리고 dfs 중간에 usedTicket[i] = false로 초기화해줘야 한다. 예를 들어 JFK를 먼저 방문했으면 그 다음 경로에서는 JFK를 방문하지 못하도록 방문처리를 해줬지만, 다른 공항을 먼저 방문한 후의 경로에서는 JFK를 방문할 수 있어야 하..

https://www.acmicpc.net/problem/1082 1082번: 방 번호 첫째 줄에 N이 주아진다. 둘째 줄에는 공백으로 구분된 P0, ..., PN-1이 주어진다. 마지막 줄에는 M이 주어진다. www.acmicpc.net 그리디 문제로, 주요 포인트는 다음과 같다. 가격이 싼 숫자를 우선으로 골라야 많은 숫자를 구매할 수 있어서 자릿수가 길어진다! 그런데 가격이 가장 싼 숫자가 0(인덱스가 0)이라면, 맨 앞자리 수가 0이 되어 자릿수랑 무관하게 큰 숫자가 될 수 없다. 따라서 가격이 가장 싼 숫자가 0이라면, 그 다음으로 싼 숫자를 제일 앞에 두고, 나머지 자릿수는 가장 싼 숫자를 둔다. 반면 가격이 가장 싼 숫자가 0이 아니라면, 해당 숫자를 최대한 많이 고른다. 위 과정으로 최대한..

https://www.acmicpc.net/problem/1034 1034번: 램프 첫째 줄에 N과 M이 주어진다. N은 행의 개수이고, M은 열의 개수이다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 램프의 상태가 주어진다. 1이 켜져있는 상태이고, 0이 꺼져 www.acmicpc.net 처음에는 완전 탐색으로 m개의 열 중 k번 스위치를 눌러 켜진 행의 갯수를 구하려고 했다. 그런데 이렇게 하면 m개의 열 중 중복을 허용하여 k개를 고르는 것이기 때문에 m^k (50 ^ 1000)으로 시간초과가 날 것이다. 주요 포인트는 다음과 같다. 행 단위로 생각해보자. 하나의 행을 모두 1로 만들어야 켜진 행이 된다. (1) 만약 하나의 행에 0의 갯수가 k보다 크면, 그 행은 절대..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 특별한 알고리즘이 필요하지 않은 문제이다. 그런데 자료구조로 스택을 사용해야 한다! 주요 로직은 다음과 같다. 스택이 비어있으면, 답은 0이고 현재 값을 스택에 push한다. 그렇지 않으면, peek한 값과 현재 값을 비교한다. peek한 값이 더 크면, 답은 peek한 값의 인덱스이고 현재 값을 스택에 push한다. 그렇지 않으면, peek한 값을 pop하고 2번으로 돌아간다. 예제 1번의 경..

https://school.programmers.co.kr/learn/courses/30/lessons/150370 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 단순 구현문제이고 레벨 1 문제인데 살짝 헤맸다.. 다른 건 다 간단하고, 주의할 점은 년, 월, 일에 n달을 더하고 비교하는 건데 이를 쉽게 하기 위해 모든 날짜를 일로 변환하면 된다(모든 달은 28일까지 있다고 가정하기 때문에 이렇게 해도 된다). 즉 2022년 1월 1일은 (2022 * 12 * 28) + (1 * 28) + (1)일인 것이다! import java.util.*; // 파기..

https://school.programmers.co.kr/learn/courses/30/lessons/118669 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 출입구를 A, 산봉우리를 B라고 할 때, A -> ... -> B -> ... -> A의 경로로 이동한다. 그리고 가장 작은 intensity를 구하면 된다. 이때 출입구 A -> 산봉우리 B로 이동할 때의 최소 intensity만 구하면 된다. B -> A에서의 최소 intensity는 A -> B로 올라온 경로로 똑같이 내려가면 되기 때문이다. 이렇게 생각하면 별도의 중복 처리 없이 등산코스..