네발로 코딩하는 포메라니안

문제 https://www.acmicpc.net/problem/10800 10800번: 컬러볼 첫 줄에는 공의 개수를 나타내는 자연수 N이 주어진다(1 ≤ N ≤ 200,000). 다음 N개의 줄 중 i번째 줄에는 i번째 공의 색을 나타내는 자연수 Ci와 그 크기를 나타내는 자연수 Si가 주어진다(1 ≤ Ci ≤ N www.acmicpc.net 풀이과정 풀이 방법이 2가지가 있는데, 우선 구현하는 로직은 같고 정렬할 때 사용하는 방법만 다르다. [방법1]에서는 공의 정보를 모두 받은 후, Arrays.sort를 통해 O(nlogn)이 걸리는 정렬을 수행했고, [방법2]에서는 크기 별로 ArrayList를 만들어서 크기 별로 공을 모아서 사용했다. 공의 최대 가능한 개수에 비해, 크기의 종류가 훨씬 적었기..

문제 https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 풀이 과정 가장 왼쪽, 위쪽에서 출발해서 일반 블럭일 때만 DFS 탐색을 하면, 일반블럭이 무조건 1개 이상인 조건을 만족한다. 탐색 후, (블럭 사이즈가 최대) || (이전 블럭 사이즈와 같고 rainbow블럭의 개수가 같거나 큼)일 때, 가장 큰 블럭 값을 갱신해준다. 가장 큰 블럭은 삭제하면서 -2로 표시한다. import java.io.BufferedReader; import ja..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 1. BFS 탐색으로 퍼즐(remove를 쓰기 위해 LinkedList를 사용)과 빈 칸을 각각 분석한다. 1-1. 블럭의 가장 위쪽에서 가장 왼쪽에 있는 블럭을 (0, 0)으로 맞추어 블럭들의 좌표를 변경한다. - setCenter메서드 2. 각 빈칸에 퍼즐을 넣을 수 있는 지 검사한다. 2-1. 개수가 다르면 return false; 2-2. 개수가 같으면 회전시켜가면서 넣을 ..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/84512 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 과정 처음엔 AEIOU 순서대로 DFS방식을 통해 사전순대로 읽어가면서 해당 문자열을 만나면 return하는 방식이 떠올랐다. 그런데, 굳이 순서대로 다 탐색하는 것보다 몇 번째인지 바로 계산할 수 있는 방식이 있어서 이 방식으로 구현했다. 원래는 O(N)만큼 걸리는 알고리즘을 O(1)으로 구현할 수 있는 것이다. 수식 : 5^(length("AEIOU")-1-i) + sum(1*5^(..

문제 https://www.acmicpc.net/problem/22251 22251번: 빌런 호석 LED를 2개까지 바꿀 수 있을 때, 5층에서 3층, 6층, 8층, 그리고 9층으로 바꿔버릴 수 있다. www.acmicpc.net 풀이 과정 각 수마다 변경될 때 반전이 필요한 횟수를 arr배열에 저장했고, 이 코드는 미리 짜서 돌린후 대입해서 실제 코드에서는 넣지 않았다. 고정적인 값이라서 굳이 계속 돌릴 필요가 없다고 판단했다. DFS를 통해서, 모든 경우의 수를 탐색한다. 여기서 (자리수, 10^(자리수), 현재까지 수, 반전시킨 횟수)를 인자로 넣어서 반전 시킨 횟수도 최대 횟수를 넘지않고, 현재 수가 N층을 넘지 않으면 통과시킨다. 이때 K자리까지 다 탐색했으면 결과+1을 하고 마지막엔 -1을 해..

문제 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 풀이 과정 첫 번째 스위치의 상태가 정해지면, 나머지 전구를 꺼야하는지가 결정된다. 따라서 첫 번째 스위치를 눌렀을 때와 안 눌렀을 때 2가지 경우에 대해 최솟값을 반환한다. 각 스위치를 누를지 말지 결정하는 기준은 자기 앞의 값이 목표 상태와 같은지 보고 결정하면 된다. import java.io.BufferedReader; import java.io.Input..

문제 https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 풀이 과정 코드를 작성하기 전에는 각 문자를 인덱스로 써서 문자별 개수를 cnt하고 이를 비교해야겠다까지 설계하고 시작했다. 하지만, 첫 번째 문자열 길이가 더 큰지, 주어지는 문자열 길이가 더 큰지 등 조건까지 같이 떠올리는 연습이 필요한 것 같다. 아래는 문자열 길이 차이가 2이상이면 비교 연산없이 다음 문자열로 넘어간다. 2미만이면 같은 문자의 개수가 몇 개인지 count하여 주어진 ..

1. 문제 https://www.acmicpc.net/problem/1138 1138번: 한 줄로 서기 첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 www.acmicpc.net 2. 풀이 과정 처음엔 앞에서부터 빈칸을 해당 개수만큼 비워두고 해당 값을 적는 형태로 작성했다. 하지만, 자기보다 큰 수의 개수를 가지고 있기 때문에, 반대로 큰 수부터 보면서 배열의 arr[i]번째에 넣어주는 방식으로도 구현할 수 있었다. import java.io.BufferedReader; import java.io.InputStreamReader; import java...

1. 문제 https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 2. 풀이과정 문제대로 구현하면 되는 문제이고, 톱니바퀴를 회전할 때는 배열의 모든 값을 오른쪽 혹은 왼쪽으로 움직이지 않고 시작 포인트만 변경해서 얼만큼 회전했는지 표현했다. 그리고 가장 왼쪽, 오른쪽의 값은 나머지 연산을 통해 시작에서 각각 2번째, 6번째에 떨어진 값을 반환하도록 했다. import java.io.BufferedReader; import java.io.Inpu..

1. 문제 https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 2. 풀이 과정 처음엔 ArrayList로 구현했다가 N의 범위가 100보다 작아서 2차원 배열이 더 빠를 것 같아서 수정했더니 2배 빨라졌다. 배열의 처음과 끝이 이어져있기 때문에 1번 과정에서의 8방향 탐색은 나머지 연산을 활용했다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.uti..