Algorithm/BOJ

๋ฐฑ์ค€(BOJ) 1158๋ฒˆ ์š”์„ธํ‘ธ์Šค [์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)/์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ]

2021. 7. 7. 20:49
๋ชฉ์ฐจ
  1. [๋ฌธ์ œ]
  2. [์ž…๋ ฅ]
  3. [์ถœ๋ ฅ]

https://www.acmicpc.net/problem/1158

 

1158๋ฒˆ: ์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ

์ฒซ์งธ ์ค„์— N๊ณผ K๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค K โ‰ค N โ‰ค 5,000)

www.acmicpc.net

 

 

 

[๋ฌธ์ œ]

์š”์„ธํ‘ธ์Šค ๋ฌธ์ œ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ N๋ช…์˜ ์‚ฌ๋žŒ์ด ์›์„ ์ด๋ฃจ๋ฉด์„œ ์•‰์•„์žˆ๊ณ , ์–‘์˜ ์ •์ˆ˜ K(โ‰ค N)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ์ด์ œ ์ˆœ์„œ๋Œ€๋กœ K๋ฒˆ์งธ ์‚ฌ๋žŒ์„ ์ œ๊ฑฐํ•œ๋‹ค. ํ•œ ์‚ฌ๋žŒ์ด ์ œ๊ฑฐ๋˜๋ฉด ๋‚จ์€ ์‚ฌ๋žŒ๋“ค๋กœ ์ด๋ฃจ์–ด์ง„ ์›์„ ๋”ฐ๋ผ ์ด ๊ณผ์ •์„ ๊ณ„์†ํ•ด ๋‚˜๊ฐ„๋‹ค. ์ด ๊ณผ์ •์€ N๋ช…์˜ ์‚ฌ๋žŒ์ด ๋ชจ๋‘ ์ œ๊ฑฐ๋  ๋•Œ๊นŒ์ง€ ๊ณ„์†๋œ๋‹ค. ์›์—์„œ ์‚ฌ๋žŒ๋“ค์ด ์ œ๊ฑฐ๋˜๋Š” ์ˆœ์„œ๋ฅผ (N, K)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์ด๋ผ๊ณ  ํ•œ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด (7, 3)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์€ <3, 6, 2, 7, 5, 1, 4>์ด๋‹ค.

N๊ณผ K๊ฐ€ ์ฃผ์–ด์ง€๋ฉด (N, K)-์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์„ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

 

[์ž…๋ ฅ]

์ฒซ์งธ ์ค„์— N๊ณผ K๊ฐ€ ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ˆœ์„œ๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. (1 โ‰ค K โ‰ค N โ‰ค 5,000)

 

[์ถœ๋ ฅ]

์˜ˆ์ œ์™€ ๊ฐ™์ด ์š”์„ธํ‘ธ์Šค ์ˆœ์—ด์„ ์ถœ๋ ฅํ•œ๋‹ค.

 

 

class Node:
    def __init__(self, key = None):
        self.key = key
        self.next = self.prev = self

    def __str__(self):
        return str(self.key)

class DoubleLinkedList:
    def __init__(self):
        self.head = Node()
        self.size = 0

    def __len__(self):
        return self.size

    def splice(self, a, b, x):
        if a == None or b == None or x == None: return

        a.prev.next = b.next
        b.next.prev = a.prev
        x.next.prev = b
        b.next = x.next
        a.prev = x
        x.next = a

    def moveBefore(self, a, x):
        self.splice(a, a, x.prev)
        
    def insertBefore(self, x, key):
        self.moveBefore(Node(key), x)

    def pushBack(self, key):
        self.insertBefore(self.head, key)
        self.size += 1

    def delete(self, x):
        if x == None or x == self.head: return

        x.prev.next, x.next.prev = x.next, x.prev
        self.size -= 1
        return x.key

    def search(self, key):
        v = self.head.next
        while v != self.head:
            if v.key == key: return v
            v = v.next
        return None

N,K = map(int, input().split())
L = DoubleLinkedList()
Answer = []

for i in range(1, N+1):
    L.pushBack(i)
    
v = L.head
while L.__len__() != 0:
    for i in range(1, K):
        if v.key == L.head.key: v = v.next
        x = L.search(v.key)
        L.pushBack(L.delete(x))
        v = v.next
    if v.key == L.head.key: v = v.next
    x = L.search(v.key)
    L.delete(x)
    Answer.append(v.key)
    v = v.next

print("<", end="")
print(", ".join(str(v) for v in Answer), end="")
print(">")

 

