Algorithm

Cos Pro 1๊ธ‰ | ๋น„์ˆ์ด ์ด๋™ ๊ฐ€๋Šฅํ•œ ์นธ ๊ฐœ์ˆ˜ ์ฐพ๊ธฐ

osean 2020. 12. 10. 01:50

๋ฌธ์ œ

 

Arori | ๋‹น์‹ ์˜ ์ง€์‹

ํšŒ์›๊ฐ€์ž… ์กฐ๊ฑด์ด ๋งž๋Š”์ง€ ๋‹ค์‹œํ•œ๋ฒˆ ํ™•์ธํ•ด์ฃผ์ƒˆ์š”

www.sysout.co.kr

์ฒด์Šค์—์„œ ๋น„์ˆ(Bishop)์€ ์•„๋ž˜ ๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ๋Œ€๊ฐ์„  ๋ฐฉํ–ฅ์œผ๋กœ ๋ช‡ ์นธ์ด๋“  ํ•œ ๋ฒˆ์— ์ด๋™ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ๋งŒ์•ฝํ•œ ๋ฒˆ์— ์ด๋™ ๊ฐ€๋Šฅํ•œ ์นธ์— ์ฒด์Šค ๋ง์ด ๋†“์—ฌ์žˆ๋‹ค๋ฉด ๊ทธ ์ฒด์Šค ๋ง์„ ์žก์„ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

8 x 8 ํฌ๊ธฐ์˜ ์ฒด์ŠคํŒ ์œ„์— ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋น„์ˆ(Bishop)์ด ๋†“์—ฌ์žˆ์Šต๋‹ˆ๋‹ค. ์ด๋•Œ๋น„์ˆ(Bishop)๋“ค์—๊ฒŒ ํ•œ ๋ฒˆ์— ์žกํžˆ์ง€ ์•Š๋„๋ก ์ƒˆ๋กœ์šด ๋ง์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š” ๋นˆ์นธ์˜ ๊ฐœ์ˆ˜๋ฅผ ๊ตฌํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

์œ„ ๊ทธ๋ฆผ์—์„œ ์›์ด ๊ทธ๋ ค์ง„ ์นธ์€ ๋น„์ˆ์—๊ฒŒ ํ•œ ๋ฒˆ์— ์žกํžˆ๋Š” ์นธ๋“ค์ด๋ฉฐ ๋”ฐ๋ผ์„œ ์ฒด์Šค ๋ง์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š” ๋นˆ์นธ ๊ฐœ์ˆ˜๋Š” 50๊ฐœ์ž…๋‹ˆ๋‹ค.

8 x 8 ์ฒด์ŠคํŒ์— ๋†“์ธ ๋น„์ˆ์˜ ์œ„์น˜ bishops๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ ๋น„์ˆ์—๊ฒŒ ํ•œ ๋ฒˆ์— ์žกํžˆ์ง€ ์•Š๋„๋ก ์ƒˆ๋กœ์šด ์ฒด์Šค ๋ง์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š” ๋นˆ์นธ ๊ฐœ์ˆ˜๋ฅผ return ํ•˜๋„๋ก solution ๋ฉ”์†Œ๋“œ๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”.


๋งค๊ฐœ๋ณ€์ˆ˜ ์„ค๋ช…

