deo2kim
๋งž์™œํ‹€
deo2kim
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ
    • CS
      • Algorithm
      • Data Structure
      • Network
      • DB
      • OS
    • Algorithm Problem
      • Python
      • JavaScript
    • Programming language
      • Python
      • JavaScript
    • Tool
      • Jquery
      • React
    • ๊ฐœ๋ฐœ
    • Infra

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
deo2kim
Algorithm Problem/Python

[python] ๋ฐฑ์ค€ - 17140. ์ด์ฐจ์› ๋ฐฐ์—ด๊ณผ ์—ฐ์‚ฐ

[python] ๋ฐฑ์ค€ - 17140. ์ด์ฐจ์› ๋ฐฐ์—ด๊ณผ ์—ฐ์‚ฐ
Algorithm Problem/Python

[python] ๋ฐฑ์ค€ - 17140. ์ด์ฐจ์› ๋ฐฐ์—ด๊ณผ ์—ฐ์‚ฐ

2020. 11. 30. 12:17
๋ฐ˜์‘ํ˜•

๐Ÿค”๋ฌธ์ œ ํ•ด๊ฒฐ

  • G4 | ์‹œ๋ฎฌ๋ ˆ์ด์…˜, ๊ตฌํ˜„

๋ฌธ์ œ๋ฅผ ์ดํ•ดํ•˜๋Š”๋ฐ ์‹œ๊ฐ„์ด ์ข€ ๊ฑธ๋ ธ๋‹ค.

  • k๊ฐ’์ด ๋งž๋Š”์ง€ ํ™•์ธํ•˜๊ณ  ์•„๋‹ˆ๋ผ๋ฉด ์‹œ๊ฐ„์„ +1 ์ฆ๊ฐ€์‹œํ‚จ๋‹ค.
  • R์—ฐ์‚ฐ์ธ์ง€ C์—ฐ์‚ฐ์ธ์ง€ ํ™•์ธํ•œ๋‹ค.
  • R ์—ฐ์‚ฐ์ผ ๊ฒฝ์šฐ
    • ๊ฐ ํ–‰์˜ ์ˆซ์ž์™€ ํ•ด๋‹น ์ˆซ์ž์˜ ๊ฐœ์ˆ˜๋ฅผ ๋ฆฌ์ŠคํŠธ๋‚˜ ํŠœํ”Œ ํ˜•ํƒœ๋กœ ์ €์žฅํ•œ๋‹ค. [(1, 1), (2, 1)] ์ด๋Ÿฐ์‹์œผ๋กœ
    • sort๋ฅผ ์ด์šฉํ•ด ์ •๋ ฌํ•œ๋‹ค.
    • ํŠœํ”Œ์„ ํ’€์–ด์„œ ์ˆซ์ž ํ•˜๋‚˜ํ•˜๋‚˜์˜ ํ˜•ํƒœ๋กœ ๋ฆฌ์ŠคํŠธ์— ์ €์žฅํ•˜๊ณ  ๋‚˜๋จธ์ง€ ๊ธธ์ด๋ฅผ 0์œผ๋กœ ์ฑ„์›Œ๋„ฃ๋Š”๋‹ค.
  • C ์—ฐ์‚ฐ์ผ ๊ฒฝ์šฐ ํ–‰๊ณผ ์—ด์„ ๋ฐ”๊ฟ”์„œ ์œ„์˜ ๊ณผ์ •์„ ๋˜‘๊ฐ™์ด ์ง„ํ–‰ํ•œ ํ›„ ๋‹ค์‹œ ํ–‰๊ณผ ์—ด์„ ๋ฐ”๊ฟ”์ค€๋‹ค.

 

๐Ÿ’ป์†Œ์Šค ์ฝ”๋“œ

def is_k():
    if r - 1 < len(arr) and c - 1 < len(arr[0]):
        if arr[r - 1][c - 1] == k:
            return True

    return False


def update_arr():
    # ๊ฐœ์ˆ˜ ์„ธ๊ธฐ
    tmp_matrix = []
    max_length = 0
    for i in range(len(arr)):
        numbers = set(arr[i])
        tmp_lst = []
        for num in numbers:
            if num == 0:
                continue
            tmp_lst.append((num, arr[i].count(num)))
        max_length = max(max_length, len(tmp_lst) * 2)
        tmp_matrix.append(tmp_lst)

    # ์ •๋ ฌํ•˜๊ธฐ
    for i in range(len(tmp_matrix)):
        tmp_matrix[i].sort(key=lambda x: (x[1], x[0]))

    # ๊ธธ์ด ๋งž์ถ”๊ธฐ๊ณ  ๋ฐฐ์—ด์— ๋„ฃ๊ธฐ
    for i in range(len(tmp_matrix)):
        tmp_lst = []
        for j in range(len(tmp_matrix[i])):
            tmp_lst.append(tmp_matrix[i][j][0])
            tmp_lst.append(tmp_matrix[i][j][1])
        tmp_lst.extend([0] * (max_length - len(tmp_lst)))
        arr[i] = tmp_lst


