[SWEA Java] 19113번 식료품 가게

💡문제

[D3] 식료품 가게 - 19113

문제 링크

성능 요약

메모리: 31,236 KB, 시간: 154 ms, 코드길이: 1,207 Bytes

---

🤔접근법

주어진 N개의 수들 중에 기존의 수와 75% 할인된 수의 짝에서 75% 할인된 정수를 오름차순으로 출력하는 문제

범위 체크 및 시간복잡도 예상

• 1 ≤ N ≤ 100
• 1 ≤ Pi ≤ 10^9 (십억)
• $O(N^4)$까지도 가능하다.

풀이법

⭕ 접근 방법. 완탐

1. 0 ~ N-1 인덱스 까지 i 반복 → $O(N^2)$
   1. i ~ N-1 인덱스 까지 j 반복 → $O(N^2)$
      • i 와 j * 4/3가 같다면 짝을 찾았으니 표시

➡️ 해당 풀이법의 시간 복잡도 : $O(N^4)$

---

😎SUCCESS

로직에 실수가 없나 잘 확인하자 ..

---

👩‍💻 코드

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

public class Solution_19113 {

	static int TC;
	static int N;
	static long price[];
	static boolean isused[];
	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		TC = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();
		for (int tc = 1; tc <= TC ; tc++) {
			sb.append("#"+tc+" ");

			N = Integer.parseInt(br.readLine());
			price = new long[N*2];
			isused = new boolean[N*2];
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 0; i < N*2; i++) {
				price[i] = Long.parseLong(st.nextToken());
			}

			for (int i = 0; i < N*2 ; i++) {
				if(isused[i]) continue;
				long originPrice = (price[i]/3L)*4L;
				for (int j = i+1; j < N*2 ; j++) {
					if(!isused[j] && price[j] == originPrice){
						isused[i] = true;
						isused[j] = true;
						sb.append(price[i]+" ");
						break;
					}
				}
			}
			sb.append("\n");
		}

		System.out.println(sb.toString());

	}

}