>알고리즘 문제
1. 문제
테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.
- 조각은 한 번에 하나씩 채워 넣습니다.
- 조각을 회전시킬 수 있습니다.
- 조각을 뒤집을 수는 없습니다.
- 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.
다음은 퍼즐 조각을 채우는 예시입니다.
위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.
이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.
- 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
- 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.
다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.
최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.
현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.
제한사항
- 3 ≤ game_board의 행 길이 ≤ 50
- game_board의 각 열 길이 = game_board의 행 길이
- 즉, 게임 보드는 정사각 격자 모양입니다.
- game_board의 모든 원소는 0 또는 1입니다.
- 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
- 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
- table의 행 길이 = game_board의 행 길이
- table의 각 열 길이 = table의 행 길이
- 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다.
- table의 모든 원소는 0 또는 1입니다.
- 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
- 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
- game_board에는 반드시 하나 이상의 빈칸이 있습니다.
- table에는 반드시 하나 이상의 블록이 놓여 있습니다.
2. 솔루션
class Solution {
fun solution(game_board: Array<IntArray>, table: Array<IntArray>): Int {
var answer: Int = 0
val size=table.size
val gamePiece=BFS(0,game_board)
val tablePiece=BFS(1,table)
val gamePieceWithRotationIdx=Array(gamePiece.size){HashSet<List<Int>>()}
val tablePieceIdx=tablePiece.map{indexing(it,size)}
for(i in 0..gamePiece.size-1){
for(j in 0..3){
gamePieceWithRotationIdx[i]+=indexing(gamePiece[i],size)
rotation(gamePiece[i])
}
}
val isUsed=BooleanArray(gamePieceWithRotationIdx.size){false}
for(i in tablePieceIdx){
for((idx,j) in gamePieceWithRotationIdx.withIndex()){
if(isUsed[idx]) continue
var flag=false
for(k in j){
if(i==k&&!isUsed[idx]){
flag=true
answer+=i.size
isUsed[idx]=true
break
}
}
if(flag) break
}
}
return answer
}
}
fun indexing(piece:Piece, size:Int):List<Int>{
val result=HashSet<Int>()
val visited=HashSet<Block>()
val q=ArrayDeque<Pair<Int,Block>>()
q.addLast(Pair(0,piece.blocks[0]))
visited+=piece.blocks[0]
while(q.isNotEmpty()){
val (idx,b)=q.removeFirst()
result+=idx
for(i in 0..3){
b.adj[i]?.let{
if(!visited.contains(it)){
when(i){
0 -> q.addLast(Pair(idx-size,it))
1 -> q.addLast(Pair(idx+1,it))
2 -> q.addLast(Pair(idx+size,it))
else -> q.addLast(Pair(idx-1,it))
}
visited+=it
}
}
}
}
return result.sorted().let{it.map{b -> b-it[0]}}
}
fun blockRotation(block:Block){
block.adj.also{
val tmp=it[0]
it[0]=it[1]
it[1]=it[2]
it[2]=it[3]
it[3]=tmp
}
}
fun rotation(piece:Piece){
for(i in piece.blocks){
blockRotation(i)
}
}
fun BFS(type:Int, arr:Array<IntArray>):ArrayList<Piece>{
val size=arr.size
val visited=BooleanArray(size*size){false}
val result=ArrayList<Piece>()
for(i in arr.indices){
for(j in arr.indices){
if(arr[i][j]!=type){
visited[i*size+j]=true
}
}
}
val q=ArrayDeque<Triple<Int,Block,Piece>>()
var initIdx=0
for(i in visited.indices){
if(!visited[i]){
visited[i]=true
initIdx=i
break
}
}
val piece=Piece()
val block=Block()
piece.blocks+=block
result+=piece
q.addLast(Triple(initIdx,block,piece))
val dx=listOf(0,0,1,-1)
val dy=listOf(1,-1,0,0)
while(q.isNotEmpty()){
val (idx,b,p)=q.removeFirst()
val x=idx/size
val y=idx%size
for(i in 0..3){
val nx=x+dx[i]
val ny=y+dy[i]
if(nx !in 0..size-1||ny !in 0..size-1) continue
val nextIdx=nx*size+ny
if(!visited[nextIdx]){
visited[nextIdx]=true
val newB=Block()
p.blocks+=newB
when(i){
0 ->{
b.adj[2]=newB
newB.adj[0]=b
}
1 ->{
b.adj[0]=newB
newB.adj[2]=b
}
2->{
b.adj[1]=newB
newB.adj[3]=b
}
else->{
b.adj[3]=newB
newB.adj[1]=b
}
}
q.addLast(Triple(nextIdx,newB,p))
}
}
if(q.isEmpty()){
for(i in visited.indices){
if(!visited[i]){
visited[i]=true
val piece=Piece()
val block=Block()
piece.blocks+=block
result+=piece
q.addLast(Triple(i,block,piece))
break
}
}
}
}
return result
}
class Block( ){
val adj:MutableList<Block?> =mutableListOf(null,null,null,null)//위 오른 아래 왼
}
class Piece(){
val blocks=ArrayList<Block>()
}-BFS로 각 Piece들을 구함
-table과 game에 대한 piece모음을 구함
-game에 대하여 각 piece에 대해 rotation을 돌린 경우도 모아둠
-각 piece에 대해 indexing을 하여 결과를 비교함.
>특강
1. Room: 스마트폰 내장 DB에 데이터 저장을 위한 라이브러리
1)세가지 요소
-Database:DB객체를 만들기 위한 추상 클래스
-Entity: table
-DAO: 쿼리
-DB는 Application의 Context가 필요
@Context받는것 유의점: Context는 받은 스코프의 수명이 끝나면 context도 파기됨
=>프래그먼트에서 받으면 프래그먼트 수명이 끝나면 context도 파기됨
=>그때문에 DB는 Application에서 받는게 좋음
=>받는 방법은 Application class를 만들어서 그 안에 public인 applicationContext변수를 선언해둔다.
=넣을때는 requireContext()?.applicationContext as ~applicationContext
-entity는 유니크 아이디가 필요
=>유니크한 프로퍼티위에 어노테이션을 primaryKey를 넣으면 됨. 없으면 autogenerate=true로
-Room은 Date타입이 적용이 안되므로 Long타입으로 바꿔주는 converter를 추가해야함 =>데이터베이스에 @TypeConverters로 적용
-DB도 코루틴에서 사용할거면 Dao에서 쿼리 메소드를 suspend로 만들기
-데이터베이스 객체를 생성하고 쿼리 쓰는건 코루틴에서 하기
@viewModel은 View의 context를 가지면 안됨 =>둘은 라이프사이클이 다르므로 메모리누수가 발생.
=>필요하면 어플리케이션 컨텍스트를 제공
@유의점:Adapter역시도 뷰이기 때문에 비즈니스 로직을 뷰모델이나 유스케이스로 최대한 빼줘야 한다.
@viewModels<뷰모델타입> 과 activityViewModels의 차이점
=>viewModels는 해당 viewModel을 초기화 하는 Component의 라이프사이클을 따름
=>ActivityViewModels는 root Activity의 LifeCycle을 따름
=>즉, 위에 것은 component가 프래그먼트먼 오너가 프래그먼트가 되어 해당 라이프사이클을 따름.
=>오너가 같은 동일타입 뷰모델은 한 인스턴스가 공유되는 상태이다.
@인터페이스를 이용하여 데이터 동기화
1) 데이터 변경할 인터페이스 생성
2) 컨테이너 역할을 하는 액티비티가 인터페이스 상속후 메소드 오버라이드.
=>첫번째 프레그먼트가 컨텍스트를 인터페이스로 타입변환하여 받은뒤에 해당 메소드로 값 변경
=>바뀐데이터를 액티비티가 저장
3) 두번째 프래그먼트 생성시 바뀐 데이터를 건네줌
interface LikeUserEvent{
fun like(item:User)
}
class MainActivity: AppCompatActivity(), LikeUserEvent{
private var favoerite:User? = null
override fun onCreate(saveInstanceState:Bundle?){
.
.
.
suppporFragmentManager.beginTransaction().
replace(
R.id.container,
secondFragment.newInstance(favorite)
)
.commit()
.
.
.
override fun like(item:User){
favorite = item
}
}
class FirstFragment: Fragment(){
private var likeUserEvent : LikeUserEvent? = null
override fun onAttach(context:Context){
super.onAttach(context)
likeUserEvent = context as LikeUserEvent
}
override fun onViewCreated(view:View, savedInstanceState: Bundle?){
//likeuser메소드 활용 코드
}
.
.
.
}