미생물 격리

틀린 이유

  1. 한 칸에 2개 이상의 군집이 들어오면, 그 모든 군집들 미생물 수 중 가장 큰 군집이 그 칸을 차지하게 된다. => 한번에 2,4,5 미생물 군집이 들어올 때, 2, 4 먼저 처리해주고, 5 처리하면 문제 없을 것이라 생각했는데 여기서 틀려버림‼️ 2,4,5를 한번에 비교해서 처리해야한다. 그래서 5인 군집 방향을 따라야하는데, 2,4 를 먼저 처리해버리면 이미 6이 되버린 군집과 5를 비교하기 때문에 방향이 틀려버린다‼️ 따라서 한 칸에 2개 이상의 군집들이 동시에 이동하게 될 경우, 일괄적으로 한번에 처리해야한다‼️ (nx,ny)칸으로 이동하는 군집들을 어떤 저장소에 저장한다. => Map dupMap에 저장! <Key, Value> = <(nx,ny)를 한자리수로 나타낸 정수, 군집 객체>

  2. 반복 횟수 : TC 갯수 T 만큼 N,M,K,Map 생성&저장 메인 로직 solve() 반복 횟수 : T가 아니라 M만큼 반복해야하는데 T 반복문 내에 있어서 틀림.

  3. 객체 타입의 2차원 배열에 군집을 저장한 것까지는 okay. 하지만 2차원 배열을 순회하면서 값의 변경이 일어나기 때문에 2차원 배열이 2개 필요하게 된다! 어느 군집이 map[nx][ny] 로 이동할 때, (nx,ny)가 비지 않았다면 이번 턴에서 새로 이동한 군집인지, 이동하기 전의 군집인지 식별할 수 없다.

  4. K개의 군집을 저장, 관리하는 저장소가 필요하다 : 1차원 배열 또는 큐 K개의 군집들을 순회하면서 군집들 하나씩 이동시켜야하기 때문이다!

  5. 배열 인덱스 초과 이유 : 주어지는 미생물들의 좌표는 0시작 인덱스이기 때문에 따로 -1 안해줘도 되는데도 불구하고 문제 제대로 안 읽고 -1 처리 해서 틀린 것이였음. 타인의 코드를 보고, 입력값에 1을 하지 않았는데도 1부터 N까지가 아니라 0부터 N-1 반복문이 구성된 것을 보고 알아차릴 수 있었다.

  6. 미생물 수가 홀수 일때, 반감하고 난 후의 소수점 자리는 버린다=>Math.floor 처리해주어야한다! 이때, Math.floor()의 매개변수는 double형이기 때문에 (double)로 형변환해주어야한다!

  7. 여전히 에러가 난다. 왜 때문에

보완할 부분

문제를 번역하고, 추상화하는 부분과 자료구조/알고리즘 선택해서 코드로 어떻게 나타낼 것인지 정하는 부분을 분리할 필요가 있다. 전자는 로직을 구체화시키는 부분이고, 후자는 코드로 구현할 부분이다. 이 두개가 섞이면 방향을 잃는다. 로직을 꼼꼼하게 먼저 세우고, 해당하는 코드를 1:1로 매칭하듯이 하면 좋을 것 같다. 문제 처음부터 끝까지 주구장창 적지말고, 문제푸는 데에 필요한 부분만을 key가 되는 것들을 위주로 노트테이킹하도록 하자!!! ex) 문제에서 하라고 하는 연산의 순서, 조건, 변수명, 가로 세로 의미 등

구현 Tip

반대 방향으로 방향 전환이 일어날 때 쉽게 구현하는 방법 일반적으로 상하좌우 = 0123 순서로 방향벡터를 구성하는데, 상하/ 좌우 이렇게 셋트로 생각해서 반전시키는 개념으로 인덱스를 처리하기 위해 상:0,하:2 좌:1,우:3 이런식으로 +2 관계로 만든다. 방향이 4개이기 때문에 +2가 4를 넘어가는 경우를 대비해 %4 처리해주면, dir = (dir+2) %4; 로 해주면 4가지 방향에 대해 반대 방향으로 전환시킬 때 일반화가 가능하다!

