[5주차_월요일] 놀이기구 탑승

[yeongleej]

• 사이트 : 코드트리(CT)
• 문제: 놀이기구 탑승
• 년도: 2021년

[KodaHye]

🤔 시간복잡도 고려사항

3 <= n <= 20이므로 문제에서 주어진대로 구현해도 시간 충분

💡 풀이 아이디어

각 학생마다 친한 친구를 저장하고, 입력된 학생 순서대로 map에 위치 앉히기

• LinkedHashMap<Integer, HashSet<Integer>> hashMap
  • key: 학생 번호, value: 친한 친구 집합
  • LinkedHashMap이므로 학생이 입력한 순서대로 앉힐 수 있음
• placeKey(int key): 학생을 map에 위치 시키기
  • map을 순차 탐색하며 조건에 맞는 위치 찾기
• getScore()
  • 학생마다 주변에 친한 친구 몇 명있는지 세고, 점수 구하기
  • result += Math.pow(10, likeCnt - 1)

[Jewan1120]

🤔 시간복잡도 고려사항

• 3 ≤ n ≤ 20 → 제한도 넉넉하고 구현 문제라 신경쓰지 않음

💡 풀이 아이디어

• 최적의 자리를 구하는 문제 → 자리 별로 우선순위가 존재하므로 우선순위 큐를 이용
  • 우선순위 비교 구현
• 입장하는 순서에 따라서 비어있는 모든 자리에서의 주변 정보를 계산 후 우선순위 큐에 삽입
• 가장 우선순위가 높은 자리에 학생을 배치

  @Override
  public int compareTo(Node o) {
  if (this.favor != o.favor)
      return o.favor - this.favor;
  else if (this.empty != o.empty)
      return o.empty - this.empty;
  else if (this.y != o.y)
    return this.y - o.y;
  return this.x - o.x;
  }

  행과 열 우선순위를 반대로 적었는데도 통과 되네요..? 테스트 케이스 부족해보입니다...

[yeongleej]

🤔 시간복잡도 고려사항

• n <= 20 => 충분히 작으므로 단순 구현해도 O

💡 풀이 아이디어

• Comparable 이용해서 우선순위 정하기
  • 위치를 나타내는 객체 Pos(x좌표, y좌표, 인접좋아하는사람수, 인접빈칸수)를 선언
  • 인접좋아하는사람수 -> 인접빈칸수 -> 행 -> 열의 우선순위를 설정해서 PriorityQueue에 삽입

    static class Pos implements Comparable<Pos> {
    int x, y, like, empty;
    public Pos(int x, int y, int like, int empty) {
        this.x = x;
        this.y = y;
        this.like = like;
        this.empty = empty;
    }
    @Override
    public int compareTo(Pos other) {
        if(this.like == other.like) {
            if(this.empty == other.empty) {
                if(this.x == other.x) {
                    return this.y - other.y;
                }
                return this.x - other.x;
            }
            return other.empty - this.empty;
        }
        return other.like - this.like;
    }
    }

  • 위의 우선순위를 통해 출력된 칸에 해당 학생 번호 기록
  • findPos(): 빈칸 찾기
  • calLike(): 인접한 좋아하는 사람의 수 카운트
  • calEmpty(): 인접한 빈칸의 수 카운트
  • calScore(): 그래프에 기록된 것을 바탕으로 각 학생의 점수 계산

[baexxbin]

🤔 시간복잡도 고려사항

• 3<= n <= 20
• 조건 널널함

💡 풀이 아이디어

• 조건의 우선순위에 따라 자리에 앉아야함
  • 조건에 해당하는 행, 열, 좋아하는 친구 수, 비어있는 칸을 Node객체로 만들고 우선순위큐로 자리 선정
  • Node객체에서 compareTo로 우선순위 정하기
  • Integer.compare(a, b); a,b : 오름차순 / b,a: 내림차순
• 코드 흐름
  • 초기화
    • emptyCnt 배열: 주위 빈칸 개수 정보
    • 모서리(2), 가장자리 (3), 안쪽(4)로 초기화
    • 이때 처음 자리 선정하기 위해 (4)해당 노드 우선순위큐에 넣기
  • findSit: 전체 배열을 돌며 행, 열, 좋아하는 친구 수, 비어있는 칸 정보 우선순위큐에 넣기
  • checkNxt: 주위 자리에 좋아하는 친구 수 세기
  • fixSit: 자리 선정 후 빈자리 업데이트(emptyCnt)
  • 자리 배정 끝난 후 점수 세기

[icegosimperson]

🤔 시간복잡도 고려사항 n<= 20 -> 주어진 조건으로 구현 가능

💡 풀이 아이디어 주어진 순서대로 학생을 좋아하는 학생 옆에 앉히는 문제

• 학생별 좋아하는 학생 : 크기 고정, 중복X(이거아님) -> ArrayList 사용
• 중복 포함하지 않으려면 Set 사용하기
• Pos 클래스에 compareTo구현하여 우선순위 정렬
• 탐색 방향 : 상하좌우 (맨 처음 값 십자 가운데에)
• PriorityQueue를 사용하여 좌석 선택의 우선순위를 관리하고, 각 학생의 만족도를 계산하여 최종 점수 구함

  문제 이해 못해서 엄청 헤맸었는데, 지영님 코드로 이해하고 공부하고,, 그랬습니다 아직 위치값 객체로 선언하는게 낯서네요,,! compareTo 공부하기

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: 구현
• 시간복잡도: 3 ≤ n ≤ 20 으로 완전탐색 가능

💡 풀이 아이디어

• 한명의 학생이 모든 탑승기구 자리를 순회하며 최적의 자리를 찾기
• 최적의 자리 찾는 방법: 문제에서 요구한 4가지 우선순위에 따라 자리 결정
• 최적의 자리를 찾을 때 마다 해당 위치로 갱신 해주는게 핵심 포인또

4방향 탐색에서 BFS를 생각했는데, 문제의 요구사항에 맞게 구현하기 위해선 완전탐색을 해야했기 때문에 굳이 BFS 로 풀 이유가 없었음