ํ๋ฅผ ์‚ฌ์šฉํ•ด์„œ ์‰ฝ๊ฒŒ ํ’€ ์ˆ˜ ์žˆ์ง€๋งŒ ์›ํ˜•์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ๋ฅผ ์‚ฌ์šฉํ•ด์„œ ํ’€์–ด๋ดค๋‹ค!

๋ฐฑ์ค€์—์„œ python3๋กœ ์ œ์ถœํ•˜๋ฉด ์ž๊พธ ์‹œ๊ฐ„์ดˆ๊ณผ ์—๋Ÿฌ๊ฐ€ ๋ฐœ์ƒํ•ด์„œ ๋” ๋น ๋ฅธ pypy๋กœ ์ œ์ถœํ–ˆ๋Š”๋ฐ ํ†ต๊ณผ๋๋‹ค. ์ด๋ ‡๊ฒŒ ํ•ด๋„ ๋˜๋Š”๊ฒƒ์ธ๊ฐ€,,ใ…Žใ…Ž

 

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

๋ฐฑ์ค€(BOJ) 11047๋ฒˆ ๋™์ „ 0 [๊ทธ๋ฆฌ๋””(Greedy)/์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)]  (0) 2021.08.11
๋ฐฑ์ค€(BOJ) 1931๋ฒˆ ํšŒ์˜์‹ค๋ฐฐ์ • [๊ทธ๋ฆฌ๋””(Greedy)/์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)]  (0) 2021.08.07
๋ฐฑ์ค€(BOJ) 11000๋ฒˆ ๊ฐ•์˜์‹ค๋ฐฐ์ • [๊ทธ๋ฆฌ๋””(Greedy)/์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)/ํ]  (0) 2021.08.06
๋ฐฑ์ค€(BOJ) 9012๋ฒˆ ์Šคํƒ๋ฌธ์ œ [ํŒŒ์ด์ฌ(python)]  (0) 2021.07.02
๋ฐฑ์ค€(BOJ) 10828๋ฒˆ ์Šคํƒ๋ฌธ์ œ [ํŒŒ์ด์ฌ(python) / ์‹œ๊ฐ„์ดˆ๊ณผ ์—๋Ÿฌ]  (0) 2021.06.28
  1. [๋ฌธ์ œ]
  2. [์ž…๋ ฅ]
  3. [์ถœ๋ ฅ]
'Algorithm/BOJ' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • ๋ฐฑ์ค€(BOJ) 1931๋ฒˆ ํšŒ์˜์‹ค๋ฐฐ์ • [๊ทธ๋ฆฌ๋””(Greedy)/์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)]
  • ๋ฐฑ์ค€(BOJ) 11000๋ฒˆ ๊ฐ•์˜์‹ค๋ฐฐ์ • [๊ทธ๋ฆฌ๋””(Greedy)/์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)/ํ]
  • ๋ฐฑ์ค€(BOJ) 9012๋ฒˆ ์Šคํƒ๋ฌธ์ œ [ํŒŒ์ด์ฌ(python)]
  • ๋ฐฑ์ค€(BOJ) 10828๋ฒˆ ์Šคํƒ๋ฌธ์ œ [ํŒŒ์ด์ฌ(python) / ์‹œ๊ฐ„์ดˆ๊ณผ ์—๋Ÿฌ]
DAHLIA CHOI
DAHLIA CHOI
DAHLIA CHOI
๐ŸŒผ dali's log ๐ŸŒผ
DAHLIA CHOI
์ „์ฒด
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (103)
    • Spring (42)
    • JAVA & OOP (8)
    • AWS (2)
    • DevOps (5)
    • Network (7)
    • DB (5)
    • Algorithm (9)
      • BOJ (6)
      • PROGRAMMERS (2)
      • LEETCODE (0)
    • Books (5)
    • ํŠธ๋Ÿฌ๋ธ” ์ŠˆํŒ… (5)
    • ํšŒ๊ณ  (0)
    • ๊ธฐํƒ€ (5)
    • FRENCH (1)
    • ํ•„์‚ฌ (2)
    • ๊ฒฝํ—˜ (5)

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

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

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

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๊ธ€

hELLO ยท Designed By ์ •์ƒ์šฐ.
DAHLIA CHOI
๋ฐฑ์ค€(BOJ) 1158๋ฒˆ ์š”์„ธํ‘ธ์Šค [์•Œ๊ณ ๋ฆฌ์ฆ˜/ํŒŒ์ด์ฌ(python)/์—ฐ๊ฒฐ๋ฆฌ์ŠคํŠธ]
์ƒ๋‹จ์œผ๋กœ

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

๋‹จ์ถ•ํ‚ค

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

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

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

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

๋ชจ๋“  ์˜์—ญ

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

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