문제 해결 방법 문제를 읽자마자 "전체 참가자 Set - 완주자 Set 으로 풀면 되겠다!"고 생각했고 멋지게 틀렸다. 제한 사항에 다음과 같은 문장이 있다. 참가자 중에는 동명이인이 있을 수 있습니다. * Set은 '중복'을 허용하지 않는 자료구조이기 때문에 동명이인 처리가 불가능하다. 내 아이디어는 이렇다. HashMap 를 생성하여 동명이인 수 '1명' 이 되는 사람의 이름을 구하자. 구현 (Java)
Algorithm/Algorithm (문제풀이)
문제 해결 방법 (1) 접두어 -> 길이가 짧을 수록 접두어 Matching 될 확률이 증가함 -> Sort 아이디어 떠올림. (2) 이중 For loop 반드시 첫자리 원소가 접두어인 것이 아니라 모든 원소가 서로 접두어 관계를 갖지 않는지 확인해야할 필요가 있음. 실수 (1) break break문은 하나의 Loop 만을 탈출한다는 사실을 망각하고 다음과 같이 작성했었다. 이중 for loop 안에서의 break은 2번째 loop은 탈출하지 못한다. 물론 정답을 도출해 내는데는 영향을 미치지 않지만 Time Complexity 증가의 원인이 된다. (2) compare 오름차순 정렬을 전화번호의 '길이'를 기준으로 시도하기 위해 compare 함수를 다음과 같이 작성했었다. 근데 요놈이 효율성 검사에..
문제 문제 이해하기 여타 다른 문제와 입력값이 좀 다른데 다른 문제는 보통 graph matrix를 제시하고 1,0으로 vertex가 존재하는지 존재하지 않는지를 표현한다면 이 문제는 adjacecy matrix를 아예 입력값으로 제시한다. 때문에 다음과 같이 해석했다. (0)번 노드 기준 (1)번 노드 기준 (2)번 노드는 아무런 노드와도 연결되지 않았다. (2번 행 또는 열에서 자기 자신을 제외한 모든 원소 0) (3)번 노드 기준 따라서 위와 같은 4*4 인접 행렬이 주어졌을때 return 값 (그래프 수)는 2가된다. 해결 방법 방문 여부를 keep하는 visited[]행렬 대신 BFS로 방문하며 방문했던 노드의 자리를 0값으로 대치하여 모든 행렬의 원소가 0이될 때까지 BFS의 호출 수를 증가시..
문제 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 해결 방법 행렬에 1로 되어있는 영역 (Graph) 갯수를 구하는 문제 BFS로 풀이한다. 노드간 연결을 수행할 때 양방향으로 해야하는지 단방향으로 해도 되는지 판단한다. 연결 대상 탐색은 우-하방향으로 하고 연결은 양방향 (우-좌, 하-상) 다 수행한다. 구현 [OrganicCabbage.kt] [main.kt]
문제 아이디어 총 단지수 == Graph 갯수 단지 내 집의 수 == Graph 내 노드(Vertex) 수 출력으로 요구하는 값만 봐고 DFS & BFS가 떠올랐다. 총 단지수 => main 에서 DFS 호출 수 단지 내 집의 수 => 한 DFS 내 재귀 호출 수 그래프 연결작업 => 행렬 전체를 돌며 '오른쪽, 아래'로 연결된 [행번호,열번호] 양방향 연결 리스트 추가 약간 헷갈렸던 것이 단지 내 집의 수 (DFS내 재귀 호출 수 카운트) 하는 부분이었다. DFS 코드 // main에서 마지막 argument로 DFS 호출 횟수를 keep하는 변수를 넘겨서 fun dfs (rowIndex: Int, colIndex: Int, callCount: Int) { //start vertex 는 0,0 가정 상..
문제 아이디어 정점, 간선 단어를 보자마자 '그래프'? 연결 요소 == 이어진 그래프를 의미한다. BFS or DFS를 떠올린다. 나는 BFS를 선택했다. 모든 노드(정점) 목록을 원소로 갖는 집합(Set)을 두고 한 번의 BFS마다 생기는 그래프를 전체 집합에서 제외시키는 방식으로 풀이했다. (전체 집합이 공집합이 될 때까지 Loop) 실수 undirected graph (무방향 그래프) 인것을 확인하지 않고 단방향 연결 리스트로만 체크하다가 틀려버렸다. 구현 [Graph.kt] import java.util.* import kotlin.collections.ArrayList class Graph(private val vertexNumber: Int) { val vertexSet : Set = (1 ...