์ฒด์ŠคํŒ์— ๋†“์ธ ๋น„์ˆ์˜ ์œ„์น˜ bishops๊ฐ€ solution ๋ฉ”์†Œ๋“œ์˜ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.

  • bishops๋Š” ๋น„์ˆ์˜ ์œ„์น˜๊ฐ€ ๋ฌธ์ž์—ด ํ˜•ํƒœ๋กœ ๋“ค์–ด์žˆ๋Š” ๋ฐฐ์—ด์ž…๋‹ˆ๋‹ค.
  • bishops์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 64 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ๋น„์ˆ์ด ๋†“์ธ ์œ„์น˜๋Š” ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž์™€ ์ˆซ์ž๋กœ ํ‘œ๊ธฐํ•ฉ๋‹ˆ๋‹ค.
    • ์•ŒํŒŒ๋ฒณ ๋Œ€๋ฌธ์ž๋Š” ๊ฐ€๋กœ ๋ฐฉํ–ฅ์ˆซ์ž๋Š” ์„ธ๋กœ ๋ฐฉํ–ฅ ์ขŒํ‘œ๋ฅผ ๋‚˜ํƒ€๋ƒ…๋‹ˆ๋‹ค.
    • ์˜ˆ๋ฅผ ๋“ค์–ด ์œ„ ๊ทธ๋ฆผ์—์„œ ๋น„์ˆ์ด ์žˆ๋Š” ์นธ์€ 'D5'๋ผ๊ณ  ํ‘œํ˜„ํ•ฉ๋‹ˆ๋‹ค.
  • ํ•œ ์นธ์— ์—ฌ๋Ÿฌ ๋น„์ˆ์ด ๋†“์ด๊ฑฐ๋‚˜์ž˜๋ชป๋œ ์œ„์น˜๊ฐ€ ์ฃผ์–ด์ง€๋Š” ๊ฒฝ์šฐ๋Š” ์—†์Šต๋‹ˆ๋‹ค.

return ๊ฐ’ ์„ค๋ช…

๋น„์ˆ์—๊ฒŒ ํ•œ ๋ฒˆ์— ์žกํžˆ์ง€ ์•Š๋„๋ก ์ƒˆ๋กœ์šด ์ฒด์Šค ๋ง์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š” ๋นˆ์นธ์˜ ๊ฐœ์ˆ˜๋ฅผ return ํ•ด์ฃผ์„ธ์š”.


์˜ˆ์‹œ

 

bishops return
["D5"] 50
["D5", "E8", "G2"] 42

์˜ˆ์‹œ ์„ค๋ช…

์˜ˆ์‹œ #1๋ฌธ์ œ์— ๋‚˜์˜จ ์˜ˆ์‹œ์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.

์˜ˆ์‹œ #2

๊ทธ๋ฆผ๊ณผ ๊ฐ™์ด ์›์ด ๊ทธ๋ ค์ง„ ์นธ์€ ๋น„์ˆ์—๊ฒŒ ํ•œ ๋ฒˆ์— ์žกํžˆ๋Š” ์นธ๋“ค์ด๋ฉฐ ๋”ฐ๋ผ์„œ ์ฒด์Šค ๋ง์„ ๋†“์„ ์ˆ˜ ์žˆ๋Š” ๋นˆ์นธ ๊ฐœ์ˆ˜๋Š” 42๊ฐœ์ž…๋‹ˆ๋‹ค.

ํ’€์ด

์„ค๋ช…

๋‚˜๋Š” ํ•ด๋‹น ๋ฌธ์ œ๋ฅผ ๋จผ์ € ๋น„์ˆ์ด ์ด๋™ ๊ฐ€๋Šฅํ•œ ์ขŒํ‘œ์˜ ๊ฐ’์„ ๊ณ„์‚ฐํ•˜๋ ค๊ณ  ํ–ˆ๋‹ค. ๋จผ์ € ์ฒด์ŠคํŒ์€ 8*8์˜ ํฌ๊ธฐ๋ฅผ ๊ฐ€์ง€๋ฏ€๋กœ ๋น„์ˆ์˜ ์ขŒํ‘œ๋Š” 8๋ฅผ ์ดˆ๊ณผํ•˜๊ฑฐ๋‚˜ -1๋ณด๋‹ค ์ž‘์„ ์ˆ˜ ์—†๋‹ค.

