안녕하세요 오늘은 셋과 맵의 문제 유형을 분석해보는 시간을 갖도록 하겠습니다.
우선 셋을 사용한 문제는 보통 두 집합의 비교를 필요로 하는 문제에서 사용됩니다. 셋의 특성 상 중복을 허용하지 않고 값을 저장하기 때문에 첫 번째 집합을 만족시키는 원소들을 셋에 추가하고 두 번째 집합을 만족시키는 원소들을 셋에서 찾아 로직을 처리하는 방식으로 풀이합니다.
백준 1764(듣보잡) 문제의 경우 듣도 못한 사람의 명단과 보도 못한 사람의 명단이 주어질 때 듣도 보도 못한 사람의 명단을 구하는 문제입니다. 듣도 못한 사람을 셋에 저장한 후 보도 못한 사람이 그 셋에 들어있는 경우 출력하는 방식으로 풀 수 있습니다.
백준 7785(회사에 있는 사람) 문제의 경우 로그가 주어졌을 때 현재 회사에 있는 모든 사람을 구하는 문제입니다. 들어간 사람을 셋에 저장한 후 나간 사람이 있을 경우 셋에서 제거한 후 셋의 크기를 출력하는 방식으로 풀 수 있습니다. 여기서 포인트는 현재 존재하는 사람들을 내림차순으로 보여줘야하기 때문에 자동으로 셋을 정렬해주는 TreeSet을 사용하고 Collections.reverseOrder() 를 이용하여 정렬해주시면 됩니다.
맵을 이용한 문제는 이전 상태가 계속 변동되는 문제에서 사용됩니다. 맵의 특성 상 중복을 허용하지 않고 key-value 형식으로 값을 저장하기 때문에 이전 상태를 key로 하여 상태값을 value에 저장하여 로직을 처리합니다. 배열을 이용한 상태 체크(ex boolean[][] check)의 경우 이전 상태가 계속 변동될 경우 그 값을 계속 불러와야 하기 때문에 특정 경우에서 메모리 초과가 발생할 수 있어 이 경우 맵을 사용하여 상태를 처리합니다.
백준 1302(베스트셀러) 문제의 경우 오늘 하루 동안 팔린 책의 제목이 들어왔을 때 가장 많이 팔린 책의 제목을 출력하는 문제입니다. 맵에 책을 추가하면서 이미 존재한다면 값을 1씩 증가시키고 맵에 저장된 값 중 value가 가장 큰 값을 출력합니다.
백준 1525(퍼즐) 문제의 경우 빈 칸으로 퍼즐을 이동시킬 때 정리된 상태로 만드는 최소 횟수를 구하는 문제입니다. 이전 상태가 계속 바뀌기 때문에 배열을 이용해서 처리하게 되면 메모리 초과가 발생합니다. 따라서 빈 칸을 9로 변경한 후 퍼즐 정답을 "123456789"로 정리하여 현재 퍼즐의 모양을 이 방식대로 변환한 값을 key로, 이동 횟수를 value로 설정하여 bfs로 탐색하여 정답이 되었다면 value값을 리턴하는 방식으로 풀 수 있습니다.