리얼 오답노트. 2번째 풀었을 때 틀린 이유

  1. (nx,ny)로 이동할 때 조건 설정 : 빈칸인지 아닌지로 조건을 판단했다. => 중요한 것은 이동하려는 칸이 빈칸인지 아닌지가 아니라 약품처리한 칸인지 아닌지가 관건이다! 약품처리한 칸이라면 별도의 연산을 해주어야하는데, 빈칸인지만 판단하고 그대로 이동하는 처리를 해버리면 안된다!! 그렇기 때문에 조건 판단은 약품처리한 칸인지 아닌지를 확인(판단)해야한다‼️

  2. (nx,ny)에 이미 다른 군집이 있는 경우 : Map에 그 칸의 모든 군집들을 저장해서 일괄적을 처리한다! i) 자신이 처음 도착한 제2의 군집인 경우 : Map.containsKey(key) = false => Map에 <key,value> 쌍을 넣을 때, 현재의 군집만 value 컬렉션에 추가하는 것이 아니라 이미 존재하는 군집도 컬렉션에 추가해야한다‼️(그 칸의 모든 군집들을 일괄적으로 처리하기 때문에 현재 존재하는 군집도 컬렉션에 추가해야한다‼️) ii)이미 다른 군집들이 있고 자신이 n번째로 도착한 군집인 경우: Map.containsKey(key) = true 구현할 때 조건문과 연산 처리를 뒤바꿔버렸다. =>2가지 경우 모두, 현재 군집 클래스 cur의 위치(x,y)를 (nx,ny)로 갱신해야한다. 어쨌든 이동한 것이기 때문에. =>2가지 경우 모두 Map 조회하면서 최댓값 미생물 군집 도출 후, value 컬렉션에서 최댓값 군집을 제외한 나머지 군집들은 삭제처리해야한다!(삭제 처리 : 군집 배열에서 null로 마킹)

  3. 약품처리 구역에 도달했을 경우 : 미생물 반감처리 시, 반감한 미생물 양이 0이 되면 삭제 처리. 미생물 반감처리를 2번 중복해서 해버렸다. => 예외 케이스만 처리한다 : 현재 미생물의 양이 1인 경우, 해당 군집을 삭제한다. => if(cur.micro == 1) { Groups[id] = null;}

    else if(isChemi(nx,ny)) {
  //미생물 수 반감, 삭제처리.
	if(cur.micro>0) {cur.micro /= 2;}
	if(cur.micro == 0) {Groups[id] = null;}
	cur.micro /= 2;//미생물 반감
	cur.dir = (cur.dir+2)%4;//방향 전환
	//위치 갱신:갱신된 방향대로 값 갱신~!
	nx = cur.x+dx[cur.dir];
	ny = cur.y+dy[cur.dir];
	Map[cur.x][cur.y] = 0;
	Map[nx][ny] = id;
}

  4. 궁금했던 사항 : BFS 하던 Map처럼 객체(군집)이 이동할 때, 다음 위치를 갱신할 뿐만 아니라 현재의 위치는 0 또는 null로 갱신해야한다고 생각했다. =>Map 이 존재하는 이유와 생명주기를 생각해보자! Map은 새로 이동하는 군집들의 id를 저장한다! 따라서 현재의 턴에서만 유효하기 때문에, 군집이 이동한 후, 이동하기 전의 위치를 굳이 리셋하는 처리를 안해줘도 되는 것이다!

  5. 클래스 생성할 때, 처리해야할 데이터(속성값) 들이 많기 때문에 편의 메서드를 함께 구현해준다. ① 위치 갱신 메서드 ② 미생물 반감 메서드 ③ 방향 전환 메서드

  6. 입력 받는 중 NoSuchElementException 해결하지 못함... Solution1,2 모두 TC 반복문 내에서 N,M,K 입력받고 바로 연산 수행하도록 구현되어있다. 일단 그대로 따라해보자.

3번째 풀었을 때 틀린 이유

  1. M번 이동을 반복할 때마다 K개의 군집을 이동시킬 때 i번 군집이 삭제됐을 수 있기 때문에 Null 체크를 해줘야하는데 빼먹어서 틀림.

  2. (nx,ny)를 Key로 만들어줘야하는데 군집의 현재위치 cur.x와 cur.y로 Key를 만들어서 Map을 이상하게 만들어줬기 때문에 틀렸다. (nx,ny)에 동시에 존재하는 군집들을 HashMap에 위치 값을 한자리 정수(nx*N+nc)로 나타내고, 이것을 key로 Map을 완성한다. Map에 저장된 각 군집 컬렉션 각각을 조회하면서 각 컬렉션마다 최대 군집을 도출한다. 최대 군집에 미생물 수를 전체 군집 미생물 수 합산해서 넣어주고, 나머지 군집들은 삭제처리한다. => 최대 군집에 미생물 수 합산해서 넣어줄 때, NullPointerException 이 발생했다. 최대 미생물 수를 갖는 군집의 id로 배열을 조회해서 값을 넣어주려고 했는데 말이다. =>해당 id의 군집은 존재하지 않는다는 의미. Map에 key를 이상한 값으로 넣음으로써 Map에는 key와 value가 엉망진창으로 들어가있게 된다. a,b,c 위치에서 각 군집에 (nx,ny)위치로 이동할 경우 (nx,ny) 위치에 대한 <key,value>로 저장해야하는데 a,b,c 각각의 위치에 대한 <key,value>가 들어간다. 최댓값 군집을 찾으려고 할 때, key에 대한 value인 컬렉션에는 아무 군집도 존재하지 않을 수 있다. 그런데 그 컬렉션에서 최댓값 군집을 찾으려고 하고, 그 최댓값 군집에 값을 넣으려고 하기 때문에 존재하지 않는 객체에 접근할 때 NullPointerException이 발생하게 되는 것이다.

  3. 답지를 보고 이해하면 그 문제를 풀었다고 생각하겠지만 착각일 수 있다. 틀린 이유를 모른다면 시험장에 똑같은 문제가 나와도 똑같이 틀릴 것이다. 그렇기 때문에 왜 틀렸는지 정확하게 짚고 넘어가야한다. =>정답은 main에서 반복 연산 구현, 나는 solve함수로 따로 구현해서 반복문 안에 구현. 를 제외하고는 동일한 것 같은데 내 코드가 틀린 이유 정확하게 알아내기.

Previous6. 매칭 점수(문자열 파싱)Next등산로 조성

Last updated