https://softeer.ai/practice/6287 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai풀이처음에는 BFS를 통해 가장 빠른 조립시간을 구하려 했다. 하지만 BFS로 수행할 시 메모리 초과가 발생했다.풀이방법에 대해 더 생각해보았더니 DP를 사용하여 해당 작업장까지의 최소 조립시간을 구하는 방식으로 풀었다.// 0 코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)..
https://softeer.ai/practice/6294 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai풀이누적합 배열을 사용하여 풀이하였다.코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st = new StringTokenizer(br.readLi..
https://www.acmicpc.net/problem/4920 4920번: 테트리스 게임 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 표의 크기 N이 주어지고, 4 ≤ N ≤ 100을 만족한다. 둘째 줄부터 표에 쓰여 있는 숫자가 주어진다. 숫자는 절댓 www.acmicpc.net 풀이 5가지 조각으로 배치할 수 있는 모든 도형의 경우의 수(총 13가지)를 배열로 지정하여 풀었다. 주의할 점 - n을 입력받을 때와 NxN 표를 입력받을 때 trim()을 해주어야 한다. - 표에 쓰이는 숫자는 절댓값이 1,000,000을 넘지 않는 정수이다. 즉, 음수가 입력될 수 있으므로 초기 max값을 Integer.MIN_VALUE로 초기화한다. 코드 import java.i..
https://www.acmicpc.net/problem/15886 15886번: 내 선물을 받아줘 2 욱제는 구사과의 열렬한 팬이다. 오늘 욱제는 구사과에게 선물()을 전달해주려고 한다. 지난 며칠간의 관찰 끝에 욱제는 구사과의 이동 패턴을 모두 파악했다. 구사과가 있는 곳은 1×N 크기의 직 www.acmicpc.net 풀이 처음 문제를 봤을 때는 BFS 알고리즘을 생각했다. 같은 위치를 다시 방문하면 안되기 때문에 boolean[] visited 방문 배열을 사용해야겠다고 생각했다. 하지만 단순한 방문배열이 아닌, 현재 탐색 단계와 이전 탐색 단계를 구분하는 방문 배열이 필요하다. ex) EEW W EW - 인덱스가 3인 W부터 시작해서 탐색할 때 왼쪽의 EEW와 합쳐진다. 따라서 카운트하지 않는다..
https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 5 ≤ sequence의 길이 ≤ 1,000,000 = 10^6 이기 때문에 O(n) 알고리즘을 사용해야 한다. 따라서 투포인터 알고리즘을 사용하여 문제를 풀었다. 코드 class Solution { public int[] solution(int[] sequence, int k) { int sum = sequence[0]; int i = 0, j = 0; // 답이 [0, 0]인 경우 if..
https://school.programmers.co.kr/learn/courses/30/lessons/42883 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 그리디 알고리즘을 사용하기 위해서는 아래와 같이 2가지 조건을 만족해야 한다. 1) 탐욕 선택 속성(Greedy Choice Property) 2) 최적 부분 구조(Optimal Substructure) 1)은 이전의 선택이 이후에 영향을 주지 않음을 의미하며, 2)는 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다는 것이다. 1개 제거 2개 제거 3개 제거 4개 제거 1924..
https://school.programmers.co.kr/learn/courses/30/lessons/148653 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 처음에는 BFS로 풀었다가 틀린 결괏값이 나와서 의아했는데, 입력값과 출력값을 보니 각 자리 숫자로만 답을 구할 수 있는 것 같아서 로직을 바꿨다. storey % 10으로 한 자리씩 처리하는 로직을 작성하였고, 각 자리 숫자가 5보다 큰 경우, 작은 경우, 같은 경우를 나누어서 처리하도록 하였다. 같은 경우(숫자가 5인 경우)에는 앞 자리 숫자가 5보다 크거나 같은 경우, 작은 경우로 나..
https://school.programmers.co.kr/learn/courses/30/lessons/12941 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 누적값이 최소가 되게 하는 경우를 찾기 위해 다음의 예시를 들어보았다. A: [x, x+1] B: [y, y+1] 1. x*(y+1) + (x+1)*y = xy + x + xy + y = 2xy + x + y 2. xy + (x+1)*(y+1) = xy + xy + x + y + 1 = 2xy + x + y + 1 A: [x, x+k] B: [y, y+m] 1. x*(y+m) + (x+k)*..
https://www.acmicpc.net/problem/9079 9079번: 동전 게임 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 세 줄로 이루어지며, 한 줄에 세 개의 동전모양이 주어지는데, 각각의 동전 표시 사이에는 하나의 공백이 www.acmicpc.net 풀이 모두 같은 면이 보이도록 하는 최소 연산 횟수를 구해야 하기 때문에 BFS를 사용하였다. 또한 이미 탐색했던 상태가 나올 수 있으므로, Map map을 선언하여 (동전상태, 해당 동전상태가 나오기 위한 최소 연산 횟수)를 저장한다. 동전 상태는 다음과 같이 문자열로 저장된다. H T T H T T T H H -> HTTHTTTHH BFS 로직 1. 초기 동전상태를 큐와 Map에 추가한다..
https://school.programmers.co.kr/learn/courses/30/lessons/17684 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 사전 정보를 저장할 Map dict, 정답 숫자들을 저장할 리스트 List answerWords를 생성한다. int cnt는 사전의 색인 번호이며, dict에 단어가 추가될때마다 1씩 증가한다. int cnt = 1; // 사전의 색인 번호 Map dict // 사전 List answerWords // 정답 숫자 리스트 길이가 1인 단어(알파벳)들로 dict 초기화한 후, 아래의 로직대로 d..
https://school.programmers.co.kr/learn/courses/30/lessons/17687 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 숫자를 n진법으로 변환해야 하고, m명 중 p번째로 말할 숫자를 t개 구해야 한다. 숫자를 n진법으로 변환할 때는 Integer.toString(int i, int radix)를 사용하고 m명 중 p번째로 말할 숫자를 구할 때는 (전체 길이 % m == p)인 경우이다. 이 때 m == p일 때는 p를 미리 0으로 변경한다. 또한 Integer.toString()으로 변환하면 문자의 경우 소..
https://school.programmers.co.kr/learn/courses/30/lessons/68645 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 n x n 크기의 2차원 배열을 생성하여, 우하향 대각선 기준으로 아랫부분만 번호를 채운다. int lastNum: 마지막 번호 int[][] arr: 번호를 저장할 2차원 배열 int sequence = 1 -> lastNum int[] dr, int[] dc int dir = 0, 1, 2 int r, c: 현재 위치의 행, 열 번호 로직 while(탈출조건 => sequence == l..