if __name__ == '__main__':
    r, c, k = map(int, input().split())
    arr = [list(map(int, input().split())) for _ in range(3)]

    time = 0
    while time < 101:

        # k ๊ฐ’ ๋งž๋Š”์ง€ ํ™•์ธ
        if is_k():
            print(time)
            break

        time += 1  # ์‹œ๊ฐ„ ์ฆ๊ฐ€
        # R์—ฐ์‚ฐ vs C์—ฐ์‚ฐ
        if len(arr) >= len(arr[0]):  # ํ–‰์˜ ๊ฐœ์ˆ˜๊ฐ€ ์—ด์˜ ๊ฐœ์ˆ˜๋ณด๋‹ค ํฌ๊ฑฐ๋‚˜ ๊ฐ™์œผ๋ฉด
            update_arr()
        else:  # ํ–‰์˜ ๊ฐœ์ˆ˜๊ฐ€ ์—ด์˜ ๊ฐœ์ˆ˜๋ณด๋‹ค ์ ์œผ๋ฉด
            arr = list(map(list, zip(*arr)))  # ํ–‰๊ณผ ์—ด ๋ฐ”๊พธ๊ธฐ
            update_arr()
            arr = list(map(list, zip(*arr)))  # ๋‹ค์‹œ ํ–‰๊ณผ ์—ด ๋ฐ”๊พธ๊ธฐ
    else:
        print(-1)
 

 

๐Ÿ“•๋ฌธ์ œ ํ™•์ธ

์ถœ์ฒ˜: BACKJOON ONLINE JUDGE

๋งํฌ: https://www.acmicpc.net/problem/17140

 

17140๋ฒˆ: ์ด์ฐจ์› ๋ฐฐ์—ด๊ณผ ์—ฐ์‚ฐ

์ฒซ์งธ ์ค„์— r, c, k๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค r, c, k โ‰ค 100) ๋‘˜์งธ ์ค„๋ถ€ํ„ฐ 3๊ฐœ์˜ ์ค„์— ๋ฐฐ์—ด A์— ๋“ค์–ด์žˆ๋Š” ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๋ฐฐ์—ด A์— ๋“ค์–ด์žˆ๋Š” ์ˆ˜๋Š” 100๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ์ž์—ฐ์ˆ˜์ด๋‹ค.

www.acmicpc.net

๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€ (์ƒˆ์ฐฝ์—ด๋ฆผ)

'Algorithm Problem > Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[python] SWEA - 10580. ์ „๋ด‡๋Œ€  (0) 2020.12.06
[python] SWEA - 4047. ์˜์ค€์ด์˜ ์นด๋“œ ์นด์šดํŒ…  (0) 2020.12.01
[python] ๋ฐฑ์ค€ - 10819. ์ฐจ์ด๋ฅผ ์ตœ๋Œ€๋กœ  (0) 2020.11.29
[python] ๋ฐฑ์ค€ - 18428. ๊ฐ์‹œ ํ”ผํ•˜๊ธฐ  (0) 2020.11.28
[python] ๋ฐฑ์ค€ - 1916. ์ตœ์†Œ๋น„์šฉ ๊ตฌํ•˜๊ธฐ  (0) 2020.11.27
  • ๐Ÿค”๋ฌธ์ œ ํ•ด๊ฒฐ
  • ๐Ÿ’ป์†Œ์Šค ์ฝ”๋“œ
  • ๐Ÿ“•๋ฌธ์ œ ํ™•์ธ
'Algorithm Problem/Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [python] SWEA - 10580. ์ „๋ด‡๋Œ€
  • [python] SWEA - 4047. ์˜์ค€์ด์˜ ์นด๋“œ ์นด์šดํŒ…
  • [python] ๋ฐฑ์ค€ - 10819. ์ฐจ์ด๋ฅผ ์ตœ๋Œ€๋กœ
  • [python] ๋ฐฑ์ค€ - 18428. ๊ฐ์‹œ ํ”ผํ•˜๊ธฐ
deo2kim
deo2kim
์ฝ”๋”ฉ ๊ธฐ๋กํ•˜๊ธฐ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”

๋‹จ์ถ•ํ‚ค

๋‚ด ๋ธ”๋กœ๊ทธ

๋‚ด ๋ธ”๋กœ๊ทธ - ๊ด€๋ฆฌ์ž ํ™ˆ ์ „ํ™˜
Q
Q
์ƒˆ ๊ธ€ ์“ฐ๊ธฐ
W
W

๋ธ”๋กœ๊ทธ ๊ฒŒ์‹œ๊ธ€

๊ธ€ ์ˆ˜์ • (๊ถŒํ•œ ์žˆ๋Š” ๊ฒฝ์šฐ)
E
E
๋Œ“๊ธ€ ์˜์—ญ์œผ๋กœ ์ด๋™
C
C

๋ชจ๋“  ์˜์—ญ

์ด ํŽ˜์ด์ง€์˜ URL ๋ณต์‚ฌ
S
S
๋งจ ์œ„๋กœ ์ด๋™
T
T
ํ‹ฐ์Šคํ† ๋ฆฌ ํ™ˆ ์ด๋™
H
H
๋‹จ์ถ•ํ‚ค ์•ˆ๋‚ด
Shift + /
โ‡ง + /

* ๋‹จ์ถ•ํ‚ค๋Š” ํ•œ๊ธ€/์˜๋ฌธ ๋Œ€์†Œ๋ฌธ์ž๋กœ ์ด์šฉ ๊ฐ€๋Šฅํ•˜๋ฉฐ, ํ‹ฐ์Šคํ† ๋ฆฌ ๊ธฐ๋ณธ ๋„๋ฉ”์ธ์—์„œ๋งŒ ๋™์ž‘ํ•ฉ๋‹ˆ๋‹ค.