Don't give up!

1068번: 트리 (acmicpc.net) 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 주어진 입력이 i번째 노드의 부모 노드가 몇번째 노드인지 나타내고 있고, 0번째 노드가 루트 노드가 아닐 수 있다는 점, 자식 노드의 수가 정해져 있지 않다는 점을 고려하였습니다. 이를 해결하고자 N개의 노드가 가리키는 부모 노드의 인덱스를 노드 초기화시 저장하고, 모든 노드가 초기화된 후 각 노드가 가리키는 부모 노드의 자식 노드를 추가하도록 하였습니다. 노드의 삭제시 자식 노드..

1051번: 숫자 정사각형 (acmicpc.net) 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 배열에 정사각형 구간을 설정하고, 각 꼭짓점의 문자가 모두 같은지 확인하여야 합니다. 좌상단 좌표를 for문 2개로 x와 y좌표를 선택, 문자가 같은 우상단 좌표를 얻었다면 좌하단, 우하단 좌표의 문자 비교를 통해 조건을 만족하는 정사각형 구간을 찾아내고 넓이를 구할 수 있습니다. 코드 import java.io.*; import java.util.*; class Main ..

1089번: 스타트링크 타워 (acmicpc.net) 1089번: 스타트링크 타워 스타트링크 타워는 총 10N개 층이 있는 고층 건물이고, 0층부터 10N-1층으로 번호가 매겨져 있다. 층 번호를 숫자 N개로 표현한다. 숫자 N개로 층 번호를 표시할 수 없는 경우 앞에 0을 채운다. 숫자 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 0~9의 숫자에 해당하는 문자들을 미리 생성한 후, 5줄의 문자열과 비교하여 가능한 숫자들을 찾아낸 후 평균을 낸다면 문제를 해결할 수 있을 것이라고 생각하였습니다. 그러나 가능한 숫자들을 모두 String 또는 Double로 생성하고 평균을 내는 코드에 대해서는 메모리 초과가 발생하였는데, 이를 해결하고자 경우의 수를 모두 저장하는 것이 아닌 각 자리에 대..

코딩테스트 연습 - [1차] 셔틀버스 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr 어떻게 생각하고 문제를 풀었는가? 주어진 타임 테이블로부터 크루들을 셔틀에 배분하는데 있어 필요한 조건은 다음과 같습니다. 1. 크루가 줄을 선 시간이 셔틀의 도착시간보다 늦지 않았는가? 2. 셔틀의 자리가 남아있는가? 1의 조건을 만족하더라도 2의 조건을 만족하지..

1013번: Contact (acmicpc.net) 1013번: Contact 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 전파를 표현하는, { 0, 1 }만으로 이루어진 문자열이 공백 없이 주어진다. 문자열 길이는 (1 ≤ www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? (100+1+|01)+의 패턴을 검사하는 문제이지만 10011001와 같은 입력에 대해서 10011로 패턴을 확인할 것인지, 1001로 패턴을 확인할 것인지에 따라서 결과가 달라질 수 있습니다. 따라서 정규표현식으로 패턴을 확인하기보다 유한 상태 장치를 구현하여 문제를 해결하고자 하였습니다. 코드 import java.io.*; class Main { public s..

1107번: 리모컨 (acmicpc.net) 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? N을 만드는 최소 값을 구하기 위해서 모든 경우의 수를 조사하는 Brute Force 방식을 사용하고자 하였습니다. 각 케이스에 해당하는 숫자가 에러 버튼을 눌러야 하는 경우를 제외하고 남은 케이스 중 눌러야 하는 버튼의 숫자가 가장 작은 값을 반환한다면 정답을 얻을 수 있을 것이라 생각하였습니다. 코드 import java.io.*; import java.util.*..

1030번: 프렉탈 평면 (acmicpc.net) 1030번: 프렉탈 평면 첫째 줄에 7개의 정수 s, N, K, R1, R2, C1, C2가 주어진다. www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? 각 타일에 검정색이 칠해지기 위한 조건은 다음과 같습니다. 1. 이전 시간에 의해 검정색으로 칠해져 있는가? 2. 현재 시간에서 중앙 KxK의 타일에 위치해 있는가? 시간 0초에서부터 s초까지 진행하며 NxN개의 재귀함수를 호출하고, s초에 도달하였을 때, 타일을 검정색 또는 흰색으로 칠하여 문제를 해결할 수 있다고 생각하였습니다. 조건으로 주어지는 R1,R2,C1,C2의 범위에 해당하는 타일만을 출력해야 하므로 범위에 해당하지 않는 타일에 대해서 재귀함수의 작업을 중단한다면 더 빠른 시간내..

코딩테스트 연습 - 표 편집 | 프로그래머스 (programmers.co.kr) 코딩테스트 연습 - 표 편집 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z"] "OOOOXOOO" 8 2 ["D 2","C","U 3","C","D 4","C","U 2","Z","Z","U 1","C"] "OOXOXOOO" programmers.co.kr 어떻게 생각하고 문제를 풀었는가? 문제를 보고 먼저 떠올린 것은 LinkedList입니다. 현재 위치를 Iterator로서 표현하고, 노드와 연결된 노드를 x번 탐색하기만 하면 해결되며, 노드의 연결관계를 변경하기만 하면 삭제와 복구가 해결되므로 문제를 해결할 수 있을 것이라고 생각하였습니다. 코드 import java.util.*;..