๊ทธ๋ฆฌ๊ณ  ๋น„์ˆ์€ ๋Œ€๊ฐ์„ ์œผ๋กœ ์ƒํ•˜์ขŒ์šฐ๋ฅผ ์ด๋™ํ•˜๊ธฐ ๋•Œ๋ฌธ์— ํ˜„์žฌ ๋น„์ˆ์˜ ์œ„์น˜ ๊ธฐ์ค€

 

  • x์ถ•
    • ์ฆ๊ฐ€ํ•˜๋Š” ์˜์—ญ
      • nx = i + ์ฃผ์–ด์ง„ ์ขŒํ‘œ์˜ x๊ฐ’
      • ny = i + ์ฃผ์–ด์ง„ ์ขŒํ‘œ์˜ y๊ฐ’
    • ๊ฐ์†Œํ•˜๋Š” ์˜์—ญ
      • mx = ์ฃผ์–ด์ง„ ์ขŒํ‘œ์˜ x๊ฐ’ - 1
      • my = ์ฃผ์–ด์ง„ ์ขŒํ‘œ์˜ y๊ฐ’ - 1
  • y์ถ•
    • ์ฆ๊ฐ€ํ•˜๋Š” ์˜์—ญ
      • ix = nx
      • iy = ny - (ํ˜„์žฌ ์ธ๋ฑ์Šค * 2)
    • ๊ฐ์†Œํ•˜๋Š” ์˜์—ญ
      • jx = nx - (ํ˜„์žฌ ์ธ๋ฑ์Šค * 2)
      • jy = ny

 

 

์ด๋ ‡๊ฒŒ ์ด 4๊ฐ€์ง€๋กœ ๋‚˜๋ˆ„์–ด ์—ฐ์‚ฐํ•  ์ˆ˜ ์žˆ๋„๋ก ์•„์ด๋””์–ด๋ฅผ ์งฐ๋‹ค.

๊ทธ๋ฆฌ๊ณ  ๋ฐฉ๋ฌธํ•œ ์ขŒํ‘œ๋Š” ํ˜„์žฌ์˜ ๋น„์ˆ์ด ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ์นธ์ด๋ฏ€๋กœ ๋ฐฉ๋ฌธ ์ฒดํฌ๋ฅผ ํ•ด๋†“์€ ๋’ค ์ฒด์ŠคํŒ์„ ๋‹ค์‹œ ์กฐํšŒํ•ด์„œ ๋ฐฉ๋ฌธํ•œ ์นธ์˜ ๊ฐœ์ˆ˜๋ฅผ ์„ธ์–ด์„œ ์ฃผ์–ด์ง„ ๋น„์ˆ์ด ์ด๋™๊ฐ€๋Šฅํ•œ ์นธ์˜ ๊ฐœ์ˆ˜๋ฅผ ํŒŒ์•…ํ•  ์ˆ˜ ์žˆ๊ฒŒ ํ•œ๋‹ค.

์ฝ”๋“œ

package ๋ชจ๋ฐ”์ผ๋ฆฌ๋”_์ฝ”๋”ฉํ…Œ์ŠคํŠธ_03;

