[Greedy] 27514번 - 1차원 2048

🔗 문제 링크

백준 27514번 - 1차원 2048

📝 잘못된.. 풀이

처음엔 투포인터가 떠올라서
start, end 인덱스를 두고 두 인덱스가 배열의 크기보다 작을때만 while문을 돌면서 계산을 하도록 코드를 짰다.
하지만 계속해서 런타임에러와 시간초과가 떴다.
수열의 원소를 int형으로 받은 것도 에러 뜨는 것에 한 몫했다.

아주 멍청한 생각을 몇시간동안 했다....

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		LinkedList<Long> arr = new LinkedList<>();
		
		for(int i = 0; i < N; i++) {
			long num = Long.parseLong(st.nextToken());
			if(num != 0) {
				arr.add(num);
			}
		}
		
		int start = 0, end = 1;
		long n1, n2;
		int size = arr.size();
		
		while(start < size && end < size) {
			n1 = arr.get(start);
			n2 = arr.get(end);
			
			if(n1 == n2) {
				arr.set(start, 2 * n1);
				arr.remove(end);
				
				size = arr.size();
				start = 0;
				end = start + 1;
			}
			else {
				end++;
				if(end == size) {
					start++;
					end = start + 1;
				}
			}
		}
		
		
		long max = Integer.MIN_VALUE;
		for(long num: arr) {
			if(num > max) {
				max = num;
			}
		}
		
		System.out.println(max);
	}

}

📝 풀이

HashMap은 원하는 키값을 remove 메소드로 삭제할 수 있다는 점을 활용했다.

입력을 받으면서 수열의 원소가 0이면 아무 동작도 하지않고
0이 아닐때만 add 함수의 매개변수로 넘겼다.

add 메소드에서

• map에 특정 원소가 이미 존재하면
  특정 원소를 삭제하고 2배한 값을 다시 add로 넘겼다.

• map에 특정 원소가 존재하지 않으면
  HashMap 메소드 put을 사용해서 값을 추가했다.

마지막으로 해시맵의 모든 키를 담은 Set 컬렉션을 반환해서 Collections.max()로 최댓값을 출력하도록 구현했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.HashMap;
import java.util.StringTokenizer;

public class 일차원2048_27514 {
	
	static HashMap<Long, Integer> map = new HashMap<>();
    
	static void add(Long num) {
		if(!map.containsKey(num))
			map.put(num, 1);
		else {
			map.remove(num);
			add(2 * num);
		}
	}

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < N; i++) {
			long num = Long.parseLong(st.nextToken());
			if(num != 0) {
				add(num);
			}
		}
		
		System.out.println(Collections.max(map.keySet()));
		
	}

}