문제 주소
https://school.programmers.co.kr/learn/courses/30/lessons/17679
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
문제 설명
블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".
같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.
이거 2048같은 거네
만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.
블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.
만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.
위 초기 배치를 문자로 표시하면 아래와 같다.
TTTANT RRFACC RRRFCC TRRRAA TTMMMF TMMTTJ
각 문자는 라이언(R), 무지(M), 어피치(A), 프로도(F), 네오(N), 튜브(T), 제이지(J), 콘(C)을 의미한다
입력으로 블록의 첫 배치가 주어졌을 때, 지워지는 블록은 모두 몇 개인지 판단하는 프로그램을 제작하라.
입력 형식
- 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
- 2 ≦ n, m ≦ 30
- board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.
출력 형식
입력으로 주어진 판 정보를 가지고 몇 개의 블록이 지워질지 출력하라.
입출력 예제
m n board answer
| 4 | 5 | ["CCBDE", "AAADE", "AAABF", "CCBBF"] | 14 |
| 6 | 6 | ["TTTANT", "RRFACC", "RRRFCC", "TRRRAA", "TTMMMF", "TMMTTJ"] | 15 |
예제에 대한 설명
- 입출력 예제 1의 경우, 첫 번째에는 A 블록 6개가 지워지고, 두 번째에는 B 블록 4개와 C 블록 4개가 지워져, 모두 14개의 블록이 지워진다.
- 입출력 예제 2는 본문 설명에 있는 그림을 옮긴 것이다. 11개와 4개의 블록이 차례로 지워지며, 모두 15개의 블록이 지워진다.
제출 코드
import java.util.*;
import java.lang.Math;
class Solution {
public int solution(int m, int n, String[] board) {
int answer = 0;
List<List<Character>> list = new ArrayList<>();
//리스트 초기화
for(int i=0; i<n; i++){
list.add(new ArrayList<>());
}
//리스트에 넣기(세로로)
for(String s : board){
for(int i=0; i<s.length(); i++){
list.get(i).add(s.charAt(i));
}
}
//변화가 있었으면 또 계산하고 아니면 끝남
boolean hasChanged = true;
while(hasChanged){
hasChanged = false;
//지울 인덱스 리스트 Set으로 만듦 중복을 방지하기 위해서
List<PriorityQueue<Integer>> remove = new ArrayList<>();
for(int i=0; i<n; i++){
remove.add(new PriorityQueue<>());
}
//왼쪽줄 1개랑 오른쪽줄 1개랑 가져와서 봄
for(int j=0; j<n-1; j++){
List<Character> left = list.get(j);
List<Character> right = list.get(j+1);
int min = Math.min(left.size(),right.size())-1;
for(int i=0; i<min; i++){
//네개 비교함
char l1 = left.get(left.size()-1-i);
char l2 = left.get(left.size()-1-(i+1));
char r1 = right.get(right.size()-1-i);
char r2 = right.get(right.size()-1-(i+1));
if(l1==l2 && l2==r1 && r1==r2){
hasChanged = true;
remove.get(j).add(left.size()-1-i);
remove.get(j).add(left.size()-1-(i+1));
remove.get(j+1).add(right.size()-1-i);
remove.get(j+1).add(right.size()-1-(i+1));
}
}
}
for(int i=0; i<n; i++){
List<Character> chars = list.get(i);
PriorityQueue<Integer> targets = remove.get(i);
int last = -1;
int diff = 0;
while(!targets.isEmpty()){
int t = targets.poll();
if(t==last){
continue;
}
chars.remove(t-diff);
diff++;
answer++;
last=t;
}
}
}
return answer;
}
}테스트 1 〉 통과 (0.48ms, 74.6MB)
테스트 2 〉 통과 (0.48ms, 79MB)
테스트 3 〉 통과 (0.46ms, 79MB)
테스트 4 〉 통과 (5.45ms, 81.3MB)
테스트 5 〉 통과 (28.48ms, 93.2MB)
테스트 6 〉 통과 (4.24ms, 72.4MB)
테스트 7 〉 통과 (3.39ms, 77.9MB)
테스트 8 〉 통과 (4.93ms, 82.4MB)
테스트 9 〉 통과 (0.71ms, 86MB)
테스트 10 〉 통과 (2.16ms, 75.2MB)
테스트 11 〉 통과 (9.03ms, 75.9MB)
코드 설명
우선 세로로 된 List를 만듦
네개씩 보면서 네개의 알파벳이 같다면 삭제하게 PQ에다 등록함
길이가 짧은 줄의 인덱스만큼 돌려봄
다 돌려본 후에 PQ에서 뽑아서 삭제하는데 이전에 나온 숫자와 같다면 스킵함
풀이과정
import java.util.*;
import java.lang.Math;
class Solution {
public int solution(int m, int n, String[] board) {
int answer = 0;
List<List<Character>> list = new ArrayList<>();
//리스트 초기화
for(int i=0; i<n; i++){
list.add(new ArrayList<>());
}
//리스트에 넣기(세로로)
for(String s : board){
for(int i=0; i<s.length(); i++){
list.get(i).add(s.charAt(i));
}
}
//변화가 있었으면 또 계산하고 아니면 끝남
boolean hasChanged = true;
while(hasChanged){
hasChanged = false;
//지울 인덱스 리스트 Set으로 만듦 중복을 방지하기 위해서
List<Set<Integer>> remove = new ArrayList<>();
for(int i=0; i<n; i++){
remove.add(new HashSet<>());
}
//왼쪽줄 1개랑 오른쪽줄 1개랑 가져와서 봄
for(int j=0; j<n-1; j++){
List<Character> left = list.get(j);
List<Character> right = list.get(j+1);
int min = Math.min(left.size(),right.size())-1;
for(int i=0; i<min; i++){
//네개 비교함
char l1 = left.get(left.size()-1-i);
char l2 = left.get(left.size()-1-(i+1));
char r1 = right.get(right.size()-1-i);
char r2 = right.get(right.size()-1-(i+1));
//System.out.println(l1+","+l2+","+r1+","+r2);
if(l1==l2 && l2==r1 && r1==r2){
hasChanged = true;
remove.get(j).add(left.size()-1-i);
remove.get(j).add(left.size()-1-(i+1));
remove.get(j+1).add(right.size()-1-i);
remove.get(j+1).add(right.size()-1-(i+1));
}
}
}
for(int i=0; i<n; i++){
List<Character> chars = list.get(i);
Set<Integer> targets = remove.get(i);
answer += targets.size();
List<Integer> targetList = new ArrayList<>(targets);
Collections.sort(targetList);
int diff = 0;
for(int t : targetList){
chars.remove(t-diff);
diff++;
}
}
}
return answer;
}
}처음에는 이렇게 Set을 이용해서 중복만 제거하고 풀었는데
모든 테케, 질문하기에 있는 모든 테케가 다 돌아가지만 제출하기의 5번 테케가 실패했다
이유를 몰랐는데 나중에 보니
Set을 List로 변환할때 정렬이 안 되어서 뒤에있는걸 먼저 삭제하고 diff로 ++를 해버리면 저렇게 되는 거였다
import java.util.*;
import java.lang.Math;
class Solution {
public int solution(int m, int n, String[] board) {
int answer = 0;
List<List<Character>> list = new ArrayList<>();
//리스트 초기화
for(int i=0; i<n; i++){
list.add(new ArrayList<>());
}
//리스트에 넣기(세로로)
for(String s : board){
for(int i=0; i<s.length(); i++){
list.get(i).add(s.charAt(i));
}
}
//변화가 있었으면 또 계산하고 아니면 끝남
boolean hasChanged = true;
while(hasChanged){
hasChanged = false;
//지울 인덱스 리스트 Set으로 만듦 중복을 방지하기 위해서
List<Set<Integer>> remove = new ArrayList<>();
for(int i=0; i<n; i++){
remove.add(new HashSet<>());
}
//왼쪽줄 1개랑 오른쪽줄 1개랑 가져와서 봄
for(int j=0; j<n-1; j++){
List<Character> left = list.get(j);
List<Character> right = list.get(j+1);
int min = Math.min(left.size(),right.size())-1;
for(int i=0; i<min; i++){
//네개 비교함
char l1 = left.get(left.size()-1-i);
char l2 = left.get(left.size()-1-(i+1));
char r1 = right.get(right.size()-1-i);
char r2 = right.get(right.size()-1-(i+1));
//System.out.println(l1+","+l2+","+r1+","+r2);
if(l1==l2 && l2==r1 && r1==r2){
hasChanged = true;
remove.get(j).add(left.size()-1-i);
remove.get(j).add(left.size()-1-(i+1));
remove.get(j+1).add(right.size()-1-i);
remove.get(j+1).add(right.size()-1-(i+1));
}
}
}
for(int i=0; i<n; i++){
List<Character> chars = list.get(i);
Set<Integer> targets = remove.get(i);
answer += targets.size();
List<Integer> targetList = new ArrayList<>(targets);
Collections.sort(targetList);
int diff = 0;
for(int t : targetList){
chars.remove(t-diff);
diff++;
}
}
}
return answer;
}
}테스트 1 〉 통과 (0.53ms, 74.4MB)
테스트 2 〉 통과 (0.66ms, 74.5MB)
테스트 3 〉 통과 (0.52ms, 80.6MB)
테스트 4 〉 통과 (4.23ms, 79.2MB)
테스트 5 〉 통과 (40.03ms, 77.8MB)
테스트 6 〉 통과 (7.88ms, 70.4MB)
테스트 7 〉 통과 (4.55ms, 69.4MB)
테스트 8 〉 통과 (4.02ms, 72.1MB)
테스트 9 〉 통과 (0.61ms, 79MB)
테스트 10 〉 통과 (2.02ms, 76.9MB)
테스트 11 〉 통과 (3.75ms, 75MB)정렬해주느라 시간이 좀 오래걸리는 거 같길래 PQ로 바꿨다
import java.util.*;
import java.lang.Math;
class Solution {
public int solution(int m, int n, String[] board) {
int answer = 0;
List<List<Character>> list = new ArrayList<>();
//리스트 초기화
for(int i=0; i<n; i++){
list.add(new ArrayList<>());
}
//리스트에 넣기(세로로)
for(String s : board){
for(int i=0; i<s.length(); i++){
list.get(i).add(s.charAt(i));
}
}
//변화가 있었으면 또 계산하고 아니면 끝남
boolean hasChanged = true;
while(hasChanged){
hasChanged = false;
//지울 인덱스 리스트 Set으로 만듦 중복을 방지하기 위해서
List<PriorityQueue<Integer>> remove = new ArrayList<>();
for(int i=0; i<n; i++){
remove.add(new PriorityQueue<>());
}
//왼쪽줄 1개랑 오른쪽줄 1개랑 가져와서 봄
for(int j=0; j<n-1; j++){
List<Character> left = list.get(j);
List<Character> right = list.get(j+1);
int min = Math.min(left.size(),right.size())-1;
for(int i=0; i<min; i++){
//네개 비교함
char l1 = left.get(left.size()-1-i);
char l2 = left.get(left.size()-1-(i+1));
char r1 = right.get(right.size()-1-i);
char r2 = right.get(right.size()-1-(i+1));
if(l1==l2 && l2==r1 && r1==r2){
hasChanged = true;
remove.get(j).add(left.size()-1-i);
remove.get(j).add(left.size()-1-(i+1));
remove.get(j+1).add(right.size()-1-i);
remove.get(j+1).add(right.size()-1-(i+1));
}
}
}
for(int i=0; i<n; i++){
List<Character> chars = list.get(i);
PriorityQueue<Integer> targets = remove.get(i);
int last = -1;
int diff = 0;
while(!targets.isEmpty()){
int t = targets.poll();
if(t==last){
continue;
}
chars.remove(t-diff);
diff++;
answer++;
last=t;
}
}
}
return answer;
}
}테스트 1 〉 통과 (0.48ms, 74.6MB)
테스트 2 〉 통과 (0.48ms, 79MB)
테스트 3 〉 통과 (0.46ms, 79MB)
테스트 4 〉 통과 (5.45ms, 81.3MB)
테스트 5 〉 통과 (28.48ms, 93.2MB)
테스트 6 〉 통과 (4.24ms, 72.4MB)
테스트 7 〉 통과 (3.39ms, 77.9MB)
테스트 8 〉 통과 (4.93ms, 82.4MB)
테스트 9 〉 통과 (0.71ms, 86MB)
테스트 10 〉 통과 (2.16ms, 75.2MB)
테스트 11 〉 통과 (9.03ms, 75.9MB)확실히 빨라졌다
'Coding Test' 카테고리의 다른 글
| [프로그래머스] 124나라의 숫자 (0) | 2024.06.03 |
|---|---|
| [프로그래머스] 파일명 정렬 (1) | 2024.06.03 |
| [프로그래머스] 메뉴 리뉴얼 (1) | 2024.06.03 |
| [프로그래머스] 스킬 트리 (0) | 2024.05.21 |
| [프로그래머스] 방문 길이 Java (0) | 2024.05.17 |