public class question_03 {
	public int solution(String[] bishops) {
		// ์—ฌ๊ธฐ์— ์ฝ”๋“œ๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

		// 0. ๋น„์ˆ ์œ„์น˜ ์ธ๋ฑ์Šค ๋ฒˆํ˜ธ๋กœ ๋ณ€ํ™˜
		int[][] idxTmp = new int[bishops.length][2];
		// 1. ๋น„์ˆ ์ขŒํ‘œ ๋ฐฉ๋ฌธ ์„ค์ •
		int[][] xy = new int[8][8];

		// 2. ๋น„์ˆ์˜ ํ˜„์žฌ ์œ„์น˜ ๋ฐฉ๋ฌธ ์ฒดํฌ
		for (int i = 0; i < idxTmp.length; i++) {
			idxTmp[i][0] = bishops[i].charAt(0) - 'A';
			idxTmp[i][1] = bishops[i].charAt(1) - '1';
			xy[idxTmp[i][0]][idxTmp[i][1]] += 1;
		}
		// 4. ๋น„์ˆ ์ด๋™ ๊ฐ€๋Šฅ ๊ฑฐ๋ฆฌ ๋ฐฉ๊ตฐ ์„ค์ • ๋ฐ ๊ฐœ์ˆ˜ ์„ธ๊ธฐ
		// 4-1. ํ˜„์žฌ ๋น„์ˆ ์œ„์น˜ ์œ„ ์•„๋ž˜ ๋กœ ์ด๋™ํ•˜๋ฉด์„œ ๋ฒฝ์— ๋ถ€๋”ชํžˆ๋Š”์ง€, ๊ฒน์น˜๋Š” ๋น„์ˆ ํ˜น์€ ๋‹ค๋ฅธ ๋ง์€ ์—†๋Š”์ง€ ํ™•์ธ
		for (int go = 0; go < bishops.length; go++) {
			int x = idxTmp[go][0], y = idxTmp[go][1];
			int i = 0;
			while (i < 8) {
				// x์ถ•์„ ๊ธฐ์ค€์œผ๋กœ
				int nx = i + idxTmp[go][0], ny = i + idxTmp[go][1];
				int mx = x - 1, my = y - 1;
				// y์ถ•์„ ๊ธฐ์ค€์œผ๋กœ
				int ix = nx, iy = ny - (i * 2);
				int jx = nx - (i * 2), jy = ny;

				// x์ถ• ๊ธฐ์ค€ ์ฆ๊ฐ€ํ•˜๋Š” ์˜์—ญ
				if (nx < 8 && ny < 8 && nx > -1 && ny > -1) {
					xy[nx][ny] = 1;
				}
				// x์ถ• ๊ธฐ์ค€ ๊ฐ์†Œํ•˜๋Š” ์˜์—ญ
				if (mx < 8 && my < 8 && mx > -1 && my > -1) {
					xy[mx][my] = 1;
				}

				// y์ถ• ๊ธฐ์ค€ ์ฆ๊ฐ€ํ•˜๋Š” ์˜์—ญ
				if (ix < 8 && iy < 8 && ix > -1 && iy > -1) {
					xy[ix][iy] = 1;
				}
				// y์ถ• ๊ธฐ์ค€ ๊ฐ์†Œํ•˜๋Š” ์˜์—ญ
				if (jx < 8 && jy < 8 && jx > -1 && jy > -1) {
					xy[jx][jy] = 1;
				}

				x = mx;
				y = my;
				i++;
			}
		}

		int answer = 0;
		for (int i = 0; i < xy.length; i++) {
			for (int k = xy.length - 1; k > -1; k--) {
				System.out.print(xy[i][k] + " ");
				if (xy[i][k] == 0) {
					answer++;
				}
			}
			System.out.println();
		}
		System.out.println("answer = " + answer);
		return answer;
	}

	// ์•„๋ž˜๋Š” ํ…Œ์ŠคํŠธ์ผ€์ด์Šค ์ถœ๋ ฅ์„ ํ•ด๋ณด๊ธฐ ์œ„ํ•œ main ๋ฉ”์†Œ๋“œ์ž…๋‹ˆ๋‹ค.
	public static void main(String[] args) {
		question_03 sol = new question_03();
		String[] bishops1 = { new String("D5") };
		int ret1 = sol.solution(bishops1);

		// [์‹คํ–‰] ๋ฒ„ํŠผ์„ ๋ˆ„๋ฅด๋ฉด ์ถœ๋ ฅ ๊ฐ’์„ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
		System.out.println("solution ๋ฉ”์†Œ๋“œ์˜ ๋ฐ˜ํ™˜ ๊ฐ’์€ " + ret1 + " ์ž…๋‹ˆ๋‹ค.");
		System.out.println();
		String[] bishops2 = { new String("D5"), new String("E8"), new String("G2") };
		int ret2 = sol.solution(bishops2);

		// [์‹คํ–‰] ๋ฒ„ํŠผ์„ ๋ˆ„๋ฅด๋ฉด ์ถœ๋ ฅ ๊ฐ’์„ ๋ณผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
		System.out.println("solution ๋ฉ”์†Œ๋“œ์˜ ๋ฐ˜ํ™˜ ๊ฐ’์€ " + ret2 + " ์ž…๋‹ˆ๋‹ค.");
